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