35 #define STP_TPATHS_NTERMBASES 4 36 #define STP_TPATHS_RESERVESIZE 16 39 #define pathResetSingle(entry) \ 42 entry.dist = FARAWAY; \ 43 entry.edge = UNKNOWN; \ 48 #define tpathsRepairResetNode(scip, node, resetnodes, stack, nodes_isvisited) \ 51 assert(scip && resetnodes && stack && nodes_isvisited); \ 52 assert(!nodes_isvisited[node]); \ 53 StpVecPushBack(scip, resetnodes, node); \ 54 StpVecPushBack(scip, stack, node); \ 55 nodes_isvisited[node] = TRUE; \ 117 heap[1] = heap[(*count)--];
121 if (
LT(path[heap[3]].dist, path[heap[2]].dist))
124 while((c <= (*count)) &&
GT(path[heap[j]].dist, path[heap[c]].dist))
134 if ((c + 1) <= (*count))
135 if (
LT(path[heap[c + 1]].dist, path[heap[c]].dist))
160 path[l].dist = newdist;
166 heap[++(*count)] = l;
173 while( (j > 1) && path[heap[c]].dist > path[heap[j]].dist )
216 dist += path[k].
dist;
220 dist += path[k2].
dist;
228 if(
SCIPisLT(scip, dist, path[vbk].dist) )
230 path[vbk].
dist = dist;
244 max = MIN((l + 1), 3);
246 for( r = 0; r <= max; r++ )
257 t = vbase[k2 + (r *
nnodes)];
259 for( s = 0; s < l; s++ )
260 if( vbase[vbk + s * nnodes] == t )
262 if( s < l || vbk == t )
267 dist += path[k].dist;
269 dist += path[k2 + (r * nnodes)].
dist;
271 if(
SCIPisLT(scip, dist, path[pos].dist) )
273 path[pos].
dist = dist;
295 const int offset = (level - 1) * nnodes;
296 const int base = termbases[node + offset];
308 edge_curr = termpaths[node_curr + offset].
edge;
309 node_next = (edge_curr >= 0) ? g->
tail[edge_curr] : -1;
311 while( node_curr != base )
317 printf(
"found deleted edge, break \n");
321 if( sdprofit && node_curr != node )
324 printf(
"node %d profit: %f \n", node_curr, profit);
331 printf(
"...edge killed! \n");
334 node_pred = node_curr;
335 node_curr = node_next;
336 edge_curr = termpaths[node_curr + offset].
edge;
337 node_next = (edge_curr >= 0) ? g->
tail[edge_curr] : -1;
381 const int offset = (level - 1) * nnodes;
383 assert(2 <= level && level <= 4);
384 assert(offset == nnodes || offset == 2 * nnodes || offset == 3 * nnodes);
386 for(
int i = 0; i <
nnodes; i++ )
389 const int k = i + offset;
396 for(
int i = 0; i < offset; i++ )
412 int* RESTRICT closeterms,
413 int* RESTRICT firstedges,
415 int* RESTRICT ncloseterms
425 assert(closeterms && closeterms_dist && ncloseterms && g);
427 assert(0 <= node && node < nnodes);
428 assert(nnodes == g->
knots);
429 assert(
GE(maxdist, 0.0));
434 closeterms[0] = node;
435 closeterms_dist[0] = 0.0;
443 for(
int k = 0; k < maxnumber; k++ )
447 LT(termpaths[pos].dist, maxdist)
448 :
LE(termpaths[pos].dist, maxdist);
452 closeterms[nnterms] = termbases[pos];
456 firstedges[nnterms] = termpaths[pos].
edge;
458 closeterms_dist[nnterms++] = termpaths[pos].
dist;
462 assert(distIsStrict || !
LE(termpaths[pos].dist, maxdist));
470 for(
int k = 0; k < nnterms; k++ )
472 const int term = closeterms[k];
478 *ncloseterms = nnterms;
497 const SCIP_Real ecost = ((g->
source == vbase[node]) ? cost[edge] : costrev[edge]);
500 assert(node % g->
knots == g->
tail[edge]);
501 assert(nextnode % g->
knots == g->
head[edge]);
504 if( sdprofit && path[node].edge >= 0 )
507 const int node_pred = g->
tail[path[node].
edge];
511 if( node_pred == nextnode % nnodes )
513 distnew = path[node].
dist + ecost;
518 ecost, path[node].dist, nextnode % nnodes, node_pred);
523 distnew = path[node].
dist + ecost;
527 assert(
LE(distnew, path[node].dist + ecost));
572 int nHeapElems = heapsize;
579 SCIP_Bool* nodes_isvisited = extend ? repair->nodes_isvisited :
NULL;
581 assert(nHeapElems >= 0);
582 assert(repair ==
NULL || repair->withEdgeReplacement);
584 while( nHeapElems > 0 )
596 const int m = g->
head[e];
602 if( withProfit && vbase[k] != k )
605 assert(path[k].edge >= 0);
606 k_pred = g->
tail[path[k].edge];
612 distnew = k_dist + cost[e];
615 assert(
GE(distnew, 0.0) &&
LE(distnew, k_dist + cost[e]));
618 if(
GT(path[m].dist, distnew) )
620 if( extend && !nodes_isvisited[m] )
623 nodes_isvisited[m] =
TRUE;
649 int nheapElems = heapsize;
655 SCIP_Bool* nodes_isvisited = extend ? repair->nodes_isvisited :
NULL;
657 assert(nheapElems >= 0);
658 assert(repair ==
NULL || repair->withEdgeReplacement);
660 while( nheapElems > 0 )
663 const int k = k2 -
nnodes;
673 const int head = g->
head[e];
675 if( !
Is_term(g->
term[head]) && vbase[head] != vbase[k2] && g->
mark[head] )
677 const int head2 = head +
nnodes;
681 if(
GT(path[head2].dist, distnew) )
683 if( extend && !nodes_isvisited[head] )
686 nodes_isvisited[head] =
TRUE;
690 vbase[head2] = vbase[k2];
712 const int dnnodes = 2 *
nnodes;
713 int nheapElems = heapsize;
719 SCIP_Bool* nodes_isvisited = extend ? repair->nodes_isvisited :
NULL;
721 assert(nheapElems >= 0);
722 assert(repair ==
NULL || repair->withEdgeReplacement);
724 while( nheapElems > 0 )
728 const int k = k3 - dnnodes;
729 assert(0 <= k && k < nnodes);
737 const int head = g->
head[e];
739 if( !
Is_term(g->
term[head]) && vbase[head] != vbase[k3] && vbase[head + nnodes] != vbase[k3] && g->
mark[head] )
741 const int head3 = head + dnnodes;
745 if(
GT(path[head3].dist, distnew) )
747 if( extend && !nodes_isvisited[head] )
750 nodes_isvisited[head] =
TRUE;
754 vbase[head3] = vbase[k3];
776 const int dnnodes = 2 *
nnodes;
777 const int tnnodes = 3 *
nnodes;
778 int nHeapElems = heapsize;
784 SCIP_Bool* nodes_isvisited = extend ? repair->nodes_isvisited :
NULL;
786 assert(nHeapElems >= 0);
787 assert(repair ==
NULL || repair->withEdgeReplacement);
790 while( nHeapElems > 0 )
794 const int k = k4 - tnnodes;
795 assert(0 <= k && k < nnodes);
803 const int head = g->
head[e];
806 && vbase[head] != vbase[k4] && vbase[head + nnodes] != vbase[k4] && vbase[head + dnnodes] != vbase[k4] && g->
mark[head] )
808 const int head4 = head + tnnodes;
812 if(
GT(path[head4].dist, distnew) )
814 if( extend && !nodes_isvisited[head] )
817 nodes_isvisited[head] =
TRUE;
821 vbase[head4] = vbase[k4];
841 const int*
const state = repair->tpaths->state;
842 for(
int i = 0; i <
nnodes; ++i )
847 assert(0 <= level && level <= 3);
848 assert(!repair->nodes_isvisited);
851 repair->nHeapElems = -1;
866 const STP_Vectype(
int) resetnodes_level = repair->resetnodes[level];
867 int* RESTRICT
state = repair->tpaths->state;
868 SCIP_Bool* RESTRICT nodes_isvisited = repair->nodes_isvisited;
870 const int shift = g->
knots * level;
872 assert(0 <= level && level <= 3);
875 for(
int i = 0; i < size; i++ )
877 const int node = resetnodes_level[i];
880 nodes_isvisited[node] =
FALSE;
885 for(
int i = 0; i < g->
knots; ++i )
887 assert(!nodes_isvisited[i]);
910 const TPATHS* tpaths = repair->tpaths;
912 SCIP_Bool* RESTRICT nodes_isvisited = repair->nodes_isvisited;
914 if( termpaths[start].edge >= 0 && g->
tail[termpaths[start].
edge] == pred )
916 STP_Vectype(
int) resetnodes1st = repair->resetnodes[0];
920 assert(resetnodes1st);
936 const int head = g->
head[
a];
938 if( nodes_isvisited[head] )
941 if( termpaths[head].edge >= 0 && g->
tail[termpaths[head].
edge] == node )
944 assert(head != pred);
953 repair->stack = stack;
954 repair->resetnodes[0] = resetnodes1st;
970 TPATHS* tpaths = repair->tpaths;
973 SCIP_Bool* RESTRICT nodes_isvisited = repair->nodes_isvisited;
975 const int shift = level *
nnodes;
977 STP_Vectype(
int) resetnodes_level = repair->resetnodes[level];
979 assert(scip && nodes_isvisited && resetnodes_level);
980 assert(1 <= level && level <= 3);
988 const int nodebaseorg_top = vbase_org[node + shift];
995 const int head = g->
head[
a];
997 if( !nodes_isvisited[head] )
999 const int head_shifted = head + shift;
1001 if( termpaths[head_shifted].edge >= 0 && g->
tail[termpaths[head_shifted].
edge] == node )
1003 if( nodebaseorg_top != vbase_org[head_shifted] )
1014 repair->stack = stack;
1015 repair->resetnodes[level] = resetnodes_level;
1028 const TPATHS* tpaths = repair->tpaths;
1031 const int shift = level *
nnodes;
1032 const int edge = repair->edge;
1033 const int tail = g->
tail[edge];
1034 const int head = g->
head[edge];
1036 if( termpaths[tail + shift].edge >= 0 && g->
tail[termpaths[tail + shift].
edge] == head )
1038 tpathsRepairResetNode(scip, tail, repair->resetnodes[level], repair->stack, repair->nodes_isvisited);
1041 if( termpaths[head + shift].edge >= 0 && g->
tail[termpaths[head + shift].
edge] == tail )
1043 tpathsRepairResetNode(scip, head, repair->resetnodes[level], repair->stack, repair->nodes_isvisited);
1057 const TPATHS* tpaths = repair->tpaths;
1061 SCIP_Bool* RESTRICT nodes_isvisited = repair->nodes_isvisited;
1063 const int shift = level *
nnodes;
1065 assert(repair->resetnodes[level] && vbase && nodes_isvisited);
1066 assert(1 <= level && level <= 3);
1068 for(
int d = 0; d < level; d++ )
1070 const STP_Vectype(
int) resetnodes_d = repair->resetnodes[d];
1075 for(
int i = 0; i < size; i++ )
1077 const int node = resetnodes_d[i];
1078 const int nodebase_d = vbase[node + d *
nnodes];
1079 const int nodebaseorg_d = vbase_org[node + d *
nnodes];
1083 if( !nodes_isvisited[node] && nodebase_d == vbase[node + shift] )
1090 const int head = g->
head[
a];
1092 if( !nodes_isvisited[head] )
1094 const int head_shifted = head + shift;
1096 if( termpaths[head_shifted].edge >= 0 && g->
tail[termpaths[head_shifted].
edge] == node )
1098 if( nodebaseorg_d != vbase[head_shifted] )
1124 assert(1 <= level && level <= 3);
1141 const STP_Vectype(
int) resetnodes1st = repair->resetnodes[0];
1142 const SCIP_Bool* nodes_isvisited = repair->nodes_isvisited;
1143 TPATHS* tpaths = repair->tpaths;
1149 const int edge = repair->edge;
1150 const int edge_rev =
flipedge(edge);
1153 for(
int i = 0; i < size; i++ )
1155 const int node = resetnodes1st[i];
1165 const int tail = g->
tail[e];
1167 if( nodes_isvisited[tail] || e == edge || e == edge_rev )
1170 dist = g->
cost[e] + termpaths[tail].dist;
1172 if( dist < termpaths[node].dist )
1174 termpaths[node].dist = dist;
1175 termpaths[node].edge = e;
1176 termbases[node] = termbases[tail];
1182 if( termbases[node] !=
UNKNOWN )
1185 termbases[node], g->
tail[termpaths[node].edge], termpaths[node].dist);
1191 repair->nHeapElems = nHeapElems;
1206 const STP_Vectype(
int) resetnodes_top = repair->resetnodes[level];
1207 const SCIP_Bool* nodes_isvisited = repair->nodes_isvisited;
1208 TPATHS* tpaths = repair->tpaths;
1210 int* RESTRICT vbase = tpaths->
termbases;
1215 const int shift = level *
nnodes;
1216 const int edge = repair->edge;
1217 const int edge_rev =
flipedge(edge);
1220 assert(1 <= level && level <= 3);
1222 for(
int i = 0; i < size; i++ )
1224 const int node = resetnodes_top[i];
1225 const int node_shift = node + shift;
1228 assert(nodes_isvisited[node]);
1235 const int tail = g->
tail[e];
1237 if( e == edge || e == edge_rev )
1241 for(
int d = 0; d <= level; d++ )
1244 const int tail_d = tail + d *
nnodes;
1245 const int tailbase_d = vbase[tail_d];
1248 if( d == level && nodes_isvisited[tail] )
1251 for( h = 0; h < level; h++ )
1252 if( vbase[node + h * nnodes] == tailbase_d )
1259 dist = g->
cost[e] + termpaths[tail_d].dist;
1261 if( dist < termpaths[node_shift].dist )
1263 termpaths[node_shift].dist = dist;
1264 termpaths[node_shift].edge = e;
1265 vbase[node_shift] = tailbase_d;
1272 if( vbase[node_shift] !=
UNKNOWN )
1275 vbase[node_shift], g->
tail[termpaths[node_shift].edge], termpaths[node_shift].dist);
1281 repair->nHeapElems = nHeapElems;
1293 const int edge = repair->edge;
1294 const int tail = g->
tail[edge];
1295 const int head = g->
head[edge];
1308 repair->withEdgeReplacement ? repair :
NULL);
1324 const int level = 1;
1331 repair->withEdgeReplacement ? repair :
NULL);
1346 const int level = 2;
1353 repair->withEdgeReplacement ? repair :
NULL);
1369 const int level = 3;
1376 repair->withEdgeReplacement ? repair :
NULL);
1394 TPATHS* tpaths = repair->tpaths;
1405 assert(!repair->resetnodes[i]);
1407 assert(repair->resetnodes[i]);
1420 TPATHS* tpaths = repair->tpaths;
1422 const int*
const vbase = tpaths->
termbases;
1427 STP_Vectype(
int) resetnodes_i = repair->resetnodes[i];
1429 const int shift = nnodes * i;
1431 assert(resetnodes_i);
1433 for(
int j = 0; j < size; j++ )
1435 const int node = resetnodes_i[j];
1436 const int node_shift = node + shift;
1439 vbase_org[node_shift] = vbase[node_shift];
1450 assert(vbase_org[i] == vbase[i]);
1475 assert(path && vbase && state);
1492 TPATHS tpaths = { .
termpaths = path2, .termbases = vbase2, .state = state2, .nnodes = nnodes };
1494 assert(path2 && vbase2 && state2);
1511 TPATHS tpaths = { .
termpaths = path3, .termbases = vbase3, .state = state3, .nnodes = nnodes };
1513 assert(path3 && vbase3 && state3);
1531 TPATHS tpaths = { .
termpaths = path4, .termbases = vbase4, .state = state4, .nnodes = nnodes };
1533 assert(path4 && vbase4 && state4);
1552 TPATHS tpaths = { .
termpaths = path2, .termbases = vbase2, .state = state2, .nnodes = nnodes };
1554 assert(path2 && vbase2 && state2);
1572 TPATHS tpaths = { .
termpaths = path3, .termbases = vbase3, .state = state3, .nnodes = nnodes };
1574 assert(path3 && vbase3 && state3);
1592 TPATHS tpaths = { .
termpaths = path4, .termbases = vbase4, .state = state4, .nnodes = nnodes };
1594 assert(path4 && vbase4 && state4);
1622 assert(path !=
NULL);
1623 assert(cost !=
NULL);
1624 assert(heap !=
NULL);
1625 assert(state !=
NULL);
1636 for( k = 0; k <
nnodes; k++ )
1644 if( !g->
mark[k2] || k2 < k )
1648 if( vbase[k] != vbase[k2] )
1650 boundedges[nboundedges++] = e;
1661 for( l = 0; l < 4; l++ )
1663 for( e = 0; e < nboundedges; e++ )
1665 bedge = boundedges[e];
1667 k2 = g->
head[bedge];
1668 utdist(scip, g, path, cost[bedge], vbase, k, l, k2, shift, nnodes);
1669 utdist(scip, g, path, cost[bedge], vbase, k2, l, k, shift, nnodes);
1708 assert(scip && g && sdprofit);
1753 TREPAIR repair = { .resetnodes = resetnodes, .stack =
NULL, .tpaths = tpaths, .nodes_isvisited =
NULL,
1754 .edge = edge, .nHeapElems = 0, .withEdgeReplacement = withEdgeReplacement };
1756 assert(scip && g && tpaths);
1783 assert(tpaths && g && sdprofit);
1804 assert(0 &&
"currently does not work, need to use vbase to find correct ancestor");
1808 printf(
"printing terminal paths for ");
1813 printf(
"single node path only: \n");
1824 const int base = termbases[pos];
1830 printf(
"Path to terminal (distance=%f) ", tpaths->
termpaths[pos].
dist);
1855 assert(tpaths && profitnodes && sdprofit);
1872 for( level = 0; termbases[start + nnodes * level] != base; level++ )
1876 assert(termbases[start + nnodes * level] == base);
1881 edge_curr = termpaths[node_curr + level *
nnodes].
edge;
1882 assert(edge_curr >= 0);
1883 node_next = g->
tail[edge_curr];
1887 while( node_curr != base )
1891 assert(termbases[node_curr + level * nnodes] == base);
1895 if( node_curr != start )
1898 if(
GT(profit, 0.0) )
1904 node_pred = node_curr;
1905 node_curr = node_next;
1907 while( termbases[node_curr + level * nnodes] != base )
1913 edge_curr = termpaths[node_curr + level *
nnodes].
edge;
1914 node_next = (edge_curr >= 0) ? g->
tail[edge_curr] : -1;
1921 const int node = profitnodes[k];
1944 int* RESTRICT vbase = tpaths->
termbases;
1947 assert(path !=
NULL);
1948 assert(cost !=
NULL);
1949 assert(heap !=
NULL);
1950 assert(state !=
NULL);
1951 assert(nnodes == tpaths->
nnodes);
1954 for(
int i = 0; i <
nnodes; i++ )
1962 heap[++nHeapElems] = i;
1968 state[i] = nHeapElems;
1979 if( nbases == 0 || nnodes <= 1 )
1999 int* RESTRICT vbase = tpaths->
termbases;
2002 assert(nnodes == tpaths->
nnodes);
2003 assert(path !=
NULL);
2004 assert(cost !=
NULL);
2005 assert(heap !=
NULL);
2006 assert(state !=
NULL);
2007 assert(costrev !=
NULL);
2013 for(
int k = 0; k <
nnodes; k++ )
2020 const int head = g->
head[e];
2022 if( !
Is_term(g->
term[head]) && vbase[k] != vbase[head] && g->
mark[head] )
2024 const int head2 = head +
nnodes;
2027 if(
GT(path[head2].dist, distnew) )
2030 vbase[head2] = vbase[k];
2054 const int dnnodes = 2 *
nnodes;
2057 int* RESTRICT vbase = tpaths->
termbases;
2060 assert(nnodes == tpaths->
nnodes);
2061 assert(path !=
NULL);
2062 assert(cost !=
NULL);
2063 assert(heap !=
NULL);
2064 assert(state !=
NULL);
2065 assert(costrev !=
NULL);
2070 for(
int k = 0; k <
nnodes; k++ )
2077 const int head = g->
head[e];
2078 const int head3 = head + dnnodes;
2084 for(
int level = 0; level < 2; level++ )
2086 if( vbase[kn] != vbase[head] && vbase[kn] != vbase[head + nnodes] )
2090 if(
GT(path[head3].dist, distnew) )
2093 vbase[head3] = vbase[kn];
2122 const int dnnodes = 2 *
nnodes;
2123 const int tnnodes = 3 *
nnodes;
2126 int* RESTRICT vbase = tpaths->
termbases;
2129 assert(nnodes == tpaths->
nnodes);
2130 assert(path !=
NULL);
2131 assert(cost !=
NULL);
2132 assert(costrev !=
NULL);
2133 assert(heap !=
NULL);
2134 assert(state !=
NULL);
2135 assert(costrev !=
NULL);
2140 for(
int k = 0; k <
nnodes; k++ )
2147 const int head = g->
head[e];
2148 const int head4 = head + tnnodes;
2154 for(
int level = 0; level < 3; level++ )
2156 if( vbase[kn] != vbase[head] && vbase[kn] != vbase[head + nnodes] && vbase[kn] != vbase[head + dnnodes] )
2160 if(
GT(path[head4].dist, distnew))
2163 vbase[head4] = vbase[kn];
2189 assert(cost !=
NULL);
2190 assert(costrev !=
NULL);
2191 assert(tpaths !=
NULL);
2205 for(
int level = 0; level < 1; level++ )
2207 for(
int k = 0; k <
nnodes; ++k )
2209 assert(
LE_FEAS_EPS(path2[level * nnodes + k].dist, path2[(level + 1) * nnodes + k].dist,
EPSILON));
2228 assert(cost !=
NULL);
2229 assert(costrev !=
NULL);
2230 assert(tpaths !=
NULL);
2245 for(
int level = 0; level < 2; level++ )
2247 for(
int k = 0; k <
nnodes; ++k )
2249 assert(
LE_FEAS_EPS(path3[level * nnodes + k].dist, path3[(level + 1) * nnodes + k].dist,
EPSILON));
2269 assert(cost !=
NULL);
2270 assert(costrev !=
NULL);
2285 for(
int level = 0; level < 3; level++ )
2287 for(
int k = 0; k <
nnodes; ++k )
2289 assert(
LE(path4[level * nnodes + k].dist, path4[(level + 1) * nnodes + k].dist));
2306 assert(scip && tpaths);
2326 int* RESTRICT closeterm,
2327 int* RESTRICT firstedge,
2331 assert(g && tpaths && closeterm && closeterm_dist);
2337 *closeterm_dist = 0.0;
2346 *closeterm = termbases[node];
2347 *closeterm_dist = termpaths[node].
dist;
2349 *firstedge = termpaths[node].
edge;
2361 int* RESTRICT closeterms,
2362 int* RESTRICT firstedges,
2364 int* RESTRICT ncloseterms
2368 tpathsGetKCloseTerms(g, tpaths, 3, node, maxdist_strict, isStrict, closeterms, firstedges, closeterms_dist, ncloseterms);
2379 int* RESTRICT closeterms,
2380 int* RESTRICT firstedges,
2382 int* RESTRICT ncloseterms
2386 tpathsGetKCloseTerms(g, tpaths, 4, node, maxdist_strict, isStrict, closeterms, firstedges, closeterms_dist, ncloseterms);
2397 int* RESTRICT closeterms,
2398 int* RESTRICT firstedges,
2400 int* RESTRICT ncloseterms
2404 tpathsGetKCloseTerms(g, tpaths, 4, node, maxdist_nonstrict, isStrict, closeterms, firstedges, closeterms_dist, ncloseterms);
#define STP_Vectype(type)
static void tpathsRepairExitLevel(SCIP *scip, int level, const GRAPH *g, TREPAIR *repair)
#define STP_TPATHS_RESERVESIZE
void graph_get3nextTermPaths(GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path3, int *vbase3, int *state3)
#define StpVecGetSize(vec)
static void tpathsRepairExit(SCIP *scip, const GRAPH *g, TREPAIR *repair)
SCIP_Bool graph_pc_isMw(const GRAPH *)
static void tpathsScan4th(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, int heapsize, TPATHS *tpaths, TREPAIR *repair)
void graph_tpathsGet4CloseTerms(const GRAPH *g, const TPATHS *tpaths, int node, SCIP_Real maxdist_strict, int *RESTRICT closeterms, int *RESTRICT firstedges, SCIP_Real *RESTRICT closeterms_dist, int *RESTRICT ncloseterms)
#define SCIPfreeMemoryArrayNull(scip, ptr)
static void tpathsScan3rd(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, int heapsize, TPATHS *tpaths, TREPAIR *repair)
#define SCIPfreeMemoryArray(scip, ptr)
void graph_tpathsGet3CloseTerms(const GRAPH *g, const TPATHS *tpaths, int node, SCIP_Real maxdist_strict, int *RESTRICT closeterms, int *RESTRICT firstedges, SCIP_Real *RESTRICT closeterms_dist, int *RESTRICT ncloseterms)
void graph_tpathsAdd2nd(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, TPATHS *tpaths)
#define SCIPallocMemoryArray(scip, ptr, num)
void graph_add3rdTermPaths(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path3, int *vbase3, int *state3)
static void tpathsResetMembers(const GRAPH *g, int level, TPATHS *tpaths)
void graph_knot_printInfo(const GRAPH *, int)
void graph_add4thTermPaths(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path4, int *vbase4, int *state4)
static SCIP_RETCODE tpathsRepair3rd(SCIP *scip, const GRAPH *g, TREPAIR *repair)
void graph_pathHeapAdd(const PATH *, int, int *RESTRICT, int *RESTRICT, int *)
enum SCIP_Retcode SCIP_RETCODE
includes various files containing graph methods used for Steiner tree problems
static void tpathsPrintPath(const GRAPH *g, const SDPROFIT *sdprofit, const TPATHS *tpaths, int node, int level)
SCIP_RETCODE graph_tpathsRecomputeBiased(const SDPROFIT *sdprofit, GRAPH *g, TPATHS *tpaths)
void graph_tpathsGetClosestTerm(const GRAPH *g, const TPATHS *tpaths, int node, int *RESTRICT closeterm, int *RESTRICT firstedge, SCIP_Real *RESTRICT closeterm_dist)
#define StpVecPopBack(vec)
#define StpVecReserve(scip, vec, _size_)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE graph_tpathsInit(SCIP *scip, GRAPH *g, TPATHS **tpaths)
void graph_tpathsAdd3rd(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, TPATHS *tpaths)
header only, simple implementation of an STL like vector
static SCIP_RETCODE tpathsAlloc(SCIP *scip, const GRAPH *g, TPATHS **tpaths)
static void utdist(SCIP *scip, const GRAPH *g, PATH *path, SCIP_Real ecost, int *vbase, int k, int l, int k2, int shift, int nnodes)
static void tpathsRepairTraverseLevel(SCIP *scip, const GRAPH *g, int level, TREPAIR *repair)
static void tpathsRepairUpdate1st(SCIP *scip, const GRAPH *g, TREPAIR *repair)
#define SCIPallocCleanBufferArray(scip, ptr, num)
static void tpathsRepairUpdateLevel(SCIP *scip, const GRAPH *g, int level, TREPAIR *repair)
void graph_tpathsSetAll2(GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, TPATHS *tpaths)
SCIP_RETCODE graph_tpathsRepair(SCIP *scip, int edge, SCIP_Bool withEdgeReplacement, const GRAPH *g, TPATHS *tpaths)
static void tpathsRepairTraverseLevelWithStack(SCIP *scip, const GRAPH *g, int level, TREPAIR *repair)
#define STP_TPATHS_NTERMBASES
void graph_get2nextTermPaths(GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path2, int *vbase2, int *state2)
#define StpVecGetcapacity(vec)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void pathheapCorrectDist(int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, PATH *RESTRICT path, int l, int k, int edge, SCIP_Real newdist)
static void tpathsBuild(SCIP *scip, GRAPH *g, TPATHS *tpaths)
void graph_add1stTermPaths(const GRAPH *g, const SCIP_Real *cost, PATH *path, int *vbase, int *state)
static void tpathsScan1st(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SDPROFIT *sdprofit, int heapsize, TPATHS *tpaths, TREPAIR *repair)
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
static int pathheapGetNearest(int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, const PATH *path)
void graph_tpathsPrintForNode(const GRAPH *g, const SDPROFIT *sdprofit, const TPATHS *tpaths, int node)
static SCIP_RETCODE tpathsRepair2nd(SCIP *scip, const GRAPH *g, TREPAIR *repair)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_Bool graph_edge_isDeleted(const GRAPH *, int)
static SCIP_RETCODE tpathsRepair1st(SCIP *scip, const GRAPH *g, TREPAIR *repair)
includes graph definitions used for Steiner tree problems
SCIP_Bool graph_isMarked(const GRAPH *)
void graph_add2ndTermPaths(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path2, int *vbase2, int *state2)
#define pathResetSingle(entry)
void graph_tpathsSetAll4(GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, TPATHS *tpaths)
#define tpathsRepairResetNode(scip, node, resetnodes, stack, nodes_isvisited)
SCIP_RETCODE graph_get4nextTTerms(SCIP *scip, GRAPH *g, const SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state)
static void tpathsGetKCloseTerms(const GRAPH *g, const TPATHS *tpaths, int maxnumber, int node, SCIP_Real maxdist, SCIP_Bool distIsStrict, int *RESTRICT closeterms, int *RESTRICT firstedges, SCIP_Real *RESTRICT closeterms_dist, int *RESTRICT ncloseterms)
#define BMScopyMemoryArray(ptr, source, num)
void graph_edge_printInfo(const GRAPH *, int)
static void tpathsScan2nd(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, int heapsize, TPATHS *tpaths, TREPAIR *repair)
#define StpVecIsEmpty(vec)
void graph_tpathsGet4CloseTermsLE(const GRAPH *g, const TPATHS *tpaths, int node, SCIP_Real maxdist_nonstrict, int *RESTRICT closeterms, int *RESTRICT firstedges, SCIP_Real *RESTRICT closeterms_dist, int *RESTRICT ncloseterms)
#define SCIPfreeMemory(scip, ptr)
static void tpathsRepairTraverseStackAddEdge(SCIP *scip, const GRAPH *g, int level, TREPAIR *repair)
void graph_tpathsAdd1st(const GRAPH *g, const SCIP_Real *cost, const SDPROFIT *sdprofit, TPATHS *tpaths)
static void tpathsRepairInit(SCIP *scip, const GRAPH *g, TREPAIR *repair)
static SCIP_RETCODE tpathsRepairInitLevel(SCIP *scip, int level, const GRAPH *g, TREPAIR *repair)
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
void graph_tpathsGetProfitNodes(SCIP *scip, const GRAPH *g, const TPATHS *tpaths, const SDPROFIT *sdprofit, int start, int base, STP_Vectype(int) profitnodes)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
static void tpathsBuildBiased(const SDPROFIT *sdprofit, GRAPH *g, TPATHS *tpaths)
#define SCIPfreeCleanBufferArray(scip, ptr)
void graph_get4nextTermPaths(GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path4, int *vbase4, int *state4)
#define StpVecFree(scip, vec)
void graph_tpathsFree(SCIP *scip, TPATHS **tpaths)
static SCIP_Real tpathsGetDistNew(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const int *vbase, int node, int nextnode, int edge, const SDPROFIT *sdprofit, const PATH *path)
struct tpaths_repair TREPAIR
static SCIP_Real reduce_sdprofitGetBiasedDist(const SDPROFIT *sdprofit, int node, SCIP_Real edgecost, SCIP_Real nodedist, int nonsource1, int nonsource2)
int graph_get_nNodes(const GRAPH *)
#define SCIPallocMemory(scip, ptr)
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
SCIP_RETCODE graph_tpathsRepairSetUp(const GRAPH *g, TPATHS *tpaths)
static void tpathsRepairTraverseStackAddBelow(SCIP *scip, const GRAPH *g, int level, TREPAIR *repair)
#define StpVecPushBack(scip, vec, value)
void graph_tpathsAdd4th(const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, TPATHS *tpaths)
#define LE_FEAS_EPS(a, b, eps)
static SCIP_RETCODE tpathsRepair4th(SCIP *scip, const GRAPH *g, TREPAIR *repair)
includes various reduction methods for Steiner tree problems
SCIP_RETCODE graph_tpathsInitBiased(SCIP *scip, const SDPROFIT *sdprofit, GRAPH *g, TPATHS **tpaths)
static SCIP_RETCODE tpathsRepairTraverse1st(SCIP *scip, int start, int pred, const GRAPH *g, TREPAIR *repair)
void graph_tpathsSetAll3(GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const SDPROFIT *sdprofit, TPATHS *tpaths)