43 #define VERTEX_CONNECT 0 44 #define VERTEX_TEMPNEIGHBOR 1 45 #define VERTEX_NEIGHBOR 2 46 #define VERTEX_OTHER 3 47 #define STP_RED_CNSNN 25 48 #define STP_RED_ANSMAXCANDS 500 49 #define STP_RED_ANSEXMAXCANDS 50 50 #define STP_RED_ANSMAXNEIGHBORS 25 74 assert(vbase !=
NULL);
75 assert(forbidden !=
NULL);
105 assert(g->
head[e] == tail);
107 if( g->
tail[e] == head )
117 assert(g->
head[e] == head);
119 if( g->
tail[e] == tail )
182 assert(scip !=
NULL);
183 assert(vnoi !=
NULL);
184 assert(vbase !=
NULL);
185 assert(termdist !=
NULL);
186 assert(neighbterms !=
NULL);
188 for( k = 0; k < 4; k++ )
190 if(
SCIPisLT(scip, vnoi[pos].dist, ecost) )
192 neighbterms[nnterms] = vbase[pos];
193 termdist[nnterms++] = vnoi[pos].
dist;
209 const GRAPH* netgraph,
220 for(
int k = 0; k < 4; k++ )
229 int j = nodesorg[netgraph->
head[ne]];
236 for(
int k = 0; k < 4; k++ )
240 for(
int l = 3; l > k; l-- )
242 neighbterms[l] = neighbterms[l - 1];
243 termdist[l] = termdist[l - 1];
246 termdist[k] = necost;
272 assert(scip !=
NULL);
273 assert(vnoi !=
NULL);
274 assert(vbase !=
NULL);
275 assert(termdist !=
NULL);
276 assert(neighbterms !=
NULL);
278 for( k = 0; k < 4; k++ )
280 if(
SCIPisLE(scip, vnoi[pos].dist, ecost) )
282 neighbterms[nnterms] = vbase[pos];
283 termdist[nnterms++] = vnoi[pos].
dist;
296 static int issmaller(
298 const double* pathdist,
299 const double* pathtran,
303 return (
SCIPisLT(scip, pathdist[
a], pathdist[b]) || (!
SCIPisGT(scip, pathdist[a], pathdist[b]) &&
SCIPisLT(scip, pathtran[a], pathtran[b])));
307 const double* pathdist,
308 const double* pathtran,
312 return (
SCIPisGT(scip, pathdist[
a], pathdist[b]) || (!
SCIPisLT(scip, pathdist[a], pathdist[b]) &&
SCIPisGT(scip, pathtran[a], pathtran[b])));
326 const double* pathdist,
327 const double* pathtran)
340 heap[1] = heap[(*count)--];
344 if (islarger(scip, pathdist, pathtran, heap[2], heap[3]))
347 while((c <= (*count)) && islarger(scip, pathdist, pathtran, heap[j], heap[c]))
357 if ((c + 1) <= (*count))
358 if (issmaller(scip, pathdist, pathtran, heap[c + 1], heap[c]))
383 heap[++(*count)] = l;
392 while((j > 1) && (islarger(scip, pathdist, pathtran, heap[c], heap[j])))
412 const double* randarr,
429 assert(scip !=
NULL);
432 assert(start < p->knots);
433 assert(heap !=
NULL);
434 assert(state !=
NULL);
435 assert(pathdist !=
NULL);
436 assert(pathtran !=
NULL);
437 assert(cost !=
NULL);
438 assert(count !=
NULL);
450 for(i = 0; i < p->
knots; i++)
479 k =
nearest(scip, heap, state, count, pathdist, pathtran);
486 if (++done >= p->
grad[start])
501 if ((state[m]) && (p->
mark[m]))
518 tran = pathtran[k] + cost[i];
519 temprand = pathrand[k] + randarr[i];
522 if(
SCIPisGE(scip, pathdist[k], pathtran[k] + cost[i]) )
525 dist = pathtran[k] + cost[i];
527 if(
SCIPisLT(scip, dist, pathdist[m])
528 || (
SCIPisEQ(scip, dist, pathdist[m]) &&
SCIPisLT(scip, tran, pathtran[m])) )
532 pathrand[m] = temprand;
534 correct(scip, heap, state, count, pathdist, pathtran, m);
583 PATH* pathfromsource;
612 path = malloc((
size_t)g->
knots *
sizeof(
PATH*));
614 assert(path !=
NULL);
616 pathfromterm = malloc((
size_t)g->
knots *
sizeof(
PATH));
617 pathfromsource = malloc((
size_t)g->
knots *
sizeof(
PATH));
619 assert(pathfromterm !=
NULL);
620 assert(pathfromsource !=
NULL);
622 pathhops = malloc((
size_t)g->
knots *
sizeof(
PATH));
624 assert(pathhops !=
NULL);
626 distance = malloc((
size_t)g->
knots *
sizeof(
double));
627 radius = malloc((
size_t)g->
knots *
sizeof(
double));
629 assert(distance !=
NULL);
630 assert(radius !=
NULL);
632 hopscost = malloc((
size_t)g->
edges *
sizeof(
double));
634 assert(hopscost !=
NULL);
636 vregion = malloc((
size_t)g->
knots *
sizeof(
int));
638 assert(vregion !=
NULL);
640 heap = malloc((
size_t)g->
knots *
sizeof(
int));
641 state = malloc((
size_t)g->
knots *
sizeof(
int));
643 assert(heap !=
NULL);
644 assert(state !=
NULL);
647 pred = malloc((
size_t)g->
edges *
sizeof(
int));
648 minArc1 = malloc((
size_t)g->
knots *
sizeof(
int));
649 minArc2 = malloc((
size_t)g->
knots *
sizeof(
int));
650 terms = malloc((
size_t)g->
terms *
sizeof(
int));
653 for(i = 0; i < g->
knots; i++)
657 terms[termcount] = i;
682 voronoi_term(g, g->
cost, distance, radius, pathfromterm, vregion, heap, state, pred, 1);
692 knotoffset = rand() % KNOTFREQ;
694 for(i = 0; i < g->
knots; i++)
704 if( g->
knots > KNOTLIMIT && i % KNOTFREQ != knotoffset )
715 antiedgeexists =
FALSE;
729 if (g->
cost[e] < min1)
732 shortarctail = g->
tail[e];
738 if(
LT(pathfromsource[g->
tail[e]].hops, minhops) )
739 minhops = pathfromsource[g->
tail[e]].hops;
742 antiedgeexists =
TRUE;
749 if (
LT(min1,
FARAWAY) &&
LE(pathfromsource[shortarctail].dist + min1, min2))
751 assert(shortarc >= 0);
752 assert(shortarctail >= 0);
761 if( antiedgeexists ==
TRUE )
807 if( vregion[i] != vregion[j] )
809 if( minArc1[vregion[i]] < 0 )
810 minArc1[vregion[i]] = e;
811 else if( g->
cost[e] < g->
cost[minArc1[vregion[i]]] )
813 minArc2[vregion[i]] = minArc1[vregion[i]];
814 minArc1[vregion[i]] = e;
823 for( k = 0; k < termcount; k++ )
825 assert(terms[k] >= 0 && terms[k] < g->
knots);
827 if( minArc1[terms[k]] >= 0 && minArc2[terms[k]] >= 0 && pathfromsource[g->
tail[minArc1[terms[k]]]].
dist 828 + g->
cost[minArc1[terms[k]]] + pathfromterm[g->
head[minArc1[terms[k]]]].
dist < g->
cost[minArc2[terms[k]]] )
830 e = minArc1[terms[k]];
841 *fixed += g->
cost[e];
862 free(pathfromsource);
872 * C. W. Duin and A. Volganant
874 *
"An Edge Elimination Test for the Steiner Problem in Graphs" 876 * Operations Research Letters 8, (1989), 79-83
878 * Special Distance Test
911 assert(heap !=
NULL);
912 assert(state !=
NULL);
916 assert(sddist !=
NULL);
917 assert(sdtrans !=
NULL);
921 assert(cost !=
NULL);
923 assert(knotexamined !=
NULL);
927 stalltime = timelimit*0.1;
929 for(i = 0; i < g->
knots; i++)
934 random[e] = (double)(rand() % 512);
935 cost[e] = g->
cost[e] * 1000.0 + random[e];
940 if( g->
knots > KNOTLIMIT )
946 knotoffset = rand() % KNOTFREQ;
948 }
while( g->
knots > KNOTLIMIT && knotexamined[knotoffset] >= 0 && i < 50 );
949 knotexamined[knotoffset]++;
953 for(i = 0; i < g->
knots; i++)
955 if( i % 100 == 0 && elimins == 0 &&
SCIPgetTotalTime(scip) - redstarttime > stalltime)
967 if( g->
knots > KNOTLIMIT && i % KNOTFREQ != knotoffset )
971 if ( (g->
stp_type == STP_PRIZE_COLLECTING || g->
stp_type == STP_ROOTED_PRIZE_COLLECTING
982 compute_sd(g, i, cost, random, heap, state, &count, sddist, sdtrans, sdrand);
994 assert(g->
tail[e] == i);
999 &&
LT(sddist[g->
head[e]] - sdrand[g->
head[e]], cost[e] - random[e]))
1001 SCIPindexListNodeFree(&((g->
ancestors)[e]));
1038 int bridgeedge = -1;
1039 unsigned misses = 0;
1041 assert(g->
mark[candvertex]);
1042 assert(candvertex != g->
source);
1047 if( !marked[g->
head[e2]] )
1057 if( misses == 0 &&
SCIPisLE(scip, g->
prize[candvertex], min) )
1059 (*count) += g->
grad[candvertex];
1064 marked[candvertex] =
FALSE;
1066 else if( misses == 1 )
1069 const int neighbor = g->
head[bridgeedge];
1076 const int head = g->
head[e3];
1085 (*count) += g->
grad[candvertex] + g->
grad[neighbor] - 1;
1093 marked[candvertex] =
FALSE;
1094 marked[neighbor] =
FALSE;
1128 int neighbterms1[4];
1129 int neighbterms2[4];
1153 assert(scip !=
NULL);
1154 assert(heap !=
NULL);
1155 assert(vnoi !=
NULL);
1156 assert(state !=
NULL);
1157 assert(vbase !=
NULL);
1158 assert(nelims !=
NULL);
1159 assert(nodesid !=
NULL);
1160 assert(mstsdist !=
NULL);
1161 assert(nodesorg !=
NULL);
1162 assert(edgepreds !=
NULL);
1163 assert(forbidden !=
NULL);
1169 maxnedges = MIN(nedges, (nterms - 1) * nterms);
1184 for( k = 0; k <
nnodes; k++ )
1200 for( k = 0; k < nedges; k++ )
1202 forbidden[k] =
FALSE;
1206 assert(netgraph->
knots == j);
1207 assert(netgraph->
knots == nterms);
1209 for( k = 0; k <
nnodes; k++ )
1211 if( g->
grad[k] == 0 )
1219 if( i != vbase[g->
head[e]] )
1221 i2 = vbase[g->
head[e]];
1230 if( netgraph->
head[ne] == id2 )
1240 assert(netgraph->
tail[ne] == id1);
1241 assert(netgraph->
head[ne] == id2);
1246 netgraph->
cost[ne] = ecost;
1252 assert(ne <= maxnedges);
1257 edgepreds[netgraph->
edges] = e;
1262 assert(netgraph->
edges <= maxnedges);
1278 for( k = 1; k < netgraph->
knots; k++ )
1280 assert(mst[k].edge != -1);
1281 assert((
int) edgepreds[mst[k].edge] != -1);
1282 assert((
int) edgepreds[
flipedge(mst[k].edge)] != -1);
1284 e = (int) edgepreds[mst[k].edge];
1286 assert(vbase[g->
tail[e]] == nodesorg[k] || vbase[g->
head[e]] == nodesorg[k]);
1290 forbidden[e] =
TRUE;
1296 for( i = 0; i <
nnodes; i++ )
1298 if( g->
grad[i] <= 0 )
1305 neighbterms1[0] = i;
1315 if( i2 < i || !g->mark[i2] )
1323 nnterms1 =
getlecloseterms(scip, vnoi, termdist1, ecost, vbase, neighbterms1, i, nnodes);
1333 neighbterms2[0] = i2;
1338 nnterms2 =
getlecloseterms(scip, vnoi, termdist2, ecost, vbase, neighbterms2, i2, nnodes);
1344 for( j = 0; j < nnterms1; j++ )
1350 tj = neighbterms1[j];
1354 for( k = 0; k < nnterms2; k++ )
1356 tk = neighbterms2[k];
1364 if(
SCIPisGE(scip, termdist1[j], termdist2[k] ) )
1365 dist = termdist1[j];
1367 dist = termdist2[k];
1369 assert(
SCIPisGE(scip, ecost, dist));
1372 if( !
sddeltable(scip, g, vnoi, vbase, forbidden, j, k, i, i2, e, nnodes ) )
1399 assert(netgraph->
head[ne] == l);
1401 l = netgraph->
tail[ne];
1404 dist = netgraph->
cost[ne];
1425 l = netgraph->
tail[ne];
1428 dist = netgraph->
cost[ne];
1430 if( mstsdist[l] >= 0 )
1432 if(
SCIPisGT(scip, mstsdist[l], dist) )
1447 l = netgraph->
tail[ne];
1455 if(
SCIPisLT(scip, dist, termdist1[j]) )
1456 dist = termdist1[j];
1458 if(
SCIPisLT(scip, dist, termdist2[k]) )
1459 dist = termdist2[k];
1464 if( !(
sddeltable(scip, g, vnoi, vbase, forbidden, j, k, i, i2, e, nnodes)) )
1467 assert(
SCIPisGE(scip, ecost, termdist1[j]));
1468 assert(
SCIPisGE(scip, ecost, termdist2[k]));
1486 SCIP_CALL(
reduce_bdr(scip, g, netgraph, mst, vnoi, mstsdist, termdist1, termdist2, vbase, nodesid, neighbterms1, neighbterms2, nelims) );
1514 int neighbterms1[4];
1515 int neighbterms2[4];
1519 const int root = g->
source;
1522 const int nedges = g->
edges;
1525 assert(heap !=
NULL);
1526 assert(vnoi !=
NULL);
1527 assert(state !=
NULL);
1528 assert(vbase !=
NULL);
1529 assert(scip !=
NULL);
1530 assert(nelims !=
NULL);
1531 assert(nodesid !=
NULL);
1532 assert(nodesorg !=
NULL);
1543 if( longedges <= longtermsq )
1546 maxnedges = ((nterms - 1) * nterms);
1558 for(
int k = 0; k < 4; k++ )
1565 for(
int k = 0; k <
nnodes; k++ )
1569 assert(g->
grad[k] > 0);
1580 assert(netgraph->
knots == j);
1581 assert(netgraph->
knots == nterms);
1584 for(
int k = 0; k <
nnodes; k++ )
1596 if( i != vbase[g->
head[e]] )
1600 const int i2 = vbase[g->
head[e]];
1605 assert(nodesid[i] >= 0);
1606 assert(nodesid[i2] >= 0);
1609 if( netgraph->
head[ne] == nodesid[i2] )
1618 assert(netgraph->
head[ne] == nodesid[i2]);
1619 assert(netgraph->
tail[ne] == nodesid[i]);
1623 netgraph->
cost[ne] = ecost;
1625 assert(ne <= maxnedges);
1630 graph_edge_add(scip, netgraph, nodesid[i], nodesid[i2], ecost, ecost);
1631 assert(netgraph->
edges <= maxnedges);
1641 for(
int i = 0; i <
nnodes; i++ )
1654 const int i2 = g->
head[e];
1664 nnterms1 =
getcloseterms2term(scip, g, netgraph, termdist1, ecost, neighbterms1, nodesid, nodesorg, i);
1666 nnterms1 =
getcloseterms(scip, vnoi, termdist1, ecost, vbase, neighbterms1, i, nnodes);
1671 nnterms1 =
getcloseterms(scip, vnoi, termdist1, ecost, vbase, neighbterms1, i, nnodes);
1680 nnterms2 =
getcloseterms2term(scip, g, netgraph, termdist2, ecost, neighbterms2, nodesid, nodesorg, i2);
1682 nnterms2 =
getcloseterms(scip, vnoi, termdist2, ecost, vbase, neighbterms2, i2, nnodes);
1687 nnterms2 =
getcloseterms(scip, vnoi, termdist2, ecost, vbase, neighbterms2, i2, nnodes);
1694 for( j = 0; j < nnterms1; j++ )
1702 tj = neighbterms1[j];
1707 for(
int k = 0; k < nnterms2; k++ )
1709 const int tk = neighbterms2[k];
1716 if(
SCIPisGT(scip, ecost, termdist1[j] + termdist2[k] - g->
prize[tj]) || tj == root )
1732 if( netgraph->
head[e2] == nodesid[tk] )
1734 necost = netgraph->
cost[e2];
1739 for(
int l = 0; l < 4; l++ )
1743 if( vbase[pos] == tk &&
SCIPisLT(scip, vnoi[pos].dist, necost) )
1745 necost = vnoi[pos].
dist;
1752 &&
SCIPisGT(scip, ecost, necost + termdist1[j] - g->
prize[tj])
1753 &&
SCIPisGT(scip, ecost, necost + termdist2[k] - g->
prize[tk])
1754 &&
SCIPisGT(scip, ecost, necost + termdist1[j] + termdist2[k] - g->
prize[tj] - g->
prize[tk]) )
1812 assert(scip !=
NULL);
1814 assert(netgraph !=
NULL);
1815 assert(mst !=
NULL);
1816 assert(mstsdist !=
NULL);
1817 assert(termdist1 !=
NULL);
1818 assert(termdist2 !=
NULL);
1819 assert(neighbterms1 !=
NULL);
1820 assert(neighbterms2 !=
NULL);
1825 if( sd_initial >= 0.0 )
1833 if( g->
head[e] == i2 )
1835 if( g->
cost[e] < sd )
1846 neighbterms1[0] = i;
1850 nnterms1 =
getcloseterms(scip, vnoi, termdist1, sd, vbase, neighbterms1, i, nnodes);
1861 neighbterms2[0] = i2;
1866 nnterms2 =
getcloseterms(scip, vnoi, termdist2, sd, vbase, neighbterms2, i2, nnodes);
1872 for( j = 0; j < nnterms1; j++ )
1874 tj = neighbterms1[j];
1876 for( k = 0; k < nnterms2; k++ )
1878 tk = neighbterms2[k];
1883 if(
SCIPisGT(scip, termdist1[j], termdist2[k]) )
1908 assert(netgraph->
head[ne] == l);
1909 l = netgraph->
tail[ne];
1911 dist = netgraph->
cost[ne];
1930 l = netgraph->
tail[ne];
1932 dist = netgraph->
cost[ne];
1934 if( mstsdist[l] >= 0 )
1936 if(
SCIPisGT(scip, mstsdist[l], dist) )
1950 l = netgraph->
tail[ne];
2000 assert(scip !=
NULL);
2001 assert(pathtail !=
NULL);
2002 assert(pathhead !=
NULL);
2003 assert(heap !=
NULL);
2004 assert(statetail !=
NULL);
2005 assert(statehead !=
NULL);
2006 assert(memlbltail !=
NULL);
2007 assert(memlblhead !=
NULL);
2008 assert(sdist !=
NULL);
2013 graph_sdPaths(scip, g, pathtail, g->
cost, distlimit, heap, statetail, memlbltail, &nlbltail, i, i2, limit);
2016 graph_sdPaths(scip, g, pathhead, g->
cost, distlimit, heap, statehead, memlblhead, &nlblhead, i2, i, limit);
2020 if( statetail[i2] !=
UNKNOWN )
2022 sd = pathtail[i2].
dist;
2027 sd = pathhead[i].
dist;
2032 for( k = 0; k < nlbltail; k++ )
2035 assert(statetail[l] !=
UNKNOWN);
2043 if(
SCIPisLT(scip, dist, pathhead[l].dist) )
2044 dist = pathhead[l].
dist;
2045 if(
SCIPisLT(scip, dist, pathtail[l].dist) )
2046 dist = pathtail[l].
dist;
2047 if( pcmw &&
SCIPisLT(scip, dist, pathhead[l].dist + pathtail[l].dist - g->
prize[l]) )
2054 if( mw && l != i && l != i2 )
2059 dist = pathhead[l].
dist + pathtail[l].
dist;
2070 for( k = 0; k < nlblhead; k++ )
2079 for( k = 0; k <
nnodes; k++ )
2081 assert(statetail[k] ==
UNKNOWN);
2082 assert(pathtail[k].dist ==
FARAWAY);
2083 assert(pathtail[k].edge ==
UNKNOWN);
2084 assert(statehead[k] ==
UNKNOWN);
2085 assert(pathhead[k].dist ==
FARAWAY);
2086 assert(pathhead[k].edge ==
UNKNOWN);
2094 if( g->
head[e] == i2 )
2122 int* pathmaxnodetail,
2123 int* pathmaxnodehead,
2137 assert(scip !=
NULL);
2138 assert(pathtail !=
NULL);
2139 assert(pathhead !=
NULL);
2140 assert(heap !=
NULL);
2141 assert(statetail !=
NULL);
2142 assert(statehead !=
NULL);
2143 assert(memlbltail !=
NULL);
2144 assert(memlblhead !=
NULL);
2145 assert(pathmaxnodetail !=
NULL);
2146 assert(pathmaxnodehead !=
NULL);
2147 assert(sdist !=
NULL);
2149 graph_path_PcMwSd(scip, g, pathtail, g->
cost, distlimit, pathmaxnodetail, heap, statetail,
NULL, memlbltail, &nlbltail, i, i2, limit);
2150 graph_path_PcMwSd(scip, g, pathhead, g->
cost, distlimit, pathmaxnodehead, heap, statehead, statetail, memlblhead, &nlblhead, i2, i, limit);
2155 for(
int k = 0; k < nlbltail; k++ )
2157 const int l = memlbltail[k];
2158 assert(statetail[l] !=
UNKNOWN);
2163 const int tailmaxterm = pathmaxnodetail[l];
2164 const int headmaxterm = pathmaxnodehead[l];
2168 assert(tailmaxterm != i && headmaxterm != i);
2169 assert(tailmaxterm != i2 && headmaxterm != i2);
2172 if( tailmaxterm >= 0 || headmaxterm >= 0 )
2174 if( tailmaxterm == headmaxterm )
2176 assert(tailmaxterm == l);
2180 pathhead[headmaxterm].
dist,
2181 pathtail[tailmaxterm].
dist,
2186 else if( tailmaxterm >= 0 && headmaxterm >= 0 )
2191 assert(tailmaxterm != headmaxterm);
2197 pathhead[headmaxterm].
dist,
2198 pathtail[tailmaxterm].
dist,
2199 distl2tailmax + distl2headmax,
2200 distl2tailmax + pathhead[l].
dist - g->
prize[headmaxterm],
2201 distl2headmax + pathtail[l].
dist - g->
prize[tailmaxterm],
2206 else if( tailmaxterm >= 0 )
2210 assert(headmaxterm < 0);
2214 pathtail[tailmaxterm].
dist,
2215 distl2tailmax + pathhead[l].
dist,
2220 else if( headmaxterm >= 0 )
2224 assert(tailmaxterm < 0);
2228 pathhead[headmaxterm].
dist,
2229 distl2headmax + pathtail[l].
dist,
2237 dist = pathhead[l].
dist + pathtail[l].
dist;
2258 for(
int k = 0; k < nlbltail; k++ )
2260 const int l = memlbltail[k];
2264 pathmaxnodetail[l] = -1;
2267 for(
int k = 0; k < nlblhead; k++ )
2269 const int l = memlblhead[k];
2273 pathmaxnodehead[l] = -1;
2276 for(
int k = 0; k <
nnodes; k++ )
2278 assert(statetail[k] ==
UNKNOWN);
2279 assert(pathtail[k].dist ==
FARAWAY);
2280 assert(pathtail[k].edge ==
UNKNOWN);
2281 assert(statehead[k] ==
UNKNOWN);
2282 assert(pathhead[k].dist ==
FARAWAY);
2283 assert(pathhead[k].edge ==
UNKNOWN);
2284 assert(pathmaxnodehead[k] == -1);
2285 assert(pathmaxnodetail[k] == -1);
2289 for(
int e = g->
outbeg[i], count = 0; (count++ <= limit) && (e !=
EAT_LAST); e = g->
oeat[e] )
2291 if( g->
head[e] == i2 )
2295 else if( sd > g->
cost[e] )
2336 assert(scip !=
NULL);
2337 assert(pathtail !=
NULL);
2338 assert(pathhead !=
NULL);
2339 assert(heap !=
NULL);
2340 assert(statetail !=
NULL);
2341 assert(statehead !=
NULL);
2342 assert(memlbltail !=
NULL);
2343 assert(memlblhead !=
NULL);
2344 assert(nelims !=
NULL);
2350 for( i = 0; i <
nnodes; i++ )
2363 for( e = 0; e < nedges; e++ )
2367 for( i = 0; i <
nnodes; i++ )
2379 assert(g->
mark[i2]);
2382 graph_sdPaths(scip, g, pathtail, g->
cost, g->
cost[e], heap, statetail, memlbltail, &nlbltail, i, i2, limit);
2385 graph_sdPaths(scip, g, pathhead, costrev, g->
cost[e], heap, statehead, memlblhead, &nlblhead, i2, i, limit);
2389 if( statetail[i2] !=
UNKNOWN )
2391 sdist = pathtail[i2].
dist;
2394 if( statehead[i] !=
UNKNOWN &&
SCIPisGT(scip, sdist, pathhead[i].dist) )
2396 sdist = pathhead[i].
dist;
2401 for( k = 0; k < nlbltail; k++ )
2405 assert(statetail[l] !=
UNKNOWN);
2411 if(
SCIPisGT(scip, sdist, pathhead[l].dist + pathtail[l].dist) )
2412 sdist = pathhead[l].
dist + pathtail[l].
dist;
2420 for( k = 0; k < nlblhead; k++ )
2429 for( k = 0; k <
nnodes; k++ )
2431 assert(statetail[k] ==
UNKNOWN);
2432 assert(pathtail[k].dist ==
FARAWAY);
2433 assert(pathtail[k].edge ==
UNKNOWN);
2434 assert(statehead[k] ==
UNKNOWN);
2435 assert(pathhead[k].dist ==
FARAWAY);
2436 assert(pathhead[k].edge ==
UNKNOWN);
2475 int* pathmaxnodetail =
NULL;
2476 int* pathmaxnodehead =
NULL;
2482 assert(scip !=
NULL);
2483 assert(pathtail !=
NULL);
2484 assert(pathhead !=
NULL);
2485 assert(heap !=
NULL);
2486 assert(statetail !=
NULL);
2487 assert(statehead !=
NULL);
2488 assert(memlbltail !=
NULL);
2489 assert(memlblhead !=
NULL);
2490 assert(nelims !=
NULL);
2499 for(
int i = 0; i <
nnodes; i++ )
2501 pathmaxnodetail[i] = -1;
2502 pathmaxnodehead[i] = -1;
2507 for(
int i = 0; i <
nnodes; i++ )
2511 for(
int i = 0; i <
nnodes; i++ )
2522 for(
int i = 0; i <
nnodes; i++ )
2533 const int i2 = g->
head[e];
2534 const int enext = g->
oeat[e];
2540 if( i2 < i || !g->mark[i2] )
2550 graph_path_PcMwSd(scip, g, pathtail, g->
cost, ecost, pathmaxnodetail, heap, statetail,
NULL, memlbltail, &nlbltail, i, i2, limit);
2551 graph_path_PcMwSd(scip, g, pathhead, g->
cost, ecost, pathmaxnodehead, heap, statehead, statetail, memlblhead, &nlblhead, i2, i, limit);
2555 graph_sdPaths(scip, g, pathtail, g->
cost, ecost, heap, statetail, memlbltail, &nlbltail, i, i2, limit);
2556 graph_sdPaths(scip, g, pathhead, g->
cost, ecost, heap, statehead, memlblhead, &nlblhead, i2, i, limit);
2562 for(
int k = 0; k < nlbltail && !deletable; k++ )
2564 const int l = memlbltail[k];
2567 assert(statetail[l] !=
UNKNOWN);
2576 const int tailmaxterm = pathmaxnodetail[l];
2577 const int headmaxterm = pathmaxnodehead[l];
2579 assert(tailmaxterm != i && headmaxterm != i);
2580 assert(tailmaxterm != i2 && headmaxterm != i2);
2583 if( tailmaxterm >= 0 || headmaxterm >= 0 )
2585 if( tailmaxterm == headmaxterm )
2587 assert(tailmaxterm == l);
2589 assert(
SCIPisGE(scip, ecost, pathhead[headmaxterm].dist) &&
SCIPisGE(scip, ecost, pathtail[tailmaxterm].dist));
2591 if(
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist - g->
prize[l]) )
2597 else if( tailmaxterm >= 0 && headmaxterm >= 0 )
2602 assert(tailmaxterm != headmaxterm);
2606 assert(
SCIPisGE(scip, ecost, pathhead[headmaxterm].dist) &&
SCIPisGE(scip, ecost, pathtail[tailmaxterm].dist));
2608 if(
SCIPisGE(scip, ecost, distl2tailmax + distl2headmax)
2609 &&
SCIPisGE(scip, ecost, distl2tailmax + pathhead[l].dist - g->
prize[headmaxterm])
2610 &&
SCIPisGE(scip, ecost, distl2headmax + pathtail[l].dist - g->
prize[tailmaxterm])
2611 &&
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist - g->
prize[tailmaxterm] - g->
prize[headmaxterm]) )
2617 else if( tailmaxterm >= 0 )
2621 assert(headmaxterm < 0);
2622 assert(
SCIPisGE(scip, ecost, pathtail[tailmaxterm].dist));
2625 if(
SCIPisGE(scip, ecost, distl2tailmax + pathhead[l].dist)
2626 &&
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist - g->
prize[tailmaxterm]) )
2632 else if( headmaxterm >= 0 )
2636 assert(tailmaxterm < 0);
2637 assert(
SCIPisGE(scip, ecost, pathhead[headmaxterm].dist));
2640 if(
SCIPisGE(scip, ecost, distl2headmax + pathtail[l].dist)
2641 &&
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist - g->
prize[headmaxterm]) )
2648 else if(
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist) )
2655 if(
SCIPisGE(scip, ecost, pathhead[l].dist) &&
SCIPisGE(scip, ecost, pathtail[l].dist)
2656 &&
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist - g->
prize[l]) )
2664 if(
SCIPisGE(scip, ecost, pathhead[l].dist) &&
SCIPisGE(scip, ecost, pathtail[l].dist) )
2668 if( pc &&
SCIPisLT(scip, ecost, pathhead[l].dist + pathtail[l].dist - g->
prize[l]) )
2675 if(
SCIPisGE(scip, ecost, pathhead[l].dist + pathtail[l].dist) )
2684 for(
int k = 0; k < nlbltail; k++ )
2686 const int l = memlbltail[k];
2691 pathmaxnodetail[l] = -1;
2694 for(
int k = 0; k < nlblhead; k++ )
2696 const int l = memlblhead[k];
2701 pathmaxnodehead[l] = -1;
2705 for(
int k = 0; k <
nnodes; k++ )
2707 assert(statetail[k] ==
UNKNOWN);
2708 assert(pathtail[k].dist ==
FARAWAY);
2709 assert(pathtail[k].edge ==
UNKNOWN);
2710 assert(statehead[k] ==
UNKNOWN);
2711 assert(pathhead[k].dist ==
FARAWAY);
2712 assert(pathhead[k].edge ==
UNKNOWN);
2715 assert(pathmaxnodetail[k] == -1);
2716 assert(pathmaxnodehead[k] == -1);
2743 #define STP_BDR_MAXDEGREE 4 2744 #define STP_BDR_MAXDNEDGES 6 2775 assert(netgraph !=
NULL);
2776 assert(netmst !=
NULL);
2785 for(
int k = 0; k < STP_BDR_MAXDEGREE - 1; k++ )
2786 for(
int k2 = STP_BDR_MAXDEGREE - 1; k2 >= k + 1; k2-- )
2800 for(
int i = 0; i <
nnodes; i++ )
2805 for(
int i = 0; i <
nnodes; i++ )
2817 ecost[k] = g->
cost[e];
2818 adjvert[k++] = g->
head[e];
2821 assert(k == degree);
2826 csum = ecost[0] + ecost[1] + ecost[2];
2828 sd[0] =
getRSD(scip, g, netgraph, netmst, vnoi, mstsdist, termdist1, termdist2, ecost[0] + ecost[1], vbase, nodesid, neighbterms1, neighbterms2, adjvert[0],
2830 sd[1] =
getRSD(scip, g, netgraph, netmst, vnoi, mstsdist, termdist1, termdist2, ecost[1] + ecost[2], vbase, nodesid, neighbterms1, neighbterms2, adjvert[1],
2832 sd[2] =
getRSD(scip, g, netgraph, netmst, vnoi, mstsdist, termdist1, termdist2, ecost[2] + ecost[0], vbase, nodesid, neighbterms1, neighbterms2, adjvert[2],
2835 if( sd[0] + sd[1] <= csum || sd[0] + sd[2] <= csum || sd[1] + sd[2] <= csum )
2846 assert(g->
grad[i] == 0);
2848 SCIPdebugMessage(
"BD3-R Reduction: %f %f %f csum: %f\n ", sd[0], sd[1], sd[2], csum);
2853 else if( degree == 4 )
2855 for( k = 0; k < 4; k++ )
2860 const int k2 = auxg->
head[e];
2863 auxg->
cost[e] =
getRSD(scip, g, netgraph, netmst, vnoi, mstsdist, termdist1, termdist2, ecost[k] + ecost[k2], vbase, nodesid, neighbterms1,
2864 neighbterms2, adjvert[k], adjvert[k2], 200);
2870 for(
int l = 0; l < 4; l++ )
2878 for(
int l = 1; l < 4; l++ )
2879 assert(mst[l].dist !=
UNKNOWN);
2882 for(
int l = 1; l < 4; l++ )
2883 mstcost += mst[l].dist;
2886 csum = ecost[0] + ecost[1] + ecost[2] + ecost[3];
2888 if( csum >= mstcost )
2891 for( k = 0; k < 4; k++ )
2899 for(
int l = 1; l < 4; l++ )
2901 mstcost += mst[l].
dist;
2906 for(
int l = 2; l < 4; l++ )
2907 mstcost += mst[l].dist;
2913 if( csum < mstcost )
2925 for( k = 0; k < 3; k++ )
2929 const int k2 = auxg->
head[e];
2931 cutoffs[edgecount++] = auxg->
cost[e];
2952 #define STP_BD_MAXDEGREE 4 2953 #define STP_BD_MAXDNEDGES 6 2983 int* pathmaxnodetail =
NULL;
2984 int* pathmaxnodehead =
NULL;
2991 assert(scip !=
NULL);
2993 assert(heap !=
NULL);
2994 assert(nelims !=
NULL);
3003 for(
int k2 = STP_BD_MAXDEGREE - 1; k2 >= k + 1; k2-- )
3021 for(
int i = 0; i <
nnodes; i++ )
3025 for(
int i = 0; i <
nnodes; i++ )
3035 pathmaxnodetail[i] = -1;
3036 pathmaxnodehead[i] = -1;
3042 for(
int i = 0; i <
nnodes; i++ )
3051 ecost[edgecount] = g->
cost[e];
3052 adjvert[edgecount++] = g->
head[e];
3058 const SCIP_Real csum = ecost[0] + ecost[1] + ecost[2];
3060 assert(edgecount == 3);
3065 reduce_getSdPcMw(scip, g, pathtail, pathhead, &(sd[0]), csum, heap, statetail, statehead, memlbltail, memlblhead,
3066 pathmaxnodetail, pathmaxnodehead, adjvert[0], adjvert[1], limit));
3068 reduce_getSdPcMw(scip, g, pathtail, pathhead, &(sd[1]), csum, heap, statetail, statehead, memlbltail, memlblhead,
3069 pathmaxnodetail, pathmaxnodehead, adjvert[1], adjvert[2], limit));
3071 reduce_getSdPcMw(scip, g, pathtail, pathhead, &(sd[2]), csum, heap, statetail, statehead, memlbltail, memlblhead,
3072 pathmaxnodetail, pathmaxnodehead, adjvert[2], adjvert[0], limit));
3077 reduce_getSd(scip, g, pathtail, pathhead, &(sd[0]), csum, heap, statetail, statehead, memlbltail, memlblhead, adjvert[0], adjvert[1], limit, pc,
FALSE));
3079 reduce_getSd(scip, g, pathtail, pathhead, &(sd[1]), csum, heap, statetail, statehead, memlbltail, memlblhead, adjvert[1], adjvert[2], limit, pc,
FALSE));
3081 reduce_getSd(scip, g, pathtail, pathhead, &(sd[2]), csum, heap, statetail, statehead, memlbltail, memlblhead, adjvert[2], adjvert[0], limit, pc,
FALSE));
3084 if(
SCIPisLE(scip, sd[0] + sd[1], csum) ||
SCIPisLE(scip, sd[0] + sd[2], csum) ||
SCIPisLE(scip, sd[1] + sd[2], csum) )
3094 assert(g->
grad[i] == 0);
3096 SCIPdebugMessage(
"BD3 Reduction: %f %f %f csum: %f\n ", sd[0], sd[1], sd[2], csum);
3101 else if( degree == 4 )
3104 SCIP_Real csum = ecost[0] + ecost[1] + ecost[2] + ecost[3];
3107 assert(edgecount == 4);
3109 for( k = 0; k < 4; k++ )
3114 const int k2 = auxg->
head[e];
3120 reduce_getSdPcMw(scip, g, pathtail, pathhead, &(s1), csum, heap, statetail, statehead, memlbltail, memlblhead,
3121 pathmaxnodetail, pathmaxnodehead, adjvert[k], adjvert[k2], limit));
3124 reduce_getSd(scip, g, pathtail, pathhead, &(s1), csum, heap, statetail, statehead, memlbltail, memlblhead, adjvert[k], adjvert[k2], limit, pc,
FALSE));
3132 for(
int l = 0; l < 4; l++ )
3140 for(
int l = 1; l < 4; l++ )
3142 assert(mst[l].dist !=
UNKNOWN);
3143 mstcost += mst[l].
dist;
3147 if(
SCIPisGE(scip, csum, mstcost) )
3150 for( k = 0; k < 4; k++ )
3158 for(
int l = 1; l < 4; l++ )
3160 mstcost += mst[l].
dist;
3165 for(
int l = 2; l < 4; l++ )
3166 mstcost += mst[l].dist;
3171 if(
SCIPisLT(scip, csum - ecost[k], mstcost) )
3181 for( k = 0; k < 3; k++ )
3185 const int k2 = auxg->
head[e];
3187 cutoffs[edgecount++] = auxg->
cost[e];
3236 int* pathmaxnodetail =
NULL;
3237 int* pathmaxnodehead =
NULL;
3239 const int nedges = g->
edges;
3244 assert(scip !=
NULL);
3246 assert(heap !=
NULL);
3247 assert(nelims !=
NULL);
3262 for(
int k2 = STP_BD_MAXDEGREE - 1; k2 >= k + 1; k2-- )
3277 for(
int i = 0; i <
nnodes; i++ )
3281 for(
int i = 0; i <
nnodes; i++ )
3291 pathmaxnodetail[i] = -1;
3292 pathmaxnodehead[i] = -1;
3298 for(
int edge = 0; edge < nedges; edge += 2 )
3307 const int tail = g->
tail[edge];
3308 const int head = g->
head[edge];
3313 assert(tail >= 0 && head >= 0);
3316 if( g->
grad[tail] != 3 || g->
grad[head] != 3 )
3325 if( g->
head[e] == head )
3327 outedge[edgecount] = e;
3328 ecost[edgecount] = g->
cost[e];
3329 adjvert[edgecount++] = g->
head[e];
3334 if( g->
head[e] == tail )
3336 outedge[edgecount] = e;
3337 ecost[edgecount] = g->
cost[e];
3338 adjvert[edgecount++] = g->
head[e];
3341 assert(edgecount == degree);
3346 for(
int i = 0; i < degree - 1; i++ )
3347 for(
int j = i + 1; j < degree; j++ )
3348 if( adjvert[i] == adjvert[j] && adjvert[j] >= 0 )
3350 adjvert[j] = -adjvert[j] - 1;
3360 assert(g->
mark[head] && g->
mark[tail]);
3365 csum = ecost[0] + ecost[1] + ecost[2] + ecost[3];
3368 for(
int k = 0; k < degree - 1 && success; k++ )
3372 const int k2 = auxg->
head[e];
3378 SCIP_CALL(
reduce_getSdPcMw(scip, g, pathtail, pathhead, &(s1), csum, heap, statetail, statehead, memlbltail, memlblhead,
3379 pathmaxnodetail, pathmaxnodehead, adjvert[k], adjvert[k2], limit) );
3381 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &(s1), csum, heap, statetail, statehead, memlbltail, memlblhead,
3382 adjvert[k], adjvert[k2], limit, pc,
FALSE) );
3386 if( g->
tail[outedge[k]] != g->
tail[outedge[k2]] )
3388 const SCIP_Real innercost = ecost[k] + ecost[k2] + edgecost;
3390 if(
SCIPisGT(scip, s1, innercost) )
3406 for(
int l = 0; l < 4; l++ )
3414 for(
int l = 1; l < 4; l++ )
3416 assert(mst[l].dist !=
UNKNOWN);
3417 mstcost += mst[l].
dist;
3420 success = (success &&
SCIPisGE(scip, csum, mstcost));
3426 for(
int k = 0; k < degree; k++ )
3428 assert(auxg->
mark[k]);
3436 for(
int l = 1; l < 4; l++ )
3438 mstcost += mst[l].
dist;
3443 for(
int l = 2; l < 4; l++ )
3444 mstcost += mst[l].dist;
3449 if(
SCIPisLT(scip, csum - ecost[k], mstcost) )
3522 assert(vnoi !=
NULL);
3523 assert(heap !=
NULL);
3524 assert(state !=
NULL);
3525 assert(vbase !=
NULL);
3526 assert(vrnodes !=
NULL);
3527 assert(visited !=
NULL);
3542 for( i = 0; i <
nnodes; i++ )
3548 for( j = 0; j <
nnodes; j++ )
3551 forbidden[j] =
FALSE;
3554 for( i = 0; i <
nnodes; i++ )
3583 if( !visited[j] && k == i )
3586 vrnodes[vrcount++] = j;
3599 mincost3 = mincost2;
3600 mincost2 = g->
cost[minedge];
3603 else if(
SCIPisLE(scip, cost, mincost2) )
3605 mincost3 = mincost2;
3606 mincost2 = g->
cost[e];
3608 else if(
SCIPisLT(scip, cost, mincost3) )
3610 mincost3 = g->
cost[e];
3615 for( j = 0; j < vrcount; j++ )
3616 visited[vrnodes[j]] =
FALSE;
3622 assert(vbase[tail] == i);
3626 if(
SCIPisGE(scip, mincost2, cost) )
3652 *fixed += g->
cost[e];
3653 assert(g->
mark[tail] && g->
mark[head]);
3678 assert(g->
grad[k] == 0 && g->
grad[j] >= 0);
3687 assert(old - g->
grad[j] - g->
grad[k] > 0);
3688 (*nelims) += old - g->
grad[j] - g->
grad[k];
3689 forbidden[vbase[j]] =
TRUE;
3690 forbidden[vbase[k]] =
TRUE;
3695 for( i = 0; i < nnodes && foundterms; i++ )
3746 assert(vnoi !=
NULL);
3747 assert(heap !=
NULL);
3748 assert(state !=
NULL);
3749 assert(vbase !=
NULL);
3778 for( i = 0; i <
nnodes; i++ )
3782 for( i = 0; i <
nnodes; i++ )
3788 if( g->
grad[i] >= 1 )
3803 minedge1[termcount] = edge1;
3804 term[termcount++] = i;
3809 SCIP_CALL(
graph_voronoiWithDist(scip, g, g->
cost, distance, edgearrint, vbase, minedge1, heap, state, distnode, vnoi) );
3811 for( l = 0; l < termcount; l++ )
3816 if( g->
grad[i] < mingrad )
3819 assert(minedge1[l] !=
UNKNOWN);
3841 assert(i == g->
tail[edge1]);
3852 ttdist = g->
cost[edge1] + vnoi[k].
dist;
3856 if( distnode !=
NULL )
3858 ttdist = distance[i];
3877 *fixed += g->
cost[edge1];
3888 assert(old - g->
grad[i] - g->
grad[k] > 0);
3889 (*nelims) += old - g->
grad[i] - g->
grad[k];
3943 assert(neighb !=
NULL);
3944 assert(vnoi !=
NULL);
3945 assert(heap !=
NULL);
3946 assert(state !=
NULL);
3947 assert(vbase !=
NULL);
3973 assert(distnode !=
NULL);
3978 for( i = 0; i <
nnodes; i++ )
3983 for( i = 0; i <
nnodes; i++ )
3990 if( g->
grad[i] >= 1 )
4004 minedge1[termcount] = edge1;
4005 term[termcount++] = i;
4010 SCIP_CALL(
graph_voronoiWithDist(scip, g, g->
cost, distance, edgearrint, vbase, minedge1, heap, state, distnode, vnoi) );
4013 for( l = 0; l < termcount; l++ )
4018 if( g->
grad[i] < mingrad )
4021 assert(minedge1[l] !=
UNKNOWN);
4060 assert(i == g->
tail[edge1]);
4072 ttdist = g->
cost[edge1] + vnoi[k].
dist;
4078 assert(distnode !=
NULL);
4081 ttdist = distance[i];
4092 else if( t != g->
source )
4121 *fixed += g->
cost[edge1];
4174 assert(vnoi !=
NULL);
4175 assert(heap !=
NULL);
4176 assert(state !=
NULL);
4177 assert(vbase !=
NULL);
4185 for( k = 0; k <
nnodes; k++ )
4200 if( nedges >= (nterms - 1) * nterms )
4201 maxnedges = (nterms - 1) * nterms;
4211 for( k = 0; k <
nnodes; k++ )
4227 netnnodes = netgraph->
knots;
4228 assert(netnnodes == e);
4229 assert(netnnodes == nterms);
4231 for( e = 0; e < nedges / 2; e++ )
4237 for( k = 0; k <
nnodes; k++ )
4242 assert(k == g->
tail[e]);
4244 if( v1 != vbase[g->
head[e]] )
4246 v2 = vbase[g->
head[e]];
4249 assert(nodesid[v1] >= 0);
4250 assert(nodesid[v2] >= 0);
4253 if( netgraph->
head[ne] == nodesid[v2] )
4261 assert(netgraph->
head[ne] == nodesid[v2]);
4262 assert(netgraph->
tail[ne] == nodesid[v1]);
4265 netgraph->
cost[ne] = cost;
4267 edgeorg[ne / 2] = e;
4268 assert(ne <= maxnedges);
4273 edgeorg[netgraph->
edges / 2] = e;
4274 graph_edge_add(scip, netgraph, nodesid[v1], nodesid[v2], cost, cost);
4275 assert(netgraph->
edges <= maxnedges);
4284 for( k = 0; k < netnnodes; k++ )
4293 assert(mst[0].edge == -1);
4295 for( k = 1; k < netnnodes; k++ )
4300 cost = netgraph->
cost[e];
4301 if(
SCIPisGT(scip, cost, maxcost) )
4304 ne = edgeorg[e / 2];
4305 blocked[ne / 2] =
TRUE;
4306 for( v1 = g->
head[ne]; v1 != vbase[v1]; v1 = g->
tail[vnoi[v1].
edge] )
4309 for( v1 = g->
tail[ne]; v1 != vbase[v1]; v1 = g->
tail[vnoi[v1].edge] )
4310 blocked[vnoi[v1].edge / 2] =
TRUE;
4314 for( k = 0; k <
nnodes; k++ )
4326 if(
SCIPisGE(scip, g->
cost[e], maxcost) && !blocked[e / 2] )
4371 assert(scip !=
NULL);
4373 assert(count !=
NULL);
4374 assert(marked !=
NULL);
4380 for(
int k = 0; k <
nnodes; k++ )
4396 for(
int i = 0; i <
nnodes; i++ )
4404 if( !marked[g->
head[e2]] )
4421 (*count) += g->
grad[i];
4437 for(
int j = 0; j <
nnodes; j++ )
4438 assert(marked[j] ==
FALSE);
4456 assert(scip !=
NULL);
4458 assert(count !=
NULL);
4459 assert(marked !=
NULL);
4466 for(
int k = 0; k <
nnodes; k++ )
4470 for(
int k = 0; k <
nnodes; k++ )
4474 int neighborcount = 0;
4494 const int j = g->
head[e];
4507 for(
int j = 0; j <
nnodes; j++ )
4508 assert(marked[j] ==
FALSE);
4527 assert(scip !=
NULL);
4529 assert(count !=
NULL);
4530 assert(marked !=
NULL);
4536 for(
int k = 0; k <
nnodes; k++ )
4540 for(
int k = 0; k <
nnodes; k++ )
4555 const int j = g->
head[e];
4558 neighbarr[nn++] = j;
4562 maxgrad = g->
grad[k];
4565 for(
int l = 0; l < nn; l++ )
4571 maxgrad += g->
grad[neighbarr[l]];
4580 assert(0 &&
"implement me");
4586 const int j = g->
head[e];
4589 candidates[ncands++] = j;
4600 for(
int l = 0; l < ncands; l++ )
4606 for(
int l = 0; l < nn; l++ )
4612 for(
int k2 = 0; k2 <
nnodes; k2++ )
4613 assert(marked[k2] ==
FALSE);
4632 assert(scip !=
NULL);
4634 assert(count !=
NULL);
4635 assert(marked !=
NULL);
4641 for(
int k = 0; k <
nnodes; k++ )
4645 for(
int k = 0; k <
nnodes; k++ )
4653 maxprize = g->
prize[k];
4656 for(
int run = 0; run < 2; run++ )
4661 int maxgrad = g->
grad[k];
4666 const int j = g->
head[e];
4670 neighbarr[nn++] = j;
4672 else if(
SCIPisGT(scip, g->
prize[j], maxprize) && g->
mark[j] && j != neighbor0 )
4674 maxprize = g->
prize[j];
4681 if( run == 0 && k2 !=
UNKNOWN )
4682 neighbarr[nn++] = k2;
4684 for(
int l = 0; l < nn; l++ )
4688 const int j = g->
head[e];
4691 maxprize = g->
prize[j];
4696 maxgrad += g->
grad[neighbarr[l]];
4699 if( run == 1 && k2 !=
UNKNOWN )
4701 maxgrad += g->
grad[k2];
4702 neighbarr[nn++] = k2;
4714 min += g->
prize[k2];
4721 const int j = g->
head[e];
4732 for(
int l = 0; l < nn; l++ )
4738 for( k2 = 0; k2 <
nnodes; k2++ )
4739 assert(marked[k2] ==
FALSE);
4771 assert(scip !=
NULL);
4773 assert(count !=
NULL);
4774 assert(marked !=
NULL);
4782 for( k = 0; k <
nnodes; k++ )
4788 for( k = 0; k <
nnodes; k++ )
4790 if( !(g->
mark[k]) || (g->
grad[k] < 2) )
4796 kprize = g->
prize[k];
4797 maxgrad = g->
grad[k];
4809 neighbarr[nn++] = j;
4821 for (l = 0; l < nn; l++)
4832 maxgrad += g->
grad[neighbarr[l]] - 1;
4841 for (j = 0; j <
nnodes; j++)
4872 for (l = 0; l < nn; l++)
4879 for( l = 0; l <
nnodes; l++ )
4886 for (k = 0; k <
nnodes; k++)
4894 kprize = g->
prize[k];
4895 maxgrad = g->
grad[k];
4907 neighbarr[nn++] = j;
4911 || (
SCIPisGE(scip, g->
prize[j], kprize) && j > k && nn2 < 3) )
4913 neighbarr2[nn2++] = j;
4925 for (l = 0; l < nn; l++)
4938 neighbarr2[nn2++] = j;
4946 maxgrad += g->
grad[neighbarr[l]] - 1;
4954 for (l = 0; l < nn2; l++)
4964 min += g->
prize[k2];
4965 k2grad = g->
grad[k2];
4966 maxgrad += k2grad - 1;
4970 for (j = 0; j <
nnodes; j++)
5001 min -= g->
prize[k2];
5002 maxgrad -= k2grad - 1;
5008 for (l = 0; l < nn; l++)
5014 for( l = 0; l <
nnodes; l++ )
5050 assert(scip !=
NULL);
5051 assert(pathtail !=
NULL);
5052 assert(pathhead !=
NULL);
5053 assert(heap !=
NULL);
5054 assert(statetail !=
NULL);
5055 assert(statehead !=
NULL);
5056 assert(memlbltail !=
NULL);
5057 assert(memlblhead !=
NULL);
5058 assert(nelims !=
NULL);
5063 for(
int i = 0; i <
nnodes; i++ )
5077 for(
int i = 0; i <
nnodes; i++ )
5081 assert(g->
grad[i] >= 0);
5093 adjverts[k++] = g->
head[e];
5100 prize = g->
prize[i];
5101 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &sdist0, -prize, heap, statetail, statehead, memlbltail, memlblhead, adjverts[0], adjverts[1], limit,
FALSE,
TRUE) );
5102 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &sdist1, -prize, heap, statetail, statehead, memlbltail, memlblhead, adjverts[1], adjverts[2], limit,
FALSE,
TRUE) );
5103 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &sdist2, -prize, heap, statetail, statehead, memlbltail, memlblhead, adjverts[2], adjverts[0], limit,
FALSE,
TRUE) );
5106 if( (
SCIPisGE(scip, -sdist0 - sdist1, prize) &&
SCIPisGE(scip, -sdist2, prize))
5107 || (
SCIPisGE(scip, -sdist1 - sdist2, prize) &&
SCIPisGE(scip, -sdist0, prize))
5108 || (
SCIPisGE(scip, -sdist2 - sdist0, prize) &&
SCIPisGE(scip, -sdist1, prize))
5112 (*nelims) += g->
grad[i];
5127 for(
int k = 0; k < 4; k++ )
5129 for(
int k = 0; k < 4; k++ )
5130 for(
int k2 = k + 1; k2 < 4; k2++ )
5136 for(
int i = 0; i <
nnodes; i++ )
5148 adjverts[k++] = g->
head[e];
5153 prize = g->
prize[i];
5156 for( k = 0; k < 4; k++ )
5161 const int k2 = auxg->
head[e];
5164 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &(sdist0), -prize, heap, statetail, statehead, memlbltail, memlblhead, adjverts[k], adjverts[k2], limit,
FALSE,
TRUE) );
5165 auxg->
cost[e] = sdist0;
5184 for(
int l = 1; l < 4; l++ )
5185 sdist0 += mst[l].dist;
5187 if(
SCIPisLE(scip, prize, -sdist0) )
5190 for( k = 0; k < 4; k++ )
5197 for(
int l = 1; l < 4; l++ )
5199 sdist0 += mst[l].
dist;
5204 for(
int l = 2; l < 4; l++ )
5205 sdist0 += mst[l].dist;
5208 if(
SCIPisGT(scip, prize, -sdist0) )
5218 (*nelims) += g->
grad[i];
5232 for(
int k = 0; k < 4; k++ )
5238 for(
int i = 0; i <
nnodes; i++ )
5250 adjverts[k++] = g->
head[e];
5255 prize = g->
prize[i];
5257 for( k = 0; k < 5; k++ )
5262 const int k2 = auxg->
head[e];
5265 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &(sdist0), -prize, heap, statetail, statehead, memlbltail, memlblhead, adjverts[k], adjverts[k2], limit,
FALSE,
TRUE) );
5266 auxg->
cost[e] = sdist0;
5281 for(
int l = 1; l < 5; l++ )
5282 sdist0 += mst[l].dist;
5284 if(
SCIPisLE(scip, prize, -sdist0) )
5286 for( k = 0; k < 5; k++ )
5294 for(
int l = 1; l < 5; l++ )
5296 sdist0 += mst[l].
dist;
5301 for(
int l = 2; l < 5; l++ )
5302 sdist0 += mst[l].dist;
5305 if(
SCIPisLE(scip, prize, -sdist0) )
5307 for( k2 = k + 1; k2 < 5; k2++ )
5313 if( k2 != 0 && k != 0)
5316 for(
int l = 1; l < 5; l++ )
5318 sdist0 += mst[l].
dist;
5323 if( k != 1 && k2 != 1 )
5328 for(
int l = 0; l < 5; l++ )
5329 if( auxg->
mark[l] && l != s )
5330 sdist0 += mst[l].
dist;
5333 if(
SCIPisGT(scip, prize, -sdist0) )
5347 (*nelims) += g->
grad[i];
5390 assert(scip !=
NULL);
5391 assert(pathtail !=
NULL);
5392 assert(pathhead !=
NULL);
5393 assert(heap !=
NULL);
5394 assert(statetail !=
NULL);
5395 assert(statehead !=
NULL);
5396 assert(memlbltail !=
NULL);
5397 assert(memlblhead !=
NULL);
5398 assert(nelims !=
NULL);
5404 for( i = 0; i <
nnodes; i++ )
5414 for( i = 0; i <
nnodes; i++ )
5416 assert(g->
grad[i] >= 0);
5428 assert(g->
mark[i1]);
5429 assert(g->
mark[i2]);
5431 SCIP_CALL(
reduce_getSd(scip, g, pathtail, pathhead, &sdist, -(g->
prize[i]), heap, statetail, statehead, memlbltail, memlblhead, i1, i2, limit,
FALSE,
TRUE) );
5460 assert(scip !=
NULL);
5462 assert(count !=
NULL);
5463 assert(marked !=
NULL);
5467 for(
int k = 0; k <
nnodes; k++ )
5471 for(
int k = 0; k <
nnodes; k++ )
5484 const int j = g->
head[e];
5492 const int candedge = e2;
5494 if( marked[g->
head[candedge]] )
5506 for(
int j = 0; j <
nnodes; j++ )
5507 assert(marked[j] ==
FALSE);
5510 *count = localcount;
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static volatile int nterms
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
static int getlecloseterms(SCIP *scip, PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, int *vbase, int *neighbterms, int i, int nnodes)
SCIP_Real misc_stp_maxReal(SCIP_Real *realarr, unsigned nreals)
#define STP_BDR_MAXDEGREE
SCIP_RETCODE reduce_getSd(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, SCIP_Real *sdist, SCIP_Real distlimit, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int i, int i2, int limit, SCIP_Bool pc, SCIP_Bool mw)
SCIP_RETCODE reduce_npv(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE graph_voronoiWithDist(SCIP *, const GRAPH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, PATH *)
SCIP_RETCODE SCIPqueueInsert(SCIP_QUEUE *queue, void *elem)
SCIP_Bool graph_valid(const GRAPH *)
SCIP_RETCODE reduce_sdsp(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit, int *edgestate)
SCIP_RETCODE reduce_getSdPcMw(SCIP *scip, const GRAPH *g, PATH *pathtail, PATH *pathhead, SCIP_Real *sdist, SCIP_Real distlimit, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *pathmaxnodetail, int *pathmaxnodehead, int i, int i2, int limit)
SCIP_RETCODE reduce_nts(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
void * SCIPqueueRemove(SCIP_QUEUE *queue)
#define VERTEX_TEMPNEIGHBOR
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Problem data for stp problem.
enum SCIP_Retcode SCIP_RETCODE
static SCIP_Bool sddeltable(SCIP *scip, GRAPH *g, PATH *path, int *vbase, int *forbidden, int tpos, int hpos, int tail, int head, int edge, int nnodes)
void graph_path_exit(SCIP *, GRAPH *)
SCIP_RETCODE reduce_cnsAdv(SCIP *scip, GRAPH *g, int *marked, int *count)
SCIP_RETCODE graph_knot_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, SCIP_Bool *)
static void correct(SCIP *scip, int *heap, int *state, int *count, PATH *path, int l, int k, int e, SCIP_Real cost, int mode)
#define SCIPfreeBufferArray(scip, ptr)
void graph_knot_chg(GRAPH *, int, int)
SCIP_RETCODE reduce_sdspSap(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
static SCIP_Real getRSD(SCIP *scip, GRAPH *g, GRAPH *netgraph, PATH *mst, PATH *vnoi, SCIP_Real *mstsdist, SCIP_Real *termdist1, SCIP_Real *termdist2, SCIP_Real sd_initial, int *vbase, int *nodesid, int *neighbterms1, int *neighbterms2, int i, int i2, int limit)
#define STP_BDR_MAXDNEDGES
SCIP_RETCODE graph_pc_contractEdge(SCIP *, GRAPH *, int *, int, int, int)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_sdPaths(SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int, int, int)
#define STP_RED_ANSMAXNEIGHBORS
void reduce_ansAdv2(SCIP *scip, GRAPH *g, int *marked, int *count)
SCIP_Bool SCIPqueueIsEmpty(SCIP_QUEUE *queue)
void reduce_ans(SCIP *scip, GRAPH *g, int *marked, int *count)
miscellaneous methods used for solving Steiner problems
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
SCIP_RETCODE level0(SCIP *, GRAPH *)
SCIP_RETCODE reduce_bdr(SCIP *scip, GRAPH *g, GRAPH *netgraph, PATH *netmst, PATH *vnoi, SCIP_Real *mstsdist, SCIP_Real *termdist1, SCIP_Real *termdist2, int *vbase, int *nodesid, int *neighbterms1, int *neighbterms2, int *nelims)
#define SCIPfreeBufferArrayNull(scip, ptr)
void graph_path_exec(SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
SCIP_RETCODE reduce_sdPc(SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *nelims)
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
void graph_path_PcMwSd(SCIP *, const GRAPH *, PATH *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, int *, int, int, int)
SCIP_RETCODE reduce_nvAdv(SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *distance, double *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *neighb, int *distnode, int *solnode, int *nelims)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
void voronoi_term(const GRAPH *, double *, double *, double *, PATH *, int *, int *, int *, int *, int)
#define SCIPallocBufferArray(scip, ptr, num)
void reduce_nnp(SCIP *scip, GRAPH *g, int *marked, int *count)
SCIP_Real SCIPgetTotalTime(SCIP *scip)
static void ansProcessCandidate(SCIP *scip, GRAPH *g, int *marked, int *count, SCIP_Real min, int candvertex)
static int getcloseterms(SCIP *scip, const PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, const int *vbase, int *neighbterms, int i, int nnodes)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define STP_BD_MAXDNEDGES
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
SCIP_RETCODE reduce_nv(SCIP *scip, GRAPH *g, PATH *vnoi, double *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *solnode, int *nelims)
SCIP_RETCODE reduce_sl(SCIP *scip, GRAPH *g, PATH *vnoi, double *fixed, int *heap, int *state, int *vbase, int *vrnodes, STP_Bool *visited, int *solnode, int *nelims)
static int getcloseterms2term(SCIP *scip, const GRAPH *g, const GRAPH *netgraph, SCIP_Real *termdist, SCIP_Real ecost, int *neighbterms, int *nodesid, int *nodesorg, int i)
includes various files containing graph methods used for Steiner tree problems
void graph_get4nextTerms(SCIP *, const GRAPH *, SCIP_Real *, SCIP_Real *, PATH *, int *, int *, int *)
void reduce_ansAdv(SCIP *scip, GRAPH *g, int *marked, int *count, SCIP_Bool extneigbhood)
SCIP_RETCODE reduce_bd34(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_RETCODE reduce_sd(SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *edgepreds, SCIP_Real *mstsdist, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *forbidden, int *nelims, SCIP_Bool nodereplacing, int *edgestate)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_knot_add(GRAPH *, int)
SCIP_RETCODE graph_get4nextTTerms(SCIP *, const GRAPH *, SCIP_Real *, PATH *, int *, int *, int *)
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
#define STP_RED_ANSEXMAXCANDS
SCIP_RETCODE reduce_chain2(SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
void SCIPqueueFree(SCIP_QUEUE **queue)
#define BMSclearMemoryArray(ptr, num)
SCIP_RETCODE reduce_ledge(SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nelims, int *edgestate)
static int nearest(int *heap, int *state, int *count, const PATH *path)
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
void graph_voronoiTerms(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
#define STP_RED_ANSMAXCANDS