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