QGIS API Documentation  3.6.0-Noosa (5873452)
problem.cpp
Go to the documentation of this file.
1 /*
2  * libpal - Automated Placement of Labels Library
3  *
4  * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5  * University of Applied Sciences, Western Switzerland
6  * http://www.hes-so.ch
7  *
8  * Contact:
9  * maxence.laurent <at> heig-vd <dot> ch
10  * or
11  * eric.taillard <at> heig-vd <dot> ch
12  *
13  * This file is part of libpal.
14  *
15  * libpal is free software: you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation, either version 3 of the License, or
18  * (at your option) any later version.
19  *
20  * libpal is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27  *
28  */
29 
30 #include "pal.h"
31 #include "palstat.h"
32 #include "layer.h"
33 #include "rtree.hpp"
34 #include "feature.h"
35 #include "geomfunction.h"
36 #include "labelposition.h"
37 #include "problem.h"
38 #include "util.h"
39 #include "priorityqueue.h"
40 #include "internalexception.h"
41 #include <cfloat>
42 #include <limits> //for std::numeric_limits<int>::max()
43 
44 #include "qgslabelingengine.h"
45 
46 using namespace pal;
47 
48 inline void delete_chain( Chain *chain )
49 {
50  if ( chain )
51  {
52  delete[] chain->feat;
53  delete[] chain->label;
54  delete chain;
55  }
56 }
57 
59 {
60  bbox[0] = 0;
61  bbox[1] = 0;
62  bbox[2] = 0;
63  bbox[3] = 0;
64  featWrap = nullptr;
65  candidates = new RTree<LabelPosition *, double, 2, double>();
66  candidates_sol = new RTree<LabelPosition *, double, 2, double>();
67  candidates_subsol = nullptr;
68 }
69 
71 {
72  if ( sol )
73  {
74  delete[] sol->s;
75  delete sol;
76  }
77 
78  delete[] featWrap;
79  delete[] featStartId;
80  delete[] featNbLp;
81 
82  qDeleteAll( mLabelPositions );
83  mLabelPositions.clear();
84 
85  delete[] inactiveCost;
86 
87  delete candidates;
88  delete candidates_sol;
89 
90  delete candidates_subsol;
91 }
92 
93 typedef struct
94 {
95  int id;
96  double inactiveCost;
97  double nbOverlap;
98 } Ft;
99 
100 inline bool borderSizeInc( void *l, void *r )
101 {
102  return ( reinterpret_cast< SubPart * >( l ) )->borderSize > ( reinterpret_cast< SubPart * >( r ) )->borderSize;
103 }
104 
106 {
107 
108  int i;
109  int j;
110  int k;
111 
112  int counter = 0;
113 
114  int lpid;
115 
116  bool *ok = new bool[nblp];
117  bool run = true;
118 
119  for ( i = 0; i < nblp; i++ )
120  ok[i] = false;
121 
122 
123  double amin[2];
124  double amax[2];
125  LabelPosition *lp2 = nullptr;
126 
127  while ( run )
128  {
129  run = false;
130  for ( i = 0; i < nbft; i++ )
131  {
132  // ok[i] = true;
133  for ( j = 0; j < featNbLp[i]; j++ ) // foreach candidate
134  {
135  if ( !ok[featStartId[i] + j] )
136  {
137  if ( mLabelPositions.at( featStartId[i] + j )->getNumOverlaps() == 0 ) // if candidate has no overlap
138  {
139  run = true;
140  ok[featStartId[i] + j] = true;
141  // 1) remove worse candidates from candidates
142  // 2) update nb_overlaps
143  counter += featNbLp[i] - j - 1;
144 
145  for ( k = j + 1; k < featNbLp[i]; k++ )
146  {
147 
148  lpid = featStartId[i] + k;
149  ok[lpid] = true;
150  lp2 = mLabelPositions.at( lpid );
151 
152  lp2->getBoundingBox( amin, amax );
153 
154  nbOverlap -= lp2->getNumOverlaps();
155  candidates->Search( amin, amax, LabelPosition::removeOverlapCallback, reinterpret_cast< void * >( lp2 ) );
156  lp2->removeFromIndex( candidates );
157  }
158 
159  featNbLp[i] = j + 1;
160  break;
161  }
162  }
163  }
164  }
165  }
166 
167  this->nblp -= counter;
168  delete[] ok;
169 }
170 
172 {
173  int i;
174 
175  if ( sol )
176  {
177  delete[] sol->s;
178  delete sol;
179  }
180 
181  sol = new Sol();
182  sol->s = new int[nbft];
183 
184  for ( i = 0; i < nbft; i++ )
185  sol->s[i] = -1;
186 
187  sol->cost = nbft;
188 }
189 
190 
191 
192 
193 typedef struct
194 {
195  PriorityQueue *list = nullptr;
196  LabelPosition *lp = nullptr;
197  RTree <LabelPosition *, double, 2, double> *candidates;
198 } FalpContext;
199 
200 bool falpCallback2( LabelPosition *lp, void *ctx )
201 {
202  FalpContext *context = reinterpret_cast< FalpContext * >( ctx );
203  LabelPosition *lp2 = context->lp;
204  PriorityQueue *list = context->list;
205 
206  if ( lp->getId() != lp2->getId() && list->isIn( lp->getId() ) && lp->isInConflict( lp2 ) )
207  {
208  list->decreaseKey( lp->getId() );
209  }
210  return true;
211 }
212 
213 
214 void ignoreLabel( LabelPosition *lp, PriorityQueue *list, RTree <LabelPosition *, double, 2, double> *candidates )
215 {
216 
217 
218  FalpContext *context = new FalpContext();
219  context->candidates = nullptr;
220  context->list = list;
221  double amin[2];
222  double amax[2];
223 
224  if ( list->isIn( lp->getId() ) )
225  {
226  list->remove( lp->getId() );
227 
228  lp->getBoundingBox( amin, amax );
229 
230  context->lp = lp;
231  candidates->Search( amin, amax, falpCallback2, context );
232  }
233 
234  delete context;
235 }
236 
237 
238 bool falpCallback1( LabelPosition *lp, void *ctx )
239 {
240  FalpContext *context = reinterpret_cast< FalpContext * >( ctx );
241  LabelPosition *lp2 = context->lp;
242  PriorityQueue *list = context->list;
243  RTree <LabelPosition *, double, 2, double> *candidates = context->candidates;
244 
245  if ( lp2->isInConflict( lp ) )
246  {
247  ignoreLabel( lp, list, candidates );
248  }
249  return true;
250 }
251 
252 
253 
254 /* Better initial solution
255  * Step one FALP (Yamamoto, Camara, Lorena 2005)
256  */
258 {
259  int i, j;
260  int label;
261  PriorityQueue *list = nullptr;
262 
263  init_sol_empty();
264 
265  list = new PriorityQueue( nblp, all_nblp, true );
266 
267  double amin[2];
268  double amax[2];
269 
270  FalpContext *context = new FalpContext();
271  context->candidates = candidates;
272  context->list = list;
273 
274  LabelPosition *lp = nullptr;
275 
276  for ( i = 0; i < nbft; i++ )
277  for ( j = 0; j < featNbLp[i]; j++ )
278  {
279  label = featStartId[i] + j;
280  try
281  {
282  list->insert( label, mLabelPositions.at( label )->getNumOverlaps() );
283  }
284  catch ( pal::InternalException::Full & )
285  {
286  continue;
287  }
288  }
289 
290  while ( list->getSize() > 0 ) // O (log size)
291  {
292  if ( pal->isCanceled() )
293  {
294  delete context;
295  delete list;
296  return;
297  }
298 
299  label = list->getBest(); // O (log size)
300 
301 
302  lp = mLabelPositions.at( label );
303 
304  if ( lp->getId() != label )
305  {
306  //error
307  }
308 
309  int probFeatId = lp->getProblemFeatureId();
310  sol->s[probFeatId] = label;
311 
312  for ( i = featStartId[probFeatId]; i < featStartId[probFeatId] + featNbLp[probFeatId]; i++ )
313  {
314  ignoreLabel( mLabelPositions.at( i ), list, candidates );
315  }
316 
317 
318  lp->getBoundingBox( amin, amax );
319 
320  context->lp = lp;
321  candidates->Search( amin, amax, falpCallback1, reinterpret_cast< void * >( context ) );
322  candidates_sol->Insert( amin, amax, lp );
323  }
324 
325  delete context;
326 
327 
328 
329 
330  if ( displayAll )
331  {
332  int nbOverlap;
333  int start_p;
334  LabelPosition *retainedLabel = nullptr;
335  int p;
336 
337  for ( i = 0; i < nbft; i++ ) // forearch hidden feature
338  {
339  if ( sol->s[i] == -1 )
340  {
341  nbOverlap = std::numeric_limits<int>::max();
342  start_p = featStartId[i];
343  for ( p = 0; p < featNbLp[i]; p++ )
344  {
345  lp = mLabelPositions.at( start_p + p );
346  lp->resetNumOverlaps();
347 
348  lp->getBoundingBox( amin, amax );
349 
350 
351  candidates_sol->Search( amin, amax, LabelPosition::countOverlapCallback, lp );
352 
353  if ( lp->getNumOverlaps() < nbOverlap )
354  {
355  retainedLabel = lp;
356  nbOverlap = lp->getNumOverlaps();
357  }
358  }
359  sol->s[i] = retainedLabel->getId();
360 
361  retainedLabel->insertIntoIndex( candidates_sol );
362 
363  }
364  }
365  }
366 
367  delete list;
368 }
369 
371 {
372 
373  if ( nbft == 0 )
374  return;
375 
376  int i;
377  int seed;
378  bool *ok = new bool[nbft];
379 
380  int r = pal->popmusic_r;
381 
382  SearchMethod searchMethod = pal->searchMethod;
383 
384  candidates_subsol = new RTree<LabelPosition *, double, 2, double>();
385 
386  double delta = 0.0;
387 
388  int it = 0;
389 
390  SubPart *current = nullptr;
391 
392  labelPositionCost = new double[all_nblp];
393  nbOlap = new int[all_nblp];
394 
395  featWrap = new int[nbft];
396  memset( featWrap, -1, sizeof( int ) *nbft );
397 
398  SubPart **parts = new SubPart*[nbft];
399  int *isIn = new int[nbft];
400 
401  memset( isIn, 0, sizeof( int ) *nbft );
402 
403 
404  for ( i = 0; i < nbft; i++ )
405  {
406  parts[i] = subPart( r, i, isIn );
407  ok[i] = false;
408  }
409  delete[] isIn;
410  Util::sort( reinterpret_cast< void ** >( parts ), nbft, borderSizeInc );
411  //sort ((void**)parts, nbft, borderSizeDec);
412 
413  init_sol_falp();
414 
415  solution_cost();
416 
417  int popit = 0;
418 
419  seed = 0;
420  while ( true )
421  {
422  it++;
423  /* find the next seed not ok */
424  for ( i = ( seed + 1 ) % nbft; ok[i] && i != seed; i = ( i + 1 ) % nbft )
425  ;
426 
427  if ( i == seed && ok[seed] )
428  {
429  current = nullptr; // everything is OK :-)
430  break;
431  }
432  else
433  {
434  seed = i;
435  current = parts[seed];
436  }
437 
438  // update sub part solution
439  candidates_subsol->RemoveAll();
440 
441  for ( i = 0; i < current->subSize; i++ )
442  {
443  current->sol[i] = sol->s[current->sub[i]];
444  if ( current->sol[i] != -1 )
445  {
446  mLabelPositions.at( current->sol[i] )->insertIntoIndex( candidates_subsol );
447  }
448  }
449 
450  switch ( searchMethod )
451  {
452  //case branch_and_bound :
453  //delta = current->branch_and_bound_search();
454  // break;
455 
456  case POPMUSIC_TABU :
457  delta = popmusic_tabu( current );
458  break;
459  case POPMUSIC_TABU_CHAIN :
460  delta = popmusic_tabu_chain( current );
461  break;
462  case POPMUSIC_CHAIN :
463  delta = popmusic_chain( current );
464  break;
465  default:
466  delete[] ok;
467  delete[] parts;
468  return;
469  }
470 
471  popit++;
472 
473  if ( delta > EPSILON )
474  {
475  /* Update solution */
476  for ( i = 0; i < current->borderSize; i++ )
477  {
478  ok[current->sub[i]] = false;
479  }
480 
481  for ( i = current->borderSize; i < current->subSize; i++ )
482  {
483 
484  if ( sol->s[current->sub[i]] != -1 )
485  {
486  mLabelPositions.at( sol->s[current->sub[i]] )->removeFromIndex( candidates_sol );
487  }
488 
489  sol->s[current->sub[i]] = current->sol[i];
490 
491  if ( current->sol[i] != -1 )
492  {
493  mLabelPositions.at( current->sol[i] )->insertIntoIndex( candidates_sol );
494  }
495 
496  ok[current->sub[i]] = false;
497  }
498  }
499  else // not improved
500  {
501  ok[seed] = true;
502  }
503  }
504 
505  solution_cost();
506 
507  delete[] labelPositionCost;
508  delete[] nbOlap;
509 
510  for ( i = 0; i < nbft; i++ )
511  {
512  delete[] parts[i]->sub;
513  delete[] parts[i]->sol;
514  delete parts[i];
515  }
516  delete[] parts;
517 
518  delete[] ok;
519 }
520 
521 typedef struct
522 {
523  QLinkedList<int> *queue;
524  int *isIn = nullptr;
525  LabelPosition *lp = nullptr;
527 
528 bool subPartCallback( LabelPosition *lp, void *ctx )
529 {
530  SubPartContext *context = reinterpret_cast< SubPartContext * >( ctx );
531  int *isIn = context->isIn;
532  QLinkedList<int> *queue = context->queue;
533 
534 
535  int id = lp->getProblemFeatureId();
536  if ( !isIn[id] && lp->isInConflict( context->lp ) )
537  {
538  queue->append( id );
539  isIn[id] = 1;
540  }
541 
542  return true;
543 }
544 
545 /* Select a sub part, expected size of r, from seed */
546 SubPart *Problem::subPart( int r, int featseed, int *isIn )
547 {
548  QLinkedList<int> *queue = new QLinkedList<int>;
549  QLinkedList<int> *ri = new QLinkedList<int>;
550 
551  int *sub = nullptr;
552 
553  int id;
554  int featS;
555  int p;
556  int i;
557 
558  int n = 0;
559  int nb = 0;
560 
561  double amin[2];
562  double amax[2];
563 
564  SubPartContext context;
565  context.queue = queue;
566  context.isIn = isIn;
567 
568  queue->append( featseed );
569  isIn[featseed] = 1;
570 
571  LabelPosition *lp = nullptr;
572 
573  while ( ri->size() < r && !queue->isEmpty() )
574  {
575  id = queue->takeFirst();
576  ri->append( id );
577 
578  featS = featStartId[id];
579  p = featNbLp[id];
580 
581  for ( i = featS; i < featS + p; i++ ) // foreach candidat of feature 'id'
582  {
583  lp = mLabelPositions.at( i );
584 
585  lp->getBoundingBox( amin, amax );
586 
587  context.lp = lp;
588  candidates->Search( amin, amax, subPartCallback, reinterpret_cast< void * >( &context ) );
589  }
590  }
591 
592  nb = queue->size();
593  n = ri->size();
594 
595  sub = new int[n + nb];
596 
597  i = 0;
598 
599  while ( !queue->isEmpty() )
600  {
601  sub[i] = queue->takeFirst();
602  isIn[sub[i]] = 0;
603  i++;
604  }
605 
606  while ( !ri->isEmpty() )
607  {
608  sub[i] = ri->takeFirst();
609  isIn[sub[i]] = 0;
610  i++;
611  }
612 
613  delete queue;
614  delete ri;
615 
616  SubPart *subPart = new SubPart();
617 
618  subPart->probSize = n;
619  subPart->borderSize = nb;
620  subPart->subSize = n + nb;
621  subPart->sub = sub;
622  subPart->sol = new int [subPart->subSize];
623  subPart->seed = featseed;
624  return subPart;
625 }
626 
627 double Problem::compute_feature_cost( SubPart *part, int feat_id, int label_id, int *nbOverlap )
628 {
629  double cost;
630  *nbOverlap = 0;
631 
633  context.inactiveCost = inactiveCost;
634  context.nbOv = nbOverlap;
635  context.cost = &cost;
636 
637  double amin[2];
638  double amax[2];
639  LabelPosition *lp = nullptr;
640 
641  cost = 0.0;
642 
643  if ( label_id >= 0 ) // is the feature displayed ?
644  {
645  lp = mLabelPositions.at( label_id );
646 
647  lp->getBoundingBox( amin, amax );
648 
649  context.lp = lp;
650  candidates_subsol->Search( amin, amax, LabelPosition::countFullOverlapCallback, reinterpret_cast< void * >( &context ) );
651 
652  cost += lp->cost();
653  }
654  else
655  {
656  cost = inactiveCost[part->sub[feat_id]];
657  //(*nbOverlap)++;
658  }
659 
660  return cost;
661 
662 }
663 
664 double Problem::compute_subsolution_cost( SubPart *part, int *s, int *nbOverlap )
665 {
666  int i;
667  double cost = 0.0;
668  int nbO = 0;
669 
670  *nbOverlap = 0;
671 
672  for ( i = 0; i < part->subSize; i++ )
673  {
674  cost += compute_feature_cost( part, i, s[i], &nbO );
675  *nbOverlap += nbO;
676  }
677 
678  return cost;
679 }
680 
681 
682 
683 typedef struct _Triple
684 {
685  int feat_id;
686  int label_id;
687  double cost;
689 } Triple;
690 
691 
692 bool decreaseCost( void *tl, void *tr )
693 {
694  return ( reinterpret_cast< Triple * >( tl ) )->cost < ( reinterpret_cast< Triple * >( tr ) )->cost;
695 }
696 
697 inline void actualizeTabuCandidateList( int m, int iteration, int nbOverlap, int *candidateListSize,
698  double candidateBaseFactor, double *candidateFactor,
699  int minCandidateListSize, double reductionFactor,
700  int minTabuTSize, double tabuFactor, int *tenure, int n )
701 {
702 
703  if ( *candidateFactor > candidateBaseFactor )
704  *candidateFactor /= reductionFactor;
705 
706  if ( iteration % m == 0 )
707  {
708  *tenure = minTabuTSize + static_cast< int >( tabuFactor * nbOverlap );
709  *candidateListSize = minCandidateListSize + static_cast< int >( *candidateFactor * nbOverlap );
710 
711  if ( *candidateListSize > n )
712  *candidateListSize = n;
713  }
714 
715 }
716 
717 
718 inline void actualizeCandidateList( int nbOverlap, int *candidateListSize, double,
719  double *candidateFactor, int minCandidateListSize, double growingFactor, int n )
720 {
721  if ( *candidateListSize < n )
722  *candidateFactor = *candidateFactor * growingFactor;
723  *candidateListSize = minCandidateListSize + static_cast< int >( *candidateFactor * nbOverlap );
724 
725  if ( *candidateListSize > n )
726  *candidateListSize = n;
727 }
728 
729 
730 
731 
732 typedef struct
733 {
734  LabelPosition *lp = nullptr;
735  Triple **candidates = nullptr;
736  double *labelPositionCost = nullptr;
737  int *nbOlap = nullptr;
738  double diff_cost;
739  int *featWrap = nullptr;
740  int *sol = nullptr;
742 } UpdateContext;
743 
744 bool updateCandidatesCost( LabelPosition *lp, void *context )
745 {
746  UpdateContext *ctx = reinterpret_cast< UpdateContext * >( context );
747 
748  if ( ctx->lp->isInConflict( lp ) )
749  {
750  ctx->labelPositionCost[lp->getId()] += ctx->diff_cost;
751  if ( ctx->diff_cost > 0 )
752  ctx->nbOlap[lp->getId()]++;
753  else
754  ctx->nbOlap[lp->getId()]--;
755 
756  int feat_id = ctx->featWrap[ctx->lp->getProblemFeatureId()];
757  int feat_id2;
758  if ( feat_id >= 0 && ctx->sol[feat_id] == lp->getId() ) // this label is in use
759  {
760  if ( ( feat_id2 = feat_id - ctx->borderSize ) >= 0 )
761  {
762  ctx->candidates[feat_id2]->cost += ctx->diff_cost;
763  ctx->candidates[feat_id2]->nbOverlap--;
764  }
765  }
766  }
767  return true;
768 }
769 
770 
771 
772 
774 {
775  int probSize = part->probSize;
776  int borderSize = part->borderSize;
777  int subSize = part->subSize;
778  int *sub = part->sub;
779  int *sol = part->sol;
780 
781  Triple **candidateList = new Triple*[probSize];
782  Triple **candidateListUnsorted = new Triple*[probSize];
783 
784  int *best_sol = new int[subSize];
785 
786  double cur_cost;
787  double best_cost;
788  double initial_cost;
789 
790  int *tabu_list = new int[probSize];
791 
792  int i;
793  int j;
794 
795  int itwImp;
796  int it = 0;
797  int max_it;
798  int stop_it;
799 
800  double delta;
801  double delta_min;
802  bool authorized;
803 
804  int feat_id;
805  int feat_sub_id;
806  int label_id;
807  int p;
808 
809  int choosed_feat;
810  int choosed_label;
811  int candidateId;
812 
813  int nbOverlap = 0;
814  //int nbOverlapLabel;
815 
816 
817  int tenure = 10; //
818  int m = 50; // m [10;50]
819 
820  int minTabuTSize = 9; // min_t [2;10]
821  double tabuFactor = 0.5; // p_t [0.1;0.8]
822 
823  int minCandidateListSize = 18; // min_c [2;20]
824 
825  double candidateBaseFactor = 0.73; // p_base [0.1;0.8]
826 
827  double growingFactor = 15; // fa [5;20]
828  double reductionFactor = 1.3; // f_r [1.1;1.5]
829 
830  int candidateListSize = minCandidateListSize;
831  double candidateFactor = candidateBaseFactor;
832 
833 
834  int first_lp;
835 
836  //double EPSILON = 0.000001;
837  max_it = probSize * pal->tabuMaxIt;
838  itwImp = probSize * pal->tabuMinIt;
839  stop_it = itwImp;
840 
841  cur_cost = 0.0;
842  nbOverlap = 0;
843 
844 
845  int lp;
846  for ( i = 0; i < subSize; i++ )
847  featWrap[sub[i]] = i;
848 
849  for ( i = 0; i < subSize; i++ )
850  {
851  j = featStartId[sub[i]];
852  for ( lp = 0; lp < featNbLp[sub[i]]; lp++ )
853  {
854  it = j + lp;
855  labelPositionCost[it] = compute_feature_cost( part, i, it, & ( nbOlap[it] ) );
856  }
857  }
858 
859  first_lp = ( displayAll ? 0 : -1 );
860  for ( i = 0; i < probSize; i++ )
861  {
862 
863  tabu_list[i] = -1; // nothing is tabu
864 
865  candidateList[i] = new Triple();
866  candidateList[i]->feat_id = i + borderSize;
867  candidateList[i]->label_id = sol[i + borderSize];
868 
869  candidateListUnsorted[i] = candidateList[i];
870 
871  if ( sol[i + borderSize] >= 0 )
872  {
873  j = sol[i + borderSize];
874  candidateList[i]->cost = labelPositionCost[j];
875  candidateList[i]->nbOverlap = nbOlap[j];
876  }
877  else
878  {
879  candidateList[i]->cost = inactiveCost[sub[i + borderSize]];
880  candidateList[i]->nbOverlap = 1;
881  }
882 
883  }
884 
885 
886  for ( i = 0; i < subSize; i++ )
887  {
888  if ( sol[i] == -1 )
889  {
890  cur_cost += inactiveCost[sub[i]];
891  }
892  else
893  {
894  nbOverlap += nbOlap[sol[i]];
895  cur_cost += labelPositionCost[sol[i]];
896  }
897  }
898 
899  Util::sort( reinterpret_cast< void ** >( candidateList ), probSize, decreaseCost );
900 
901  best_cost = cur_cost;
902  initial_cost = cur_cost;
903  memcpy( best_sol, sol, sizeof( int ) * ( subSize ) );
904 
905  // START TABU
906 
907  it = 0;
908  while ( it < stop_it && best_cost >= EPSILON )
909  {
910  actualizeTabuCandidateList( m, it, nbOverlap, &candidateListSize, candidateBaseFactor, &candidateFactor, minCandidateListSize, reductionFactor, minTabuTSize, tabuFactor, &tenure, probSize );
911  delta_min = std::numeric_limits<double>::max();
912  choosed_feat = -1;
913  choosed_label = -2;
914  candidateId = -1;
915 
916  // foreach retained Candidate
917  for ( i = 0; i < candidateListSize; i++ )
918  {
919  feat_id = candidateList[i]->feat_id;
920  feat_sub_id = sub[feat_id];
921  label_id = candidateList[i]->label_id;
922 
923  int oldPos = ( label_id < 0 ? -1 : label_id - featStartId[feat_sub_id] );
924 
925 
926  p = featNbLp[feat_sub_id];
927 
928  /* label -1 means inactive feature */
929  // foreach labelposition of feature minus the one in the solution
930  for ( j = first_lp; j < p; j++ )
931  {
932  if ( j != oldPos )
933  {
934 
935  if ( sol[feat_id] < 0 )
936  {
937  delta = -inactiveCost[feat_sub_id];
938  }
939  else
940  {
941  delta = -labelPositionCost[sol[feat_id]];
942  delta -= nbOlap[sol[feat_id]] * ( inactiveCost[feat_sub_id] + mLabelPositions.at( label_id )->cost() );
943  }
944 
945  if ( j >= 0 )
946  {
947  delta += labelPositionCost[featStartId[feat_sub_id] + j];
948  delta += nbOlap[featStartId[feat_sub_id] + j] * ( inactiveCost[feat_sub_id] + mLabelPositions.at( featStartId[feat_sub_id] + j )->cost() );
949  }
950  else
951  {
952  delta += inactiveCost[feat_sub_id];
953  }
954 
955  // move is authorized wether the feat isn't taboo or whether the move give a new best solution
956  authorized = ( tabu_list[feat_id - borderSize] <= it ) || ( cur_cost + delta < best_cost );
957 
958  if ( delta < delta_min && authorized )
959  {
960  choosed_feat = feat_id;
961 
962  if ( j == -1 )
963  choosed_label = -1;
964  else
965  choosed_label = featStartId[feat_sub_id] + j;
966 
967  delta_min = delta;
968  candidateId = i;
969  }
970  }
971  }
972  }
973 
974  // if a modification has been retained
975  if ( choosed_feat >= 0 )
976  {
977  // update the solution and update tabu list
978  int old_label = sol[choosed_feat];
979 
980  tabu_list[choosed_feat - borderSize] = it + tenure;
981  sol[choosed_feat] = choosed_label;
982  candidateList[candidateId]->label_id = choosed_label;
983 
984  if ( old_label != -1 )
985  mLabelPositions.at( old_label )->removeFromIndex( candidates_subsol );
986 
987  /* re-compute all labelpositioncost that overlap with old an new label */
988  double local_inactive = inactiveCost[sub[choosed_feat]];
989 
990  if ( choosed_label != -1 )
991  {
992  candidateList[candidateId]->cost = labelPositionCost[choosed_label];
993  candidateList[candidateId]->nbOverlap = nbOlap[choosed_label];
994  }
995  else
996  {
997  candidateList[candidateId]->cost = local_inactive;
998  candidateList[candidateId]->nbOverlap = 1;
999  }
1000 
1001  cur_cost += delta_min;
1002 
1003  double amin[2];
1004  double amax[2];
1005  LabelPosition *lp = nullptr;
1006 
1007  UpdateContext context;
1008 
1009  context.candidates = candidateListUnsorted;
1010  context.labelPositionCost = labelPositionCost;
1011  context.nbOlap = nbOlap;
1012  context.featWrap = featWrap;
1013  context.sol = sol;
1014  context.borderSize = borderSize;
1015 
1016  if ( old_label >= 0 )
1017  {
1018  lp = mLabelPositions.at( old_label );
1019 
1020  lp->getBoundingBox( amin, amax );
1021 
1022  context.diff_cost = -local_inactive - lp->cost();
1023  context.lp = lp;
1024 
1025  candidates->Search( amin, amax, updateCandidatesCost, &context );
1026  }
1027 
1028  if ( choosed_label >= 0 )
1029  {
1030  lp = mLabelPositions.at( choosed_label );
1031 
1032  lp->getBoundingBox( amin, amax );
1033 
1034  context.diff_cost = local_inactive + lp->cost();
1035  context.lp = lp;
1036 
1037 
1038  candidates->Search( amin, amax, updateCandidatesCost, &context );
1039 
1040  lp->insertIntoIndex( candidates_subsol );
1041  }
1042 
1043  Util::sort( reinterpret_cast< void ** >( candidateList ), probSize, decreaseCost );
1044 
1045  if ( best_cost - cur_cost > EPSILON ) // new best sol
1046  {
1047  best_cost = cur_cost;
1048  memcpy( best_sol, sol, sizeof( int ) * ( subSize ) );
1049  stop_it = it + itwImp;
1050  if ( stop_it > max_it )
1051  stop_it = max_it;
1052  }
1053  }
1054  else
1055  {
1056  /* no feature was selected : increase candidate list size*/
1057  actualizeCandidateList( nbOverlap, &candidateListSize, candidateBaseFactor,
1058  &candidateFactor, minCandidateListSize, growingFactor, probSize );
1059  }
1060  it++;
1061  }
1062 
1063  memcpy( sol, best_sol, sizeof( int ) * ( subSize ) );
1064 
1065  for ( i = 0; i < subSize; i++ )
1066  featWrap[sub[i]] = -1;
1067 
1068  for ( i = 0; i < probSize; i++ )
1069  delete candidateList[i];
1070 
1071  delete[] candidateList;
1072  delete[] candidateListUnsorted;
1073  delete[] best_sol;
1074  delete[] tabu_list;
1075 
1076  /* Returns delta */
1077  return initial_cost - best_cost;
1078 }
1079 
1080 
1081 
1082 
1083 
1084 typedef struct
1085 {
1086  LabelPosition *lp = nullptr;
1087  int *tmpsol = nullptr;
1088  int *featWrap = nullptr;
1089  int *feat = nullptr;
1091  QLinkedList<ElemTrans *> *currentChain;
1092  QLinkedList<int> *conflicts;
1093  double *delta_tmp = nullptr;
1094  double *inactiveCost = nullptr;
1095 
1096 } ChainContext;
1097 
1098 
1099 bool chainCallback( LabelPosition *lp, void *context )
1100 {
1101  ChainContext *ctx = reinterpret_cast< ChainContext * >( context );
1102 
1103  if ( lp->isInConflict( ctx->lp ) )
1104  {
1105  int feat, rfeat;
1106  bool sub = nullptr != ctx->featWrap;
1107 
1108  feat = lp->getProblemFeatureId();
1109  if ( sub )
1110  {
1111  rfeat = feat;
1112  feat = ctx->featWrap[feat];
1113  }
1114  else
1115  rfeat = feat;
1116 
1117  if ( feat >= 0 && ctx->tmpsol[feat] == lp->getId() )
1118  {
1119  if ( sub && feat < ctx->borderSize )
1120  {
1121  throw - 2;
1122  }
1123  }
1124 
1125  // is there any cycles ?
1126  QLinkedList< ElemTrans * >::iterator cur;
1127  for ( cur = ctx->currentChain->begin(); cur != ctx->currentChain->end(); ++cur )
1128  {
1129  if ( ( *cur )->feat == feat )
1130  {
1131  throw - 1;
1132  }
1133  }
1134 
1135  if ( !ctx->conflicts->contains( feat ) )
1136  {
1137  ctx->conflicts->append( feat );
1138  *ctx->delta_tmp += lp->cost() + ctx->inactiveCost[rfeat];
1139  }
1140  }
1141  return true;
1142 }
1143 
1144 inline Chain *Problem::chain( SubPart *part, int seed )
1145 {
1146 
1147  int i;
1148  int j;
1149 
1150  int lid;
1151 
1152  //int probSize = part->probSize;
1153  int borderSize = part->borderSize;
1154  int subSize = part->subSize;
1155  int *sub = part->sub;
1156  int *sol = part->sol;
1157  int subseed;
1158 
1159  double delta;
1160  double delta_min;
1161  double delta_best = std::numeric_limits<double>::max();
1162  double delta_tmp;
1163 
1164  int next_seed;
1165  int retainedLabel;
1166  Chain *retainedChain = nullptr;
1167 
1168  int max_degree = pal->ejChainDeg;
1169 
1170  int seedNbLp;
1171 
1172  QLinkedList<ElemTrans *> *currentChain = new QLinkedList<ElemTrans *>;
1173  QLinkedList<int> *conflicts = new QLinkedList<int>;
1174 
1175  int *tmpsol = new int[subSize];
1176  memcpy( tmpsol, sol, sizeof( int ) *subSize );
1177 
1178  LabelPosition *lp = nullptr;
1179  double amin[2];
1180  double amax[2];
1181 
1182  ChainContext context;
1183  context.featWrap = featWrap;
1184  context.borderSize = borderSize;
1185  context.tmpsol = tmpsol;
1186  context.inactiveCost = inactiveCost;
1187  context.feat = nullptr;
1188  context.currentChain = currentChain;
1189  context.conflicts = conflicts;
1190  context.delta_tmp = &delta_tmp;
1191 
1192  delta = 0;
1193  while ( seed != -1 )
1194  {
1195  subseed = sub[seed];
1196  seedNbLp = featNbLp[subseed];
1197  delta_min = std::numeric_limits<double>::max();
1198  next_seed = -1;
1199  retainedLabel = -2;
1200 
1201 
1202  if ( tmpsol[seed] == -1 )
1203  delta -= inactiveCost[subseed];
1204  else
1205  delta -= mLabelPositions.at( tmpsol[seed] )->cost();
1206 
1207  // TODO modify to handle displayAll param
1208  for ( i = -1; i < seedNbLp; i++ )
1209  {
1210  try
1211  {
1212  // Skip active label !
1213  if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[subseed] != tmpsol[seed] )
1214  {
1215  if ( i != -1 )
1216  {
1217  lid = featStartId[subseed] + i;
1218  delta_tmp = delta;
1219 
1220  lp = mLabelPositions.at( lid );
1221 
1222  // evaluate conflicts graph in solution after moving seed's label
1223  lp->getBoundingBox( amin, amax );
1224 
1225  context.lp = lp;
1226 
1227  // search ative conflicts and count them
1228  candidates_subsol->Search( amin, amax, chainCallback, reinterpret_cast< void * >( &context ) );
1229 
1230  // no conflict -> end of chain
1231  if ( conflicts->isEmpty() )
1232  {
1233  if ( !retainedChain || delta + lp->cost() < delta_best )
1234  {
1235 
1236  if ( retainedChain )
1237  {
1238  delete[] retainedChain->label;
1239  delete[] retainedChain->feat;
1240  }
1241  else
1242  {
1243  retainedChain = new Chain(); // HERE
1244  }
1245 
1246  delta_best = delta + lp->cost();
1247 
1248  retainedChain->degree = currentChain->size() + 1;
1249  retainedChain->feat = new int[retainedChain->degree]; // HERE
1250  retainedChain->label = new int[retainedChain->degree]; // HERE
1251  QLinkedList< ElemTrans * >::iterator current = currentChain->begin();
1252  ElemTrans *move = nullptr;
1253  j = 0;
1254  while ( current != currentChain->end() )
1255  {
1256  move = *current;
1257  retainedChain->feat[j] = move->feat;
1258  retainedChain->label[j] = move->new_label;
1259  ++current;
1260  ++j;
1261  }
1262  retainedChain->feat[j] = seed;
1263  retainedChain->label[j] = lid;
1264  retainedChain->delta = delta + mLabelPositions.at( retainedChain->label[j] )->cost();
1265  }
1266  }
1267 
1268  // another feature can be ejected
1269  else if ( conflicts->size() == 1 )
1270  {
1271  if ( delta_tmp < delta_min )
1272  {
1273  delta_min = delta_tmp;
1274  retainedLabel = lid;
1275  next_seed = conflicts->takeFirst();
1276  }
1277  else
1278  {
1279  conflicts->takeFirst();
1280  }
1281  }
1282  else
1283  {
1284 
1285  // A lot of conflict : make them inactive and store chain
1286  Chain *newChain = new Chain(); // HERE
1287  newChain->degree = currentChain->size() + 1 + conflicts->size();
1288  newChain->feat = new int[newChain->degree]; // HERE
1289  newChain->label = new int[newChain->degree]; // HERE
1290  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1291  ElemTrans *move = nullptr;
1292  j = 0;
1293  while ( current != currentChain->end() )
1294  {
1295  move = *current;
1296  newChain->feat[j] = move->feat;
1297  newChain->label[j] = move->new_label;
1298  ++current;
1299  ++j;
1300  }
1301 
1302  newChain->feat[j] = seed;
1303  newChain->label[j] = lid;
1304  newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
1305  j++;
1306 
1307 
1308  while ( !conflicts->isEmpty() )
1309  {
1310  int ftid = conflicts->takeFirst();
1311  newChain->feat[j] = ftid;
1312  newChain->label[j] = -1;
1313  newChain->delta += inactiveCost[sub[ftid]];
1314  j++;
1315  }
1316 
1317  if ( newChain->delta < delta_best )
1318  {
1319  if ( retainedChain )
1320  delete_chain( retainedChain );
1321 
1322  delta_best = newChain->delta;
1323  retainedChain = newChain;
1324  }
1325  else
1326  {
1327  delete_chain( newChain );
1328  }
1329  }
1330  }
1331  else // Current label == -1 end of chain ...
1332  {
1333  if ( !retainedChain || delta + inactiveCost[subseed] < delta_best )
1334  {
1335  if ( retainedChain )
1336  {
1337  delete[] retainedChain->label;
1338  delete[] retainedChain->feat;
1339  }
1340  else
1341  retainedChain = new Chain(); // HERE
1342 
1343  delta_best = delta + inactiveCost[subseed];
1344 
1345  retainedChain->degree = currentChain->size() + 1;
1346  retainedChain->feat = new int[retainedChain->degree]; // HERE
1347  retainedChain->label = new int[retainedChain->degree]; // HERE
1348  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1349  ElemTrans *move = nullptr;
1350  j = 0;
1351  while ( current != currentChain->end() )
1352  {
1353  move = *current;
1354  retainedChain->feat[j] = move->feat;
1355  retainedChain->label[j] = move->new_label;
1356  ++current;
1357  ++j;
1358  }
1359  retainedChain->feat[j] = seed;
1360  retainedChain->label[j] = -1;
1361  retainedChain->delta = delta + inactiveCost[subseed];
1362  }
1363  }
1364  }
1365  }
1366  catch ( int i )
1367  {
1368  Q_UNUSED( i );
1369  conflicts->clear();
1370  }
1371  } // end foreach labelposition
1372 
1373  if ( next_seed == -1 )
1374  {
1375  seed = -1;
1376  }
1377  else if ( currentChain->size() > max_degree )
1378  {
1379  seed = -1;
1380  }
1381  else
1382  {
1383  ElemTrans *et = new ElemTrans();
1384  et->feat = seed;
1385  et->old_label = tmpsol[seed];
1386  et->new_label = retainedLabel;
1387  currentChain->append( et );
1388 
1389  if ( et->old_label != -1 )
1390  {
1391  mLabelPositions.at( et->old_label )->removeFromIndex( candidates_subsol );
1392  }
1393 
1394  if ( et->new_label != -1 )
1395  {
1396  mLabelPositions.at( et->new_label )->insertIntoIndex( candidates_subsol );
1397  }
1398 
1399  tmpsol[seed] = retainedLabel;
1400  delta += mLabelPositions.at( retainedLabel )->cost();
1401  seed = next_seed;
1402  }
1403  }
1404 
1405  while ( !currentChain->isEmpty() )
1406  {
1407  ElemTrans *et = currentChain->takeFirst();
1408 
1409  if ( et->new_label != -1 )
1410  {
1411  mLabelPositions.at( et->new_label )->removeFromIndex( candidates_subsol );
1412  }
1413 
1414  if ( et->old_label != -1 )
1415  {
1416  mLabelPositions.at( et->old_label )->insertIntoIndex( candidates_subsol );
1417  }
1418 
1419  delete et;
1420  }
1421  delete currentChain;
1422 
1423  delete[] tmpsol;
1424  delete conflicts;
1425 
1426 
1427  return retainedChain;
1428 }
1429 
1430 
1431 inline Chain *Problem::chain( int seed )
1432 {
1433 
1434  int i;
1435  int j;
1436 
1437  int lid;
1438 
1439  double delta;
1440  double delta_min;
1441  double delta_best = std::numeric_limits<double>::max();
1442  double delta_tmp;
1443 
1444  int next_seed;
1445  int retainedLabel;
1446  Chain *retainedChain = nullptr;
1447 
1448  int max_degree = pal->ejChainDeg;
1449 
1450  int seedNbLp;
1451 
1452  QLinkedList<ElemTrans *> *currentChain = new QLinkedList<ElemTrans *>;
1453  QLinkedList<int> *conflicts = new QLinkedList<int>;
1454 
1455  int *tmpsol = new int[nbft];
1456  memcpy( tmpsol, sol->s, sizeof( int ) *nbft );
1457 
1458  LabelPosition *lp = nullptr;
1459  double amin[2];
1460  double amax[2];
1461 
1462  ChainContext context;
1463  context.featWrap = nullptr;
1464  context.borderSize = 0;
1465  context.tmpsol = tmpsol;
1466  context.inactiveCost = inactiveCost;
1467  context.feat = nullptr;
1468  context.currentChain = currentChain;
1469  context.conflicts = conflicts;
1470  context.delta_tmp = &delta_tmp;
1471 
1472  delta = 0;
1473  while ( seed != -1 )
1474  {
1475  seedNbLp = featNbLp[seed];
1476  delta_min = std::numeric_limits<double>::max();
1477 
1478  next_seed = -1;
1479  retainedLabel = -2;
1480 
1481  // sol[seed] is ejected
1482  if ( tmpsol[seed] == -1 )
1483  delta -= inactiveCost[seed];
1484  else
1485  delta -= mLabelPositions.at( tmpsol[seed] )->cost();
1486 
1487  for ( i = -1; i < seedNbLp; i++ )
1488  {
1489  try
1490  {
1491  // Skip active label !
1492  if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[seed] != tmpsol[seed] )
1493  {
1494  if ( i != -1 ) // new_label
1495  {
1496  lid = featStartId[seed] + i;
1497  delta_tmp = delta;
1498 
1499  lp = mLabelPositions.at( lid );
1500 
1501  // evaluate conflicts graph in solution after moving seed's label
1502  lp->getBoundingBox( amin, amax );
1503 
1504  context.lp = lp;
1505 
1506  candidates_sol->Search( amin, amax, chainCallback, reinterpret_cast< void * >( &context ) );
1507 
1508  // no conflict -> end of chain
1509  if ( conflicts->isEmpty() )
1510  {
1511  if ( !retainedChain || delta + lp->cost() < delta_best )
1512  {
1513  if ( retainedChain )
1514  {
1515  delete[] retainedChain->label;
1516  delete[] retainedChain->feat;
1517  }
1518  else
1519  {
1520  retainedChain = new Chain();
1521  }
1522 
1523  delta_best = delta + lp->cost();
1524 
1525  retainedChain->degree = currentChain->size() + 1;
1526  retainedChain->feat = new int[retainedChain->degree];
1527  retainedChain->label = new int[retainedChain->degree];
1528  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1529  ElemTrans *move = nullptr;
1530  j = 0;
1531  while ( current != currentChain->end() )
1532  {
1533  move = *current;
1534  retainedChain->feat[j] = move->feat;
1535  retainedChain->label[j] = move->new_label;
1536  ++current;
1537  ++j;
1538  }
1539  retainedChain->feat[j] = seed;
1540  retainedChain->label[j] = lid;
1541  retainedChain->delta = delta + lp->cost();
1542  }
1543  }
1544 
1545  // another feature can be ejected
1546  else if ( conflicts->size() == 1 )
1547  {
1548  if ( delta_tmp < delta_min )
1549  {
1550  delta_min = delta_tmp;
1551  retainedLabel = lid;
1552  next_seed = conflicts->takeFirst();
1553  }
1554  else
1555  {
1556  conflicts->takeFirst();
1557  }
1558  }
1559  else
1560  {
1561 
1562  // A lot of conflict : make them inactive and store chain
1563  Chain *newChain = new Chain();
1564  newChain->degree = currentChain->size() + 1 + conflicts->size();
1565  newChain->feat = new int[newChain->degree];
1566  newChain->label = new int[newChain->degree];
1567  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1568  ElemTrans *move = nullptr;
1569  j = 0;
1570 
1571  while ( current != currentChain->end() )
1572  {
1573  move = *current;
1574  newChain->feat[j] = move->feat;
1575  newChain->label[j] = move->new_label;
1576  ++current;
1577  ++j;
1578  }
1579 
1580  // add the current candidates into the chain
1581  newChain->feat[j] = seed;
1582  newChain->label[j] = lid;
1583  newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
1584  j++;
1585 
1586  // hide all conflictual candidates
1587  while ( !conflicts->isEmpty() )
1588  {
1589  int ftid = conflicts->takeFirst();
1590  newChain->feat[j] = ftid;
1591  newChain->label[j] = -1;
1592  newChain->delta += inactiveCost[ftid];
1593  j++;
1594  }
1595 
1596  if ( newChain->delta < delta_best )
1597  {
1598  if ( retainedChain )
1599  delete_chain( retainedChain );
1600 
1601  delta_best = newChain->delta;
1602  retainedChain = newChain;
1603  }
1604  else
1605  {
1606  delete_chain( newChain );
1607  }
1608  }
1609 
1610  }
1611  else // Current label == -1 end of chain ...
1612  {
1613  if ( !retainedChain || delta + inactiveCost[seed] < delta_best )
1614  {
1615  if ( retainedChain )
1616  {
1617  delete[] retainedChain->label;
1618  delete[] retainedChain->feat;
1619  }
1620  else
1621  retainedChain = new Chain();
1622 
1623  delta_best = delta + inactiveCost[seed];
1624 
1625  retainedChain->degree = currentChain->size() + 1;
1626  retainedChain->feat = new int[retainedChain->degree];
1627  retainedChain->label = new int[retainedChain->degree];
1628  QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1629  ElemTrans *move = nullptr;
1630  j = 0;
1631  while ( current != currentChain->end() )
1632  {
1633  move = *current;
1634  retainedChain->feat[j] = move->feat;
1635  retainedChain->label[j] = move->new_label;
1636  ++current;
1637  ++j;
1638  }
1639  retainedChain->feat[j] = seed;
1640  retainedChain->label[j] = -1;
1641  retainedChain->delta = delta + inactiveCost[seed];
1642  }
1643  }
1644  }
1645  }
1646  catch ( int i )
1647  {
1648  Q_UNUSED( i );
1649  conflicts->clear();
1650  }
1651  } // end foreach labelposition
1652 
1653  if ( next_seed == -1 )
1654  {
1655  seed = -1;
1656  }
1657  else if ( currentChain->size() > max_degree )
1658  {
1659  // Max degree reached
1660  seed = -1;
1661  }
1662  else
1663  {
1664  ElemTrans *et = new ElemTrans();
1665  et->feat = seed;
1666  et->old_label = tmpsol[seed];
1667  et->new_label = retainedLabel;
1668  currentChain->append( et );
1669 
1670  if ( et->old_label != -1 )
1671  {
1672  mLabelPositions.at( et->old_label )->removeFromIndex( candidates_sol );
1673  }
1674 
1675  if ( et->new_label != -1 )
1676  {
1677  mLabelPositions.at( et->new_label )->insertIntoIndex( candidates_sol );
1678  }
1679 
1680 
1681  tmpsol[seed] = retainedLabel;
1682  delta += mLabelPositions.at( retainedLabel )->cost();
1683  seed = next_seed;
1684  }
1685  }
1686 
1687 
1688  while ( !currentChain->isEmpty() )
1689  {
1690  ElemTrans *et = currentChain->takeFirst();
1691 
1692  if ( et->new_label != -1 )
1693  {
1694  mLabelPositions.at( et->new_label )->removeFromIndex( candidates_sol );
1695  }
1696 
1697  if ( et->old_label != -1 )
1698  {
1699  mLabelPositions.at( et->old_label )->insertIntoIndex( candidates_sol );
1700  }
1701 
1702  delete et;
1703  }
1704  delete currentChain;
1705 
1706  delete[] tmpsol;
1707  delete conflicts;
1708 
1709 
1710  return retainedChain;
1711 }
1712 
1714 {
1715  int i;
1716  //int j;
1717 
1718  int probSize = part->probSize;
1719  int borderSize = part->borderSize;
1720  int subSize = part->subSize;
1721  int *sub = part->sub;
1722  int *sol = part->sol;
1723 
1724  int *best_sol = new int[subSize];
1725 
1726  for ( i = 0; i < subSize; i++ )
1727  {
1728  featWrap[sub[i]] = i;
1729  best_sol[i] = sol[i];
1730  }
1731 
1732  double initial_cost;
1733  double cur_cost = 0;
1734  double best_cost = 0;
1735 
1736  // int nbOverlap = 0;
1737 
1738  int seed;
1739 
1740  int featOv;
1741 
1742  int lid;
1743  int fid;
1744 
1745  int *tabu_list = new int[subSize];
1746 
1747  Chain *current_chain = nullptr;
1748 
1749  //int itC;
1750 
1751  int it;
1752  int stop_it;
1753  int maxit;
1754  int itwimp; // iteration without improvment
1755 
1756  int tenure = pal->tenure;
1757 
1758  for ( i = 0; i < subSize; i++ )
1759  {
1760  cur_cost += compute_feature_cost( part, i, sol[i], &featOv );
1761  // nbOverlap += featOv;
1762  }
1763 
1764  initial_cost = cur_cost;
1765  best_cost = cur_cost;
1766 
1767  it = 0;
1768 
1769  maxit = probSize * pal->tabuMaxIt;
1770 
1771  itwimp = probSize * pal->tabuMinIt;
1772 
1773  stop_it = itwimp;
1774 
1775  // feature on border always are tabu
1776  for ( i = 0; i < borderSize; i++ )
1777  tabu_list[i] = maxit; // border always are taboo
1778 
1779  for ( i = 0; i < probSize; i++ )
1780  tabu_list[i + borderSize] = -1; // others aren't
1781 
1782  while ( it < stop_it )
1783  {
1784  seed = ( it % probSize ) + borderSize;
1785 
1786  current_chain = chain( part, seed );
1787  if ( current_chain )
1788  {
1789 
1790  /* we accept a modification only if the seed is not tabu or
1791  * if the nmodification will generate a new best solution */
1792  if ( tabu_list[seed] < it || ( cur_cost + current_chain->delta ) - best_cost < 0.0 )
1793  {
1794 
1795  for ( i = 0; i < current_chain->degree; i++ )
1796  {
1797  fid = current_chain->feat[i];
1798  lid = current_chain->label[i];
1799 
1800  if ( sol[fid] >= 0 )
1801  {
1802  mLabelPositions.at( sol[fid] )->removeFromIndex( candidates_subsol );
1803  }
1804  sol[fid] = lid;
1805 
1806  if ( sol[fid] >= 0 )
1807  {
1808  mLabelPositions.at( lid )->insertIntoIndex( candidates_subsol );
1809  }
1810 
1811  tabu_list[fid] = it + tenure;
1812  }
1813 
1814  cur_cost += current_chain->delta;
1815 
1816  /* check if new solution is a new best solution */
1817  if ( best_cost - cur_cost > EPSILON )
1818  {
1819  best_cost = cur_cost;
1820  memcpy( best_sol, sol, sizeof( int ) *subSize );
1821 
1822  stop_it = ( it + itwimp > maxit ? maxit : it + itwimp );
1823  }
1824  }
1825  delete_chain( current_chain );
1826  }
1827  it++;
1828  }
1829 
1830  memcpy( sol, best_sol, sizeof( int ) *subSize );
1831 
1832  /*
1833  for (i=borderSize;i<subSize;i++){
1834  chain = chain (part, i);
1835  if (chain){
1836  if (chain->delta < 0.0){
1837  best_cost += chain->delta;
1838  for (j=0;j<chain->degree;j++){
1839  fid = chain->feat[j];
1840  lid = chain->label[j];
1841  sol[fid] = lid;
1842  }
1843  }
1844 
1845  delete_chain(chain);
1846  }
1847  }
1848  */
1849 
1850  for ( i = 0; i < subSize; i++ )
1851  featWrap[sub[i]] = -1;
1852 
1853  delete[] best_sol;
1854  delete[] tabu_list;
1855 
1856 
1857  return initial_cost - best_cost;
1858 }
1859 
1861 {
1862  int i;
1863 
1864  int probSize = part->probSize;
1865  int borderSize = part->borderSize;
1866  int subSize = part->subSize;
1867  int *sub = part->sub;
1868  int *sol = part->sol;
1869 
1870  int *best_sol = new int[subSize];
1871 
1872  for ( i = 0; i < subSize; i++ )
1873  {
1874  featWrap[sub[i]] = i;
1875  }
1876 
1877  double initial_cost;
1878  double cur_cost = 0;
1879  double best_cost = 0;
1880 
1881  // int nbOverlap = 0;
1882 
1883  int seed;
1884 
1885  int featOv;
1886 
1887  int lid;
1888  int fid;
1889 
1890  int *tabu_list = new int[subSize];
1891 
1892  Chain *retainedChain = nullptr;
1893  Chain *current_chain = nullptr;
1894 
1895  int itC;
1896 
1897  int it;
1898  int stop_it;
1899  int maxit;
1900  int itwimp;
1901 
1902  int tenure = pal->tenure;
1903 
1904  //int deltaIt = 0;
1905 
1906  Triple **candidates = new Triple*[probSize];
1907  Triple **candidatesUnsorted = new Triple*[probSize];
1908 
1909  for ( i = 0; i < subSize; i++ )
1910  {
1911  cur_cost += compute_feature_cost( part, i, sol[i], &featOv );
1912  // nbOverlap += featOv;
1913  }
1914 
1915  initial_cost = cur_cost;
1916  best_cost = cur_cost;
1917 
1918  it = 0;
1919 
1920  maxit = probSize * pal->tabuMaxIt;
1921 
1922  itwimp = probSize * pal->tabuMinIt;
1923 
1924  stop_it = itwimp;
1925 
1926  for ( i = 0; i < borderSize; i++ )
1927  tabu_list[i] = maxit;
1928 
1929 
1930  for ( i = 0; i < probSize; i++ )
1931  {
1932  tabu_list[i + borderSize] = -1;
1933 
1934  candidates[i] = new Triple();
1935  candidates[i]->feat_id = i + borderSize;
1936  candidatesUnsorted[i] = candidates[i];
1937 
1938  candidates[i]->cost = ( sol[i + borderSize] == -1 ? inactiveCost[i + borderSize] : mLabelPositions.at( sol[i + borderSize] )->cost() );
1939  }
1940 
1941  Util::sort( reinterpret_cast< void ** >( candidates ), probSize, decreaseCost );
1942 
1943  int candidateListSize;
1944  candidateListSize = int ( pal->candListSize * static_cast< double >( probSize ) + 0.5 );
1945 
1946  if ( candidateListSize > probSize )
1947  candidateListSize = probSize;
1948 
1949  while ( it < stop_it )
1950  {
1951  retainedChain = nullptr;
1952 
1953  for ( itC = 0; itC < candidateListSize; itC++ )
1954  {
1955  seed = candidates[itC]->feat_id;
1956 
1957  current_chain = chain( part, seed );
1958 
1959  if ( current_chain )
1960  {
1961  // seed is not taboo or chain give us a new best solution
1962  if ( tabu_list[seed] < it || ( cur_cost + current_chain->delta ) - best_cost < 0.0 )
1963  {
1964  if ( !retainedChain )
1965  {
1966  retainedChain = current_chain;
1967  }
1968  else if ( current_chain->delta - retainedChain->delta < EPSILON )
1969  {
1970  delete_chain( retainedChain );
1971  retainedChain = current_chain;
1972  }
1973  else
1974  {
1975  delete_chain( current_chain );
1976  }
1977  }
1978  else
1979  {
1980  delete_chain( current_chain );
1981  }
1982  }
1983  } // end foreach candidates
1984 
1985  if ( retainedChain /*&& retainedChain->delta <= 0*/ )
1986  {
1987  for ( i = 0; i < retainedChain->degree; i++ )
1988  {
1989  fid = retainedChain->feat[i];
1990  lid = retainedChain->label[i];
1991 
1992  if ( sol[fid] >= 0 )
1993  mLabelPositions.at( sol[fid] )->removeFromIndex( candidates_subsol );
1994 
1995  sol[fid] = lid;
1996 
1997  if ( lid >= 0 )
1998  mLabelPositions.at( lid )->insertIntoIndex( candidates_subsol );
1999 
2000  tabu_list[fid] = it + tenure;
2001  candidatesUnsorted[fid - borderSize]->cost = ( lid == -1 ? inactiveCost[sub[fid]] : mLabelPositions.at( lid )->cost() );
2002 
2003  }
2004 
2005  cur_cost += retainedChain->delta;
2006 
2007  delete_chain( retainedChain );
2008 
2009  if ( best_cost - cur_cost > EPSILON )
2010  {
2011  best_cost = cur_cost;
2012  memcpy( best_sol, sol, sizeof( int ) * subSize );
2013 
2014  stop_it = ( it + itwimp > maxit ? maxit : it + itwimp );
2015  }
2016  Util::sort( reinterpret_cast< void ** >( candidates ), probSize, decreaseCost );
2017  }
2018  it++;
2019  }
2020 
2021  memcpy( sol, best_sol, sizeof( int ) *subSize );
2022 
2023  for ( i = 0; i < probSize; i++ )
2024  delete candidates[i];
2025 
2026  delete[] candidates;
2027  delete[] candidatesUnsorted;
2028 
2029  for ( i = 0; i < subSize; i++ )
2030  featWrap[sub[i]] = -1;
2031 
2032  delete[] best_sol;
2033  delete[] tabu_list;
2034 
2035 
2036  return initial_cost - best_cost;
2037 }
2038 
2039 bool checkCallback( LabelPosition *lp, void *ctx )
2040 {
2041  QLinkedList<LabelPosition *> *list = reinterpret_cast< QLinkedList<LabelPosition *>* >( ctx );
2042  list->append( lp );
2043 
2044  return true;
2045 }
2046 
2047 
2048 void Problem::check_solution()
2049 {
2050  int *solution = new int[nbft];
2051 
2052  double amin[2];
2053  double amax[2];
2054 
2055  amin[0] = bbox[0];
2056  amin[1] = bbox[1];
2057  amax[0] = bbox[2];
2058  amax[1] = bbox[3];
2059 
2060  QLinkedList<LabelPosition *> *list = new QLinkedList<LabelPosition *>;
2061 
2062  candidates_sol->Search( amin, amax, checkCallback, reinterpret_cast< void * >( list ) );
2063 
2064  int i;
2065  int nbActive = 0;
2066  for ( i = 0; i < nbft; i++ )
2067  {
2068  solution[i] = -1;
2069  if ( sol->s[i] >= 0 )
2070  nbActive++;
2071  }
2072 
2073  if ( list->size() != nbActive )
2074  {
2075  // Error in solution !!!!
2076  }
2077 
2078  while ( !list->isEmpty() )
2079  {
2080  LabelPosition *lp = list->takeFirst();
2081  int probFeatId = lp->getProblemFeatureId();
2082 
2083  solution[probFeatId] = lp->getId();
2084  }
2085 
2086  delete [] solution;
2087 }
2088 
2089 typedef struct _nokContext
2090 {
2091  LabelPosition *lp = nullptr;
2092  bool *ok = nullptr;
2093  int *wrap = nullptr;
2094 } NokContext;
2095 
2096 bool nokCallback( LabelPosition *lp, void *context )
2097 {
2098  NokContext *ctx = reinterpret_cast< NokContext *>( context );
2099  LabelPosition *lp2 = ctx->lp;
2100  bool *ok = ctx->ok;
2101  int *wrap = ctx->wrap;
2102 
2103  if ( lp2->isInConflict( lp ) )
2104  {
2105  if ( wrap )
2106  {
2107  ok[wrap[lp->getProblemFeatureId()]] = false;
2108  }
2109  else
2110  {
2111  ok[lp->getProblemFeatureId()] = false;
2112  }
2113  }
2114 
2115  return true;
2116 }
2117 
2119 {
2120 
2121  if ( nbft == 0 )
2122  return;
2123 
2124  int i;
2125  int seed;
2126  bool *ok = new bool[nbft];
2127  int fid;
2128  int lid;
2129  int popit = 0;
2130  double amin[2];
2131  double amax[2];
2132 
2133  NokContext context;
2134  context.ok = ok;
2135  context.wrap = nullptr;
2136 
2137  Chain *retainedChain = nullptr;
2138 
2139  featWrap = nullptr;
2140 
2141  for ( i = 0; i < nbft; i++ )
2142  {
2143  ok[i] = false;
2144  }
2145 
2146  //initialization();
2147  init_sol_falp();
2148 
2149  //check_solution();
2150  solution_cost();
2151 
2152  int iter = 0;
2153 
2154  while ( true )
2155  {
2156 
2157  //check_solution();
2158 
2159  for ( seed = ( iter + 1 ) % nbft;
2160  ok[seed] && seed != iter;
2161  seed = ( seed + 1 ) % nbft )
2162  ;
2163 
2164  // All seeds are OK
2165  if ( seed == iter )
2166  {
2167  break;
2168  }
2169 
2170  iter = ( iter + 1 ) % nbft;
2171  retainedChain = chain( seed );
2172 
2173  if ( retainedChain && retainedChain->delta < - EPSILON )
2174  {
2175  // apply modification
2176  for ( i = 0; i < retainedChain->degree; i++ )
2177  {
2178  fid = retainedChain->feat[i];
2179  lid = retainedChain->label[i];
2180 
2181  if ( sol->s[fid] >= 0 )
2182  {
2183  LabelPosition *old = mLabelPositions.at( sol->s[fid] );
2184  old->removeFromIndex( candidates_sol );
2185 
2186  old->getBoundingBox( amin, amax );
2187 
2188  context.lp = old;
2189  candidates->Search( amin, amax, nokCallback, &context );
2190  }
2191 
2192  sol->s[fid] = lid;
2193 
2194  if ( sol->s[fid] >= 0 )
2195  {
2196  mLabelPositions.at( lid )->insertIntoIndex( candidates_sol );
2197  }
2198 
2199  ok[fid] = false;
2200  }
2201  sol->cost += retainedChain->delta;
2202  }
2203  else
2204  {
2205  // no chain or the one is not god enough
2206  ok[seed] = true;
2207  }
2208 
2209  delete_chain( retainedChain );
2210  popit++;
2211  }
2212 
2213  solution_cost();
2214  delete[] ok;
2215 }
2216 
2218 {
2219  return l1->getWidth() * l1->getHeight() > l2->getWidth() * l2->getHeight();
2220 }
2221 
2222 QList<LabelPosition *> Problem::getSolution( bool returnInactive )
2223 {
2224  int i;
2225  QList<LabelPosition *> solList;
2226 
2227  if ( nbft == 0 )
2228  {
2229  return solList;
2230  }
2231 
2232  for ( i = 0; i < nbft; i++ )
2233  {
2234  if ( sol->s[i] != -1 )
2235  {
2236  solList.push_back( mLabelPositions.at( sol->s[i] ) ); // active labels
2237  }
2238  else if ( returnInactive
2239  || mLabelPositions.at( featStartId[i] )->getFeaturePart()->layer()->displayAll()
2240  || mLabelPositions.at( featStartId[i] )->getFeaturePart()->alwaysShow() )
2241  {
2242  solList.push_back( mLabelPositions.at( featStartId[i] ) ); // unplaced label
2243  }
2244  }
2245 
2246  // if features collide, order by size, so smaller ones appear on top
2247  if ( returnInactive )
2248  {
2249  std::sort( solList.begin(), solList.end(), compareLabelArea );
2250  }
2251 
2252  return solList;
2253 }
2254 
2256 {
2257  int i, j;
2258 
2259  PalStat *stats = new PalStat();
2260 
2261  stats->nbObjects = nbft;
2262  stats->nbLabelledObjects = 0;
2263 
2264  stats->nbLayers = nbLabelledLayers;
2265  stats->layersNbObjects = new int[stats->nbLayers];
2266  stats->layersNbLabelledObjects = new int[stats->nbLayers];
2267 
2268  for ( i = 0; i < stats->nbLayers; i++ )
2269  {
2270  stats->layersName << labelledLayersName[i];
2271  stats->layersNbObjects[i] = 0;
2272  stats->layersNbLabelledObjects[i] = 0;
2273  }
2274 
2275  QString lyrName;
2276  int k;
2277  for ( i = 0; i < nbft; i++ )
2278  {
2279  lyrName = mLabelPositions.at( featStartId[i] )->getFeaturePart()->feature()->provider()->name();
2280  k = -1;
2281  for ( j = 0; j < stats->nbLayers; j++ )
2282  {
2283  if ( lyrName == stats->layersName[j] )
2284  {
2285  k = j;
2286  break;
2287  }
2288  }
2289  if ( k != -1 )
2290  {
2291  stats->layersNbObjects[k]++;
2292  if ( sol->s[i] >= 0 )
2293  {
2294  stats->layersNbLabelledObjects[k]++;
2295  stats->nbLabelledObjects++;
2296  }
2297  }
2298  else
2299  {
2300  // unknown layer
2301  }
2302  }
2303 
2304  return stats;
2305 }
2306 
2307 void Problem::solution_cost()
2308 {
2309  sol->cost = 0.0;
2310  nbActive = 0;
2311 
2312  int nbOv;
2313 
2314  int i;
2315 
2317  context.inactiveCost = inactiveCost;
2318  context.nbOv = &nbOv;
2319  context.cost = &sol->cost;
2320  double amin[2];
2321  double amax[2];
2322  LabelPosition *lp = nullptr;
2323 
2324  int nbHidden = 0;
2325 
2326  for ( i = 0; i < nbft; i++ )
2327  {
2328  if ( sol->s[i] == -1 )
2329  {
2330  sol->cost += inactiveCost[i];
2331  nbHidden++;
2332  }
2333  else
2334  {
2335  nbOv = 0;
2336  lp = mLabelPositions.at( sol->s[i] );
2337 
2338  lp->getBoundingBox( amin, amax );
2339 
2340  context.lp = lp;
2341  candidates_sol->Search( amin, amax, LabelPosition::countFullOverlapCallback, &context );
2342 
2343  sol->cost += lp->cost();
2344 
2345  if ( nbOv == 0 )
2346  nbActive++;
2347  }
2348  }
2349 }
bool isInConflict(LabelPosition *ls)
Check whether or not this overlap with another labelPosition.
double popmusic_chain(SubPart *part)
POPMUSIC, chain.
Definition: problem.cpp:1713
LabelPosition * lp
Definition: problem.cpp:525
bool borderSizeInc(void *l, void *r)
Definition: problem.cpp:100
struct _Triple Triple
int label_id
Definition: problem.cpp:686
int * nbOlap
Definition: problem.cpp:737
static bool compareLabelArea(pal::LabelPosition *l1, pal::LabelPosition *l2)
Definition: problem.cpp:2217
void reduce()
Definition: problem.cpp:105
double * delta_tmp
Definition: problem.cpp:1093
bool isIn(int key)
double compute_feature_cost(SubPart *part, int feat_id, int label_id, int *nbOverlap)
Definition: problem.cpp:627
void getBoundingBox(double amin[2], double amax[2]) const
Returns bounding box - amin: xmin,ymin - amax: xmax,ymax.
int probSize
of features in problem
Definition: problem.h:65
double cost
Definition: problem.h:56
bool subPartCallback(LabelPosition *lp, void *ctx)
Definition: problem.cpp:528
QLinkedList< int > * queue
Definition: problem.cpp:523
Thrown when something is added in a Full set.
int feat_id
Definition: problem.cpp:685
int degree
Definition: problem.h:95
bool chainCallback(LabelPosition *lp, void *context)
Definition: problem.cpp:1099
Is slower and best than TABU, worse and faster than TABU_CHAIN.
Definition: pal.h:64
bool checkCallback(LabelPosition *lp, void *ctx)
Definition: problem.cpp:2039
struct _nokContext NokContext
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
int getProblemFeatureId() const
struct pal::_elementary_transformation ElemTrans
double nbOverlap
Definition: problem.cpp:97
void remove(int key)
static bool removeOverlapCallback(LabelPosition *lp, void *ctx)
QLinkedList< ElemTrans * > * currentChain
Definition: problem.cpp:1091
Is a little bit better than CHAIN but slower.
Definition: pal.h:63
LabelPosition * lp
Definition: problem.cpp:196
bool falpCallback1(LabelPosition *lp, void *ctx)
Definition: problem.cpp:238
bool updateCandidatesCost(LabelPosition *lp, void *context)
Definition: problem.cpp:744
int * wrap
Definition: problem.cpp:2093
Triple ** candidates
Definition: problem.cpp:735
int nbOverlap
Definition: problem.cpp:688
int * tmpsol
Definition: problem.cpp:1087
double cost() const
Returns the candidate label position&#39;s geographical cost.
RTree< LabelPosition *, double, 2, double > * candidates
Definition: problem.cpp:197
void chain_search()
Test with very-large scale neighborhood.
Definition: problem.cpp:2118
int * featWrap
Definition: problem.cpp:1088
int * label
Definition: problem.h:98
double getHeight() const
Definition: problem.cpp:93
SubPart * subPart(int r, int featseed, int *isIn)
Definition: problem.cpp:546
Is the best but slowest.
Definition: pal.h:62
void seed(uint32_t value)
struct pal::_chain Chain
static void sort(void **items, int N, bool(*greater)(void *l, void *r))
Sort an array of pointers.
Definition: util.cpp:40
double * inactiveCost
Definition: problem.cpp:1094
int id
Definition: problem.cpp:95
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
double popmusic_tabu(SubPart *part)
Definition: problem.cpp:773
bool nokCallback(LabelPosition *lp, void *context)
Definition: problem.cpp:2096
void actualizeTabuCandidateList(int m, int iteration, int nbOverlap, int *candidateListSize, double candidateBaseFactor, double *candidateFactor, int minCandidateListSize, double reductionFactor, int minTabuTSize, double tabuFactor, int *tenure, int n)
Definition: problem.cpp:697
void insert(int key, double p)
void popmusic()
popmusic framework
Definition: problem.cpp:370
int * featWrap
Definition: problem.cpp:739
double diff_cost
Definition: problem.cpp:738
void removeFromIndex(RTree< LabelPosition *, double, 2, double > *index)
bool * ok
Definition: problem.cpp:2092
double * labelPositionCost
Definition: problem.cpp:736
PalStat * getStats()
Definition: problem.cpp:2255
int * sol
sub solution
Definition: problem.h:85
LabelPosition * lp
Definition: problem.cpp:1086
int getId() const
Returns the id.
void actualizeCandidateList(int nbOverlap, int *candidateListSize, double, double *candidateFactor, int minCandidateListSize, double growingFactor, int n)
Definition: problem.cpp:718
struct pal::_subpart SubPart
LabelPosition * lp
Definition: problem.cpp:2091
double cost
Definition: problem.cpp:687
int * sub
wrap bw sub feat and main feat
Definition: problem.h:80
int * s
Definition: problem.h:55
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
double compute_subsolution_cost(SubPart *part, int *s, int *nbOverlap)
Definition: problem.cpp:664
int * feat
Definition: problem.h:97
double getWidth() const
int getNumOverlaps() const
void delete_chain(Chain *chain)
Definition: problem.cpp:48
LabelPosition * lp
Definition: problem.cpp:734
QLinkedList< int > * conflicts
Definition: problem.cpp:1092
double inactiveCost
Definition: problem.cpp:96
#define EPSILON
Definition: util.h:75
int subSize
total # features (prob + border)
Definition: problem.h:75
Summary statistics of labeling problem.
Definition: palstat.h:48
void ignoreLabel(LabelPosition *lp, PriorityQueue *list, RTree< LabelPosition *, double, 2, double > *candidates)
Definition: problem.cpp:214
LabelPosition is a candidate feature label position.
Definition: labelposition.h:55
bool decreaseCost(void *tl, void *tr)
Definition: problem.cpp:692
bool falpCallback2(LabelPosition *lp, void *ctx)
Definition: problem.cpp:200
PriorityQueue * list
Definition: problem.cpp:195
SearchMethod
Search method to use.
Definition: pal.h:59
int borderSize
of features bounding the problem
Definition: problem.h:70
double popmusic_tabu_chain(SubPart *part)
POPMUSIC, Tabu search with chain&#39;.
Definition: problem.cpp:1860
void init_sol_empty()
Basic initial solution : every feature to -1.
Definition: problem.cpp:171
QList< LabelPosition * > getSolution(bool returnInactive)
Definition: problem.cpp:2222
double delta
Definition: problem.h:96
int seed
first feat in sub part
Definition: problem.h:90
void init_sol_falp()
Definition: problem.cpp:257
void decreaseKey(int key)