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