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