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