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