53 delete[] chain->
label;
65 candidates =
new RTree<LabelPosition *, double, 2, double>();
66 candidates_sol =
new RTree<LabelPosition *, double, 2, double>();
67 candidates_subsol =
nullptr;
86 qDeleteAll( mLabelPositions );
87 mLabelPositions.clear();
90 delete[] inactiveCost;
93 delete candidates_sol;
95 if ( candidates_subsol )
97 delete candidates_subsol;
110 return ( reinterpret_cast< SubPart * >( l ) )->borderSize > (
reinterpret_cast< SubPart *
>( r ) )->borderSize;
124 bool *ok =
new bool[nblp];
127 for ( i = 0; i < nblp; i++ )
138 for ( i = 0; i < nbft; i++ )
141 for ( j = 0; j < featNbLp[i]; j++ )
143 if ( !ok[featStartId[i] + j] )
145 if ( mLabelPositions.at( featStartId[i] + j )->getNumOverlaps() == 0 )
148 ok[featStartId[i] + j] =
true;
151 counter += featNbLp[i] - j - 1;
153 for ( k = j + 1; k < featNbLp[i]; k++ )
156 lpid = featStartId[i] + k;
158 lp2 = mLabelPositions.at( lpid );
175 this->nblp -= counter;
191 sol->
s =
new int[nbft];
193 for ( i = 0; i < nbft; i++ )
229 context->
list = list;
252 RTree <LabelPosition *, double, 2, double> *candidates = context->
candidates;
281 context->
list = list;
285 for ( i = 0; i < nbft; i++ )
286 for ( j = 0; j < featNbLp[i]; j++ )
288 label = featStartId[i] + j;
291 list->
insert( label, mLabelPositions.at( label )->getNumOverlaps() );
301 if (
pal->isCanceled() )
311 lp = mLabelPositions.at( label );
313 if ( lp->
getId() != label )
319 sol->
s[probFeatId] = label;
321 for ( i = featStartId[probFeatId]; i < featStartId[probFeatId] + featNbLp[probFeatId]; i++ )
323 ignoreLabel( mLabelPositions.at( i ), list, candidates );
330 candidates->Search( amin, amax,
falpCallback1, reinterpret_cast< void * >( context ) );
331 candidates_sol->Insert( amin, amax, lp );
346 for ( i = 0; i < nbft; i++ )
348 if ( sol->
s[i] == -1 )
351 start_p = featStartId[i];
352 for ( p = 0; p < featNbLp[i]; p++ )
354 lp = mLabelPositions.at( start_p + p );
368 sol->
s[i] = retainedLabel->
getId();
387 bool *ok =
new bool[nbft];
389 int r =
pal->popmusic_r;
393 candidates_subsol =
new RTree<LabelPosition *, double, 2, double>();
401 labelPositionCost =
new double[all_nblp];
402 nbOlap =
new int[all_nblp];
404 featWrap =
new int[nbft];
405 memset( featWrap, -1,
sizeof(
int ) *nbft );
408 int *isIn =
new int[nbft];
410 memset( isIn, 0,
sizeof(
int ) *nbft );
413 for ( i = 0; i < nbft; i++ )
415 parts[i] =
subPart( r, i, isIn );
433 for ( i = ( seed + 1 ) % nbft; ok[i] && i !=
seed; i = ( i + 1 ) % nbft )
436 if ( i == seed && ok[seed] )
444 current = parts[
seed];
448 candidates_subsol->RemoveAll();
450 for ( i = 0; i < current->
subSize; i++ )
452 current->
sol[i] = sol->
s[current->
sub[i]];
453 if ( current->
sol[i] != -1 )
455 mLabelPositions.at( current->
sol[i] )->insertIntoIndex( candidates_subsol );
459 switch ( searchMethod )
487 ok[current->
sub[i]] =
false;
490 for ( i = current->
borderSize; i < current->subSize; i++ )
493 if ( sol->
s[current->
sub[i]] != -1 )
495 mLabelPositions.at( sol->
s[current->
sub[i]] )->removeFromIndex( candidates_sol );
498 sol->
s[current->
sub[i]] = current->
sol[i];
500 if ( current->
sol[i] != -1 )
502 mLabelPositions.at( current->
sol[i] )->insertIntoIndex( candidates_sol );
505 ok[current->
sub[i]] =
false;
516 delete[] labelPositionCost;
519 for ( i = 0; i < nbft; i++ )
521 delete[] parts[i]->
sub;
522 delete[] parts[i]->
sol;
540 int *isIn = context->
isIn;
541 QLinkedList<int> *queue = context->
queue;
557 QLinkedList<int> *queue =
new QLinkedList<int>;
558 QLinkedList<int> *ri =
new QLinkedList<int>;
574 context.
queue = queue;
577 queue->append( featseed );
582 while ( ri->size() < r && !queue->isEmpty() )
584 id = queue->takeFirst();
587 featS = featStartId[id];
590 for ( i = featS; i < featS + p; i++ )
592 lp = mLabelPositions.at( i );
597 candidates->Search( amin, amax,
subPartCallback, reinterpret_cast< void * >( &context ) );
604 sub =
new int[n + nb];
608 while ( !queue->isEmpty() )
610 sub[i] = queue->takeFirst();
615 while ( !ri->isEmpty() )
617 sub[i] = ri->takeFirst();
632 subPart->
seed = featseed;
643 context.
nbOv = nbOverlap;
644 context.
cost = &cost;
654 lp = mLabelPositions.at( label_id );
665 cost = inactiveCost[part->
sub[feat_id]];
681 for ( i = 0; i < part->
subSize; i++ )
703 return ( reinterpret_cast< Triple * >( tl ) )->cost < (
reinterpret_cast< Triple *
>( tr ) )->cost;
707 double candidateBaseFactor,
double *candidateFactor,
708 int minCandidateListSize,
double reductionFactor,
709 int minTabuTSize,
double tabuFactor,
int *tenure,
int n )
712 if ( *candidateFactor > candidateBaseFactor )
713 *candidateFactor /= reductionFactor;
715 if ( iteration % m == 0 )
717 *tenure = minTabuTSize +
static_cast< int >( tabuFactor * nbOverlap );
718 *candidateListSize = minCandidateListSize +
static_cast< int >( *candidateFactor * nbOverlap );
720 if ( *candidateListSize > n )
721 *candidateListSize = n;
728 double *candidateFactor,
int minCandidateListSize,
double growingFactor,
int n )
730 if ( *candidateListSize < n )
731 *candidateFactor = *candidateFactor * growingFactor;
732 *candidateListSize = minCandidateListSize +
static_cast< int >( *candidateFactor * nbOverlap );
734 if ( *candidateListSize > n )
735 *candidateListSize = n;
745 double *labelPositionCost =
nullptr;
746 int *nbOlap =
nullptr;
748 int *featWrap =
nullptr;
767 if ( feat_id >= 0 && ctx->
sol[feat_id] == lp->
getId() )
769 if ( ( feat_id2 = feat_id - ctx->
borderSize ) >= 0 )
787 int *sub = part->
sub;
788 int *sol = part->
sol;
793 int *best_sol =
new int[subSize];
799 int *tabu_list =
new int[probSize];
829 int minTabuTSize = 9;
830 double tabuFactor = 0.5;
832 int minCandidateListSize = 18;
834 double candidateBaseFactor = 0.73;
836 double growingFactor = 15;
837 double reductionFactor = 1.3;
839 int candidateListSize = minCandidateListSize;
840 double candidateFactor = candidateBaseFactor;
846 max_it = probSize *
pal->tabuMaxIt;
847 itwImp = probSize *
pal->tabuMinIt;
855 for ( i = 0; i < subSize; i++ )
856 featWrap[sub[i]] = i;
858 for ( i = 0; i < subSize; i++ )
860 j = featStartId[sub[i]];
861 for ( lp = 0; lp < featNbLp[sub[i]]; lp++ )
868 first_lp = ( displayAll ? 0 : -1 );
869 for ( i = 0; i < probSize; i++ )
874 candidateList[i] =
new Triple();
875 candidateList[i]->
feat_id = i + borderSize;
876 candidateList[i]->
label_id = sol[i + borderSize];
878 candidateListUnsorted[i] = candidateList[i];
880 if ( sol[i + borderSize] >= 0 )
882 j = sol[i + borderSize];
883 candidateList[i]->
cost = labelPositionCost[j];
888 candidateList[i]->
cost = inactiveCost[sub[i + borderSize]];
895 for ( i = 0; i < subSize; i++ )
899 cur_cost += inactiveCost[sub[i]];
903 nbOverlap += nbOlap[sol[i]];
904 cur_cost += labelPositionCost[sol[i]];
910 best_cost = cur_cost;
911 initial_cost = cur_cost;
912 memcpy( best_sol, sol,
sizeof(
int ) * ( subSize ) );
917 while ( it < stop_it && best_cost >=
EPSILON )
919 actualizeTabuCandidateList( m, it, nbOverlap, &candidateListSize, candidateBaseFactor, &candidateFactor, minCandidateListSize, reductionFactor, minTabuTSize, tabuFactor, &tenure, probSize );
926 for ( i = 0; i < candidateListSize; i++ )
928 feat_id = candidateList[i]->
feat_id;
929 feat_sub_id = sub[feat_id];
930 label_id = candidateList[i]->
label_id;
932 int oldPos = ( label_id < 0 ? -1 : label_id - featStartId[feat_sub_id] );
935 p = featNbLp[feat_sub_id];
939 for ( j = first_lp; j < p; j++ )
944 if ( sol[feat_id] < 0 )
946 delta = -inactiveCost[feat_sub_id];
950 delta = -labelPositionCost[sol[feat_id]];
951 delta -= nbOlap[sol[feat_id]] * ( inactiveCost[feat_sub_id] + mLabelPositions.at( label_id )->cost() );
956 delta += labelPositionCost[featStartId[feat_sub_id] + j];
957 delta += nbOlap[featStartId[feat_sub_id] + j] * ( inactiveCost[feat_sub_id] + mLabelPositions.at( featStartId[feat_sub_id] + j )->cost() );
961 delta += inactiveCost[feat_sub_id];
965 authorized = ( tabu_list[feat_id - borderSize] <= it ) || ( cur_cost + delta < best_cost );
967 if ( delta < delta_min && authorized )
969 choosed_feat = feat_id;
974 choosed_label = featStartId[feat_sub_id] + j;
984 if ( choosed_feat >= 0 )
987 int old_label = sol[choosed_feat];
989 tabu_list[choosed_feat - borderSize] = it + tenure;
990 sol[choosed_feat] = choosed_label;
991 candidateList[candidateId]->
label_id = choosed_label;
993 if ( old_label != -1 )
994 mLabelPositions.at( old_label )->removeFromIndex( candidates_subsol );
997 double local_inactive = inactiveCost[sub[choosed_feat]];
999 if ( choosed_label != -1 )
1001 candidateList[candidateId]->
cost = labelPositionCost[choosed_label];
1002 candidateList[candidateId]->
nbOverlap = nbOlap[choosed_label];
1006 candidateList[candidateId]->
cost = local_inactive;
1007 candidateList[candidateId]->
nbOverlap = 1;
1010 cur_cost += delta_min;
1025 if ( old_label >= 0 )
1027 lp = mLabelPositions.at( old_label );
1037 if ( choosed_label >= 0 )
1039 lp = mLabelPositions.at( choosed_label );
1054 if ( best_cost - cur_cost >
EPSILON )
1056 best_cost = cur_cost;
1057 memcpy( best_sol, sol,
sizeof(
int ) * ( subSize ) );
1058 stop_it = it + itwImp;
1059 if ( stop_it > max_it )
1067 &candidateFactor, minCandidateListSize, growingFactor, probSize );
1072 memcpy( sol, best_sol,
sizeof(
int ) * ( subSize ) );
1074 for ( i = 0; i < subSize; i++ )
1075 featWrap[sub[i]] = -1;
1077 for ( i = 0; i < probSize; i++ )
1078 delete candidateList[i];
1080 delete[] candidateList;
1081 delete[] candidateListUnsorted;
1086 return initial_cost - best_cost;
1096 int *tmpsol =
nullptr;
1097 int *featWrap =
nullptr;
1098 int *feat =
nullptr;
1102 double *delta_tmp =
nullptr;
1103 double *inactiveCost =
nullptr;
1115 bool sub =
nullptr != ctx->
featWrap;
1126 if ( feat >= 0 && ctx->
tmpsol[feat] == lp->
getId() )
1128 if ( sub && feat < ctx->borderSize )
1135 QLinkedList< ElemTrans * >::iterator cur;
1138 if ( ( *cur )->feat == feat )
1144 if ( !ctx->
conflicts->contains( feat ) )
1164 int *sub = part->
sub;
1165 int *sol = part->
sol;
1170 double delta_best = DBL_MAX;
1175 Chain *retainedChain =
nullptr;
1177 int max_degree =
pal->ejChainDeg;
1181 QLinkedList<ElemTrans *> *currentChain =
new QLinkedList<ElemTrans *>;
1182 QLinkedList<int> *conflicts =
new QLinkedList<int>;
1184 int *tmpsol =
new int[subSize];
1185 memcpy( tmpsol, sol,
sizeof(
int ) *subSize );
1196 context.
feat =
nullptr;
1202 while ( seed != -1 )
1204 subseed = sub[
seed];
1205 seedNbLp = featNbLp[subseed];
1206 delta_min = DBL_MAX;
1211 if ( tmpsol[seed] == -1 )
1212 delta -= inactiveCost[subseed];
1214 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
1217 for ( i = -1; i < seedNbLp; i++ )
1222 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[subseed] != tmpsol[seed] )
1226 lid = featStartId[subseed] + i;
1229 lp = mLabelPositions.at( lid );
1237 candidates_subsol->Search( amin, amax,
chainCallback, reinterpret_cast< void * >( &context ) );
1240 if ( conflicts->isEmpty() )
1242 if ( !retainedChain || delta + lp->
cost() < delta_best )
1245 if ( retainedChain )
1247 delete[] retainedChain->
label;
1248 delete[] retainedChain->
feat;
1252 retainedChain =
new Chain();
1255 delta_best = delta + lp->
cost();
1257 retainedChain->
degree = currentChain->size() + 1;
1258 retainedChain->
feat =
new int[retainedChain->
degree];
1259 retainedChain->
label =
new int[retainedChain->
degree];
1260 QLinkedList< ElemTrans * >::iterator current = currentChain->begin();
1263 while ( current != currentChain->end() )
1266 retainedChain->
feat[j] = move->
feat;
1272 retainedChain->
label[j] = lid;
1273 retainedChain->
delta = delta + mLabelPositions.at( retainedChain->
label[j] )->cost();
1278 else if ( conflicts->size() == 1 )
1280 if ( delta_tmp < delta_min )
1282 delta_min = delta_tmp;
1283 retainedLabel = lid;
1284 next_seed = conflicts->takeFirst();
1288 conflicts->takeFirst();
1296 newChain->
degree = currentChain->size() + 1 + conflicts->size();
1299 QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1302 while ( current != currentChain->end() )
1312 newChain->
label[j] = lid;
1313 newChain->
delta = delta + mLabelPositions.at( newChain->
label[j] )->cost();
1317 while ( !conflicts->isEmpty() )
1319 int ftid = conflicts->takeFirst();
1320 newChain->
feat[j] = ftid;
1321 newChain->
label[j] = -1;
1322 newChain->
delta += inactiveCost[sub[ftid]];
1326 if ( newChain->
delta < delta_best )
1328 if ( retainedChain )
1331 delta_best = newChain->
delta;
1332 retainedChain = newChain;
1342 if ( !retainedChain || delta + inactiveCost[subseed] < delta_best )
1344 if ( retainedChain )
1346 delete[] retainedChain->
label;
1347 delete[] retainedChain->
feat;
1350 retainedChain =
new Chain();
1352 delta_best = delta + inactiveCost[subseed];
1354 retainedChain->
degree = currentChain->size() + 1;
1355 retainedChain->
feat =
new int[retainedChain->
degree];
1356 retainedChain->
label =
new int[retainedChain->
degree];
1357 QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1360 while ( current != currentChain->end() )
1363 retainedChain->
feat[j] = move->
feat;
1369 retainedChain->
label[j] = -1;
1370 retainedChain->
delta = delta + inactiveCost[subseed];
1382 if ( next_seed == -1 )
1386 else if ( currentChain->size() > max_degree )
1396 currentChain->append( et );
1400 mLabelPositions.at( et->
old_label )->removeFromIndex( candidates_subsol );
1405 mLabelPositions.at( et->
new_label )->insertIntoIndex( candidates_subsol );
1408 tmpsol[
seed] = retainedLabel;
1409 delta += mLabelPositions.at( retainedLabel )->cost();
1414 while ( !currentChain->isEmpty() )
1416 ElemTrans *et = currentChain->takeFirst();
1420 mLabelPositions.at( et->
new_label )->removeFromIndex( candidates_subsol );
1425 mLabelPositions.at( et->
old_label )->insertIntoIndex( candidates_subsol );
1430 delete currentChain;
1436 return retainedChain;
1440 inline Chain *Problem::chain(
int seed )
1450 double delta_best = DBL_MAX;
1455 Chain *retainedChain =
nullptr;
1457 int max_degree =
pal->ejChainDeg;
1461 QLinkedList<ElemTrans *> *currentChain =
new QLinkedList<ElemTrans *>;
1462 QLinkedList<int> *conflicts =
new QLinkedList<int>;
1464 int *tmpsol =
new int[nbft];
1465 memcpy( tmpsol, sol->s,
sizeof(
int ) *nbft );
1476 context.
feat =
nullptr;
1482 while ( seed != -1 )
1484 seedNbLp = featNbLp[
seed];
1485 delta_min = DBL_MAX;
1491 if ( tmpsol[seed] == -1 )
1492 delta -= inactiveCost[
seed];
1494 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
1496 for ( i = -1; i < seedNbLp; i++ )
1501 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[seed] != tmpsol[seed] )
1505 lid = featStartId[
seed] + i;
1508 lp = mLabelPositions.at( lid );
1515 candidates_sol->Search( amin, amax,
chainCallback, reinterpret_cast< void * >( &context ) );
1518 if ( conflicts->isEmpty() )
1520 if ( !retainedChain || delta + lp->
cost() < delta_best )
1522 if ( retainedChain )
1524 delete[] retainedChain->
label;
1525 delete[] retainedChain->
feat;
1529 retainedChain =
new Chain();
1532 delta_best = delta + lp->
cost();
1534 retainedChain->
degree = currentChain->size() + 1;
1535 retainedChain->
feat =
new int[retainedChain->
degree];
1536 retainedChain->
label =
new int[retainedChain->
degree];
1537 QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1540 while ( current != currentChain->end() )
1543 retainedChain->
feat[j] = move->
feat;
1549 retainedChain->
label[j] = lid;
1550 retainedChain->
delta = delta + lp->
cost();
1555 else if ( conflicts->size() == 1 )
1557 if ( delta_tmp < delta_min )
1559 delta_min = delta_tmp;
1560 retainedLabel = lid;
1561 next_seed = conflicts->takeFirst();
1565 conflicts->takeFirst();
1573 newChain->
degree = currentChain->size() + 1 + conflicts->size();
1576 QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1580 while ( current != currentChain->end() )
1591 newChain->
label[j] = lid;
1592 newChain->
delta = delta + mLabelPositions.at( newChain->
label[j] )->cost();
1596 while ( !conflicts->isEmpty() )
1598 int ftid = conflicts->takeFirst();
1599 newChain->
feat[j] = ftid;
1600 newChain->
label[j] = -1;
1601 newChain->
delta += inactiveCost[ftid];
1605 if ( newChain->
delta < delta_best )
1607 if ( retainedChain )
1610 delta_best = newChain->
delta;
1611 retainedChain = newChain;
1622 if ( !retainedChain || delta + inactiveCost[seed] < delta_best )
1624 if ( retainedChain )
1626 delete[] retainedChain->
label;
1627 delete[] retainedChain->
feat;
1630 retainedChain =
new Chain();
1632 delta_best = delta + inactiveCost[
seed];
1634 retainedChain->
degree = currentChain->size() + 1;
1635 retainedChain->
feat =
new int[retainedChain->
degree];
1636 retainedChain->
label =
new int[retainedChain->
degree];
1637 QLinkedList<ElemTrans *>::iterator current = currentChain->begin();
1640 while ( current != currentChain->end() )
1643 retainedChain->
feat[j] = move->
feat;
1649 retainedChain->
label[j] = -1;
1650 retainedChain->
delta = delta + inactiveCost[
seed];
1662 if ( next_seed == -1 )
1666 else if ( currentChain->size() > max_degree )
1677 currentChain->append( et );
1681 mLabelPositions.at( et->
old_label )->removeFromIndex( candidates_sol );
1686 mLabelPositions.at( et->
new_label )->insertIntoIndex( candidates_sol );
1690 tmpsol[
seed] = retainedLabel;
1691 delta += mLabelPositions.at( retainedLabel )->cost();
1697 while ( !currentChain->isEmpty() )
1699 ElemTrans *et = currentChain->takeFirst();
1703 mLabelPositions.at( et->
new_label )->removeFromIndex( candidates_sol );
1708 mLabelPositions.at( et->
old_label )->insertIntoIndex( candidates_sol );
1713 delete currentChain;
1719 return retainedChain;
1730 int *sub = part->
sub;
1731 int *sol = part->
sol;
1733 int *best_sol =
new int[subSize];
1735 for ( i = 0; i < subSize; i++ )
1737 featWrap[sub[i]] = i;
1738 best_sol[i] = sol[i];
1741 double initial_cost;
1742 double cur_cost = 0;
1743 double best_cost = 0;
1754 int *tabu_list =
new int[subSize];
1756 Chain *current_chain =
nullptr;
1765 int tenure =
pal->tenure;
1767 for ( i = 0; i < subSize; i++ )
1773 initial_cost = cur_cost;
1774 best_cost = cur_cost;
1778 maxit = probSize *
pal->tabuMaxIt;
1780 itwimp = probSize *
pal->tabuMinIt;
1785 for ( i = 0; i < borderSize; i++ )
1786 tabu_list[i] = maxit;
1788 for ( i = 0; i < probSize; i++ )
1789 tabu_list[i + borderSize] = -1;
1791 while ( it < stop_it )
1793 seed = ( it % probSize ) + borderSize;
1795 current_chain = chain( part, seed );
1796 if ( current_chain )
1801 if ( tabu_list[seed] < it || ( cur_cost + current_chain->
delta ) - best_cost < 0.0 )
1804 for ( i = 0; i < current_chain->
degree; i++ )
1806 fid = current_chain->
feat[i];
1807 lid = current_chain->
label[i];
1809 if ( sol[fid] >= 0 )
1811 mLabelPositions.at( sol[fid] )->removeFromIndex( candidates_subsol );
1815 if ( sol[fid] >= 0 )
1817 mLabelPositions.at( lid )->insertIntoIndex( candidates_subsol );
1820 tabu_list[fid] = it + tenure;
1823 cur_cost += current_chain->
delta;
1826 if ( best_cost - cur_cost >
EPSILON )
1828 best_cost = cur_cost;
1829 memcpy( best_sol, sol,
sizeof(
int ) *subSize );
1831 stop_it = ( it + itwimp > maxit ? maxit : it + itwimp );
1839 memcpy( sol, best_sol,
sizeof(
int ) *subSize );
1859 for ( i = 0; i < subSize; i++ )
1860 featWrap[sub[i]] = -1;
1866 return initial_cost - best_cost;
1876 int *sub = part->
sub;
1877 int *sol = part->
sol;
1879 int *best_sol =
new int[subSize];
1881 for ( i = 0; i < subSize; i++ )
1883 featWrap[sub[i]] = i;
1886 double initial_cost;
1887 double cur_cost = 0;
1888 double best_cost = 0;
1899 int *tabu_list =
new int[subSize];
1901 Chain *retainedChain =
nullptr;
1902 Chain *current_chain =
nullptr;
1911 int tenure =
pal->tenure;
1918 for ( i = 0; i < subSize; i++ )
1924 initial_cost = cur_cost;
1925 best_cost = cur_cost;
1929 maxit = probSize *
pal->tabuMaxIt;
1931 itwimp = probSize *
pal->tabuMinIt;
1935 for ( i = 0; i < borderSize; i++ )
1936 tabu_list[i] = maxit;
1939 for ( i = 0; i < probSize; i++ )
1941 tabu_list[i + borderSize] = -1;
1943 candidates[i] =
new Triple();
1944 candidates[i]->
feat_id = i + borderSize;
1945 candidatesUnsorted[i] = candidates[i];
1947 candidates[i]->
cost = ( sol[i + borderSize] == -1 ? inactiveCost[i + borderSize] : mLabelPositions.at( sol[i + borderSize] )->cost() );
1952 int candidateListSize;
1953 candidateListSize = int (
pal->candListSize * static_cast< double >( probSize ) + 0.5 );
1955 if ( candidateListSize > probSize )
1956 candidateListSize = probSize;
1958 while ( it < stop_it )
1960 retainedChain =
nullptr;
1962 for ( itC = 0; itC < candidateListSize; itC++ )
1964 seed = candidates[itC]->
feat_id;
1966 current_chain = chain( part, seed );
1968 if ( current_chain )
1971 if ( tabu_list[seed] < it || ( cur_cost + current_chain->
delta ) - best_cost < 0.0 )
1973 if ( !retainedChain )
1975 retainedChain = current_chain;
1980 retainedChain = current_chain;
1994 if ( retainedChain )
1996 for ( i = 0; i < retainedChain->
degree; i++ )
1998 fid = retainedChain->
feat[i];
1999 lid = retainedChain->
label[i];
2001 if ( sol[fid] >= 0 )
2002 mLabelPositions.at( sol[fid] )->removeFromIndex( candidates_subsol );
2007 mLabelPositions.at( lid )->insertIntoIndex( candidates_subsol );
2009 tabu_list[fid] = it + tenure;
2010 candidatesUnsorted[fid - borderSize]->
cost = ( lid == -1 ? inactiveCost[sub[fid]] : mLabelPositions.at( lid )->cost() );
2014 cur_cost += retainedChain->
delta;
2018 if ( best_cost - cur_cost >
EPSILON )
2020 best_cost = cur_cost;
2021 memcpy( best_sol, sol,
sizeof(
int ) * subSize );
2023 stop_it = ( it + itwimp > maxit ? maxit : it + itwimp );
2030 memcpy( sol, best_sol,
sizeof(
int ) *subSize );
2032 for ( i = 0; i < probSize; i++ )
2033 delete candidates[i];
2035 delete[] candidates;
2036 delete[] candidatesUnsorted;
2038 for ( i = 0; i < subSize; i++ )
2039 featWrap[sub[i]] = -1;
2045 return initial_cost - best_cost;
2050 QLinkedList<LabelPosition *> *list =
reinterpret_cast< QLinkedList<LabelPosition *>*
>( ctx );
2057 void Problem::check_solution()
2059 int *solution =
new int[nbft];
2069 QLinkedList<LabelPosition *> *list =
new QLinkedList<LabelPosition *>;
2071 candidates_sol->Search( amin, amax,
checkCallback, reinterpret_cast< void * >( list ) );
2075 for ( i = 0; i < nbft; i++ )
2078 if ( sol->s[i] >= 0 )
2082 if ( list->size() != nbActive )
2087 while ( !list->isEmpty() )
2092 solution[probFeatId] = lp->
getId();
2102 int *wrap =
nullptr;
2110 int *wrap = ctx->
wrap;
2135 bool *ok =
new bool[nbft];
2144 context.
wrap =
nullptr;
2146 Chain *retainedChain =
nullptr;
2150 for ( i = 0; i < nbft; i++ )
2168 for ( seed = ( iter + 1 ) % nbft;
2169 ok[
seed] && seed != iter;
2170 seed = ( seed + 1 ) % nbft )
2179 iter = ( iter + 1 ) % nbft;
2180 retainedChain = chain( seed );
2182 if ( retainedChain && retainedChain->
delta < -
EPSILON )
2185 for ( i = 0; i < retainedChain->
degree; i++ )
2187 fid = retainedChain->
feat[i];
2188 lid = retainedChain->
label[i];
2190 if ( sol->s[fid] >= 0 )
2198 candidates->Search( amin, amax,
nokCallback, &context );
2203 if ( sol->s[fid] >= 0 )
2210 sol->cost += retainedChain->
delta;
2234 QList<LabelPosition *> solList;
2241 for ( i = 0; i < nbft; i++ )
2243 if ( sol->s[i] != -1 )
2245 solList.push_back( mLabelPositions.at( sol->s[i] ) );
2247 else if ( returnInactive
2248 || mLabelPositions.at( featStartId[i] )->getFeaturePart()->layer()->displayAll()
2249 || mLabelPositions.at( featStartId[i] )->getFeaturePart()->alwaysShow() )
2251 solList.push_back( mLabelPositions.at( featStartId[i] ) );
2256 if ( returnInactive )
2270 stats->nbObjects = nbft;
2271 stats->nbLabelledObjects = 0;
2273 stats->nbLayers = nbLabelledLayers;
2274 stats->layersNbObjects =
new int[stats->nbLayers];
2275 stats->layersNbLabelledObjects =
new int[stats->nbLayers];
2277 for ( i = 0; i < stats->nbLayers; i++ )
2279 stats->layersName << labelledLayersName[i];
2280 stats->layersNbObjects[i] = 0;
2281 stats->layersNbLabelledObjects[i] = 0;
2286 for ( i = 0; i < nbft; i++ )
2288 lyrName = mLabelPositions.at( featStartId[i] )->getFeaturePart()->feature()->provider()->name();
2290 for ( j = 0; j < stats->nbLayers; j++ )
2292 if ( lyrName == stats->layersName[j] )
2300 stats->layersNbObjects[k]++;
2301 if ( sol->s[i] >= 0 )
2303 stats->layersNbLabelledObjects[k]++;
2304 stats->nbLabelledObjects++;
2316 void Problem::solution_cost()
2327 context.
nbOv = &nbOv;
2328 context.
cost = &sol->cost;
2335 for ( i = 0; i < nbft; i++ )
2337 if ( sol->s[i] == -1 )
2339 sol->
cost += inactiveCost[i];
2345 lp = mLabelPositions.at( sol->s[i] );
bool isInConflict(LabelPosition *ls)
Check whether or not this overlap with another labelPosition.
double popmusic_chain(SubPart *part)
POPMUSIC, chain.
bool borderSizeInc(void *l, void *r)
static bool compareLabelArea(pal::LabelPosition *l1, pal::LabelPosition *l2)
double compute_feature_cost(SubPart *part, int feat_id, int label_id, int *nbOverlap)
void getBoundingBox(double amin[2], double amax[2]) const
Return bounding box - amin: xmin,ymin - amax: xmax,ymax.
int probSize
of features in problem
bool subPartCallback(LabelPosition *lp, void *ctx)
QLinkedList< int > * queue
Thrown when something is added in a Full set.
bool chainCallback(LabelPosition *lp, void *context)
Is slower and best than TABU, worse and faster than TABU_CHAIN.
bool checkCallback(LabelPosition *lp, void *ctx)
struct _nokContext NokContext
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
int getProblemFeatureId() const
struct pal::_elementary_transformation ElemTrans
static bool removeOverlapCallback(LabelPosition *lp, void *ctx)
QLinkedList< ElemTrans * > * currentChain
Is a little bit better than CHAIN but slower.
bool falpCallback1(LabelPosition *lp, void *ctx)
bool updateCandidatesCost(LabelPosition *lp, void *context)
double cost() const
Returns the candidate label position's geographical cost.
RTree< LabelPosition *, double, 2, double > * candidates
void chain_search()
Test with very-large scale neighborhood.
SubPart * subPart(int r, int featseed, int *isIn)
void seed(uint32_t value)
static void sort(void **items, int N, bool(*greater)(void *l, void *r))
Sort an array of pointers.
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
double popmusic_tabu(SubPart *part)
bool nokCallback(LabelPosition *lp, void *context)
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)
void insert(int key, double p)
void popmusic()
popmusic framework
void removeFromIndex(RTree< LabelPosition *, double, 2, double > *index)
double * labelPositionCost
int getId() const
return id
void actualizeCandidateList(int nbOverlap, int *candidateListSize, double, double *candidateFactor, int minCandidateListSize, double growingFactor, int n)
struct pal::_subpart SubPart
int * sub
wrap bw sub feat and main feat
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
double compute_subsolution_cost(SubPart *part, int *s, int *nbOverlap)
int getNumOverlaps() const
void delete_chain(Chain *chain)
QLinkedList< int > * conflicts
int subSize
total # features (prob + border)
Summary statistics of labeling problem.
void ignoreLabel(LabelPosition *lp, PriorityQueue *list, RTree< LabelPosition *, double, 2, double > *candidates)
LabelPosition is a candidate feature label position.
bool decreaseCost(void *tl, void *tr)
bool falpCallback2(LabelPosition *lp, void *ctx)
SearchMethod
Search method to use.
int borderSize
of features bounding the problem
double popmusic_tabu_chain(SubPart *part)
POPMUSIC, Tabu search with chain'.
void init_sol_empty()
Basic initial solution : every feature to -1.
QList< LabelPosition * > getSolution(bool returnInactive)
int seed
first feat in sub part
void decreaseKey(int key)