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