45 #define RESTRICT restrict 56 #define GLOBALRELABEL_ADD 10 57 #define GLOBALRELABEL_MULT 10 60 #define listdelete(node,nodedist,next,headactive)\ 63 assert(nodedist >= 0);\ 64 assert(headactive != NULL);\ 65 headactive[nodedist] = next[node];\ 69 #define listinsert(node,nodedist,next,headactive,actmin,actmax)\ 72 assert(next != NULL);\ 73 assert(headactive != NULL);\ 74 assert(nodedist >= 0);\ 75 next[node] = headactive[nodedist];\ 76 headactive[nodedist] = node;\ 77 if( nodedist < (actmin) )\ 79 if( nodedist > (actmax) )\ 84 #define listinsert(node,nodedist,next,headactive,actmin,actmax)\ 87 assert(next != NULL);\ 88 assert(headactive != NULL);\ 89 assert(nodedist >= 0);\ 90 next[node] = headactive[nodedist];\ 91 headactive[nodedist] = node;\ 92 if( nodedist < (actmin) )\ 94 if( nodedist > (actmax) )\ 101 #define activedelete(node,nodedist,next,headactive)\ 104 assert(nodedist >= 0);\ 105 assert(headactive != NULL);\ 106 headactive[nodedist] = next[node];\ 110 #define activeinsert(node,nodedist,next,headactive,actmin,actmax,glbmax)\ 113 assert(next != NULL);\ 114 assert(headactive != NULL);\ 115 assert(nodedist >= 0);\ 116 next[node] = headactive[nodedist];\ 117 headactive[nodedist] = node;\ 118 if( nodedist < (actmin) )\ 120 if( nodedist > (actmax) )\ 122 if( (actmax) > (glbmax) )\ 127 #define inactivedelete(node,nodedist,next,prev,headinactive,nextnode,prevnode)\ 130 assert(nodedist >= 0);\ 131 assert(next != NULL);\ 132 assert(prev != NULL);\ 133 assert(headinactive != NULL);\ 134 nextnode = next[node];\ 135 if( headinactive[nodedist] == node )\ 137 headinactive[nodedist] = nextnode;\ 139 prev[nextnode] = Q_NULL;\ 143 prevnode = prev[node];\ 144 assert(prevnode >= 0);\ 145 assert(next[prevnode] == node);\ 146 next[prevnode] = nextnode;\ 148 prev[nextnode] = prevnode;\ 153 #define inactiveinsert(node,nodedist,next,prev,headinactive,nextnode)\ 156 assert(nodedist >= 0);\ 157 assert(next != NULL);\ 158 assert(prev != NULL);\ 159 assert(headinactive != NULL);\ 160 nextnode = headinactive[nodedist];\ 161 next[node] = nextnode;\ 162 prev[node] = Q_NULL;\ 164 prev[nextnode] = node;\ 165 headinactive[nodedist] = node;\ 170 static int is_valid(
const GRAPH*,
const int,
const int,
const int*,
const int *);
171 static void show_flow(
const GRAPH*,
const int*,
const int*);
174 static void cut_statist(
void);
175 static void cut_sum(
const GRAPH*,
const int*,
const int*);
179 static int s_pushes = 0;
180 static int n_pushes = 0;
181 static int m_pushes = 0;
182 static int x_pushes = 0;
183 static int relabels = 0;
184 static int s_sleeps = 0;
185 static int m_sleeps = 0;
186 static int searches = 0;
187 static int cutsums = 0;
195 static int is_valid_arr(
201 const int* revedgearr,
223 for(j = 0; j < p->
knots; j++)
226 return ((
void) fprintf(stderr,
"Negativ Execess Node %d\n", j),
FALSE);
228 if( dist[j] >= p->
knots )
229 return ((
void) fprintf(stderr,
"Distance too big Node %d dist: %d\n", j, dist[j]),
FALSE);
232 for( k = startarr[j], end = startarr[j + 1]; k != end; k++ )
238 if( dist[j] > dist[head] + 1 && w[j] == 0 && w[head] == 0 )
240 printf(
"distance fail! %d->%d (%d)\n", j, head, k);
244 if( (w[j] && (w[j] < w[head])) )
246 printf(
"Extended Dormacy Violation %d %d \n", j, head);
249 if( w[j] && !w[head] )
251 printf(
"Simple Dormacy Violation %d %d \n", j, head);
254 if( (w[j] && !w[head]) || (w[j] && (w[j] < w[head])) )
256 (void) printf(
"e=%d r[e]=%d head=%d tail=%d w[h]=%d w[t]=%d\n",
257 k, r[k], head, p->
tail[k], w[head],
260 return ((
void) fprintf(stderr,
261 "Dormacy Violation Knot %d\n", j),
FALSE);
266 return ((
void) fprintf(stderr,
"Negativ Residual Edge %d\n", k),
FALSE);
343 const int* edgestart,
357 assert(temp !=
NULL);
358 assert(dist !=
NULL);
361 assert(s < p->knots);
363 assert(t < p->knots);
372 for( j = 0; j < visited; j++ )
374 assert(visited <= nnodes);
377 dplus1 = dist[i] + 1;
381 assert(dist[i] >= 0);
382 assert(dist[i] < visited);
385 for( l = edgestart[i], end = edgestart[i + 1]; l != end; l++ )
390 if( dist[k] < 0 && w[k] == 0 )
396 assert(dist[k] < nnodes);
412 int* RESTRICT headactive,
413 int* RESTRICT headinactive,
414 int* RESTRICT edgecurr,
417 int* RESTRICT excess,
418 int* RESTRICT residual,
420 const int* edgestart,
445 assert(s < p->knots);
447 assert(t < p->knots);
450 assert(headactive !=
NULL);
451 assert(headinactive !=
NULL);
452 assert(edgecurr !=
NULL);
453 assert(prev !=
NULL);
454 assert(next !=
NULL);
455 assert(residual !=
NULL);
456 assert(excess !=
NULL);
457 assert(edgearr !=
NULL);
458 assert(headarr !=
NULL);
459 assert(edgecurr !=
NULL);
460 assert(edgestart !=
NULL);
461 assert(headactive !=
NULL);
462 assert(headinactive !=
NULL);
466 assert(*glbmax < nnodes);
472 for( i = 0; i <= end; i++ )
480 for( i = 0; i <
nnodes; i++ )
481 assert(headactive[i] ==
Q_NULL && headinactive[i] ==
Q_NULL);
483 for( i = end + 1; i <
nnodes; i++ )
500 for( currdist = 0;
TRUE; currdist++ )
502 nextdist = currdist + 1;
505 if( (headactive[currdist] < 0) && (headinactive[currdist] < 0) )
509 for( i = headinactive[currdist]; i >= 0; i = next[i] )
511 for( q = edgestart[i], end = edgestart[i + 1]; q != end; q++ )
513 if( residual[edgearr[q]] != 0 )
515 if( w[headarr[q]] < 0 )
522 edgecurr[k] = edgestart[k];
526 activeinsert(k, nextdist, next, headactive, actminloc, actmaxloc, glbmaxloc);
538 for( i = headactive[currdist]; i >= 0; i = next[i] )
540 for( q = edgestart[i], end = edgestart[i + 1]; q != end; q++ )
542 if( residual[edgearr[q]] != 0 )
551 edgecurr[k] = edgestart[k];
555 activeinsert(k, nextdist, next, headactive, actminloc, actmaxloc, glbmaxloc);
567 assert((headactive[currdist] ==
Q_NULL) && (headinactive[currdist] ==
Q_NULL));
568 assert(currdist == 0 || (headactive[currdist - 1] !=
Q_NULL) || (headinactive[currdist - 1] !=
Q_NULL));
571 if( (currdist - 1) > (glbmaxloc) )
572 glbmaxloc = currdist - 1;
578 dormmaxnext = (*dormmax) + 1;
579 for( i = 0; i <
nnodes; i++ )
588 *dormmax = dormmaxnext;
603 const int rootcutsize,
607 int* RESTRICT headactive,
608 int* RESTRICT headinactive,
609 int* RESTRICT edgecurr,
613 int* RESTRICT excess,
614 int* RESTRICT residual,
616 const int* edgestart,
642 assert(s < p->knots);
644 assert(t < p->knots);
646 assert(capa !=
NULL);
648 assert(headactive !=
NULL);
649 assert(headinactive !=
NULL);
650 assert(prev !=
NULL);
651 assert(next !=
NULL);
652 assert(temp !=
NULL);
653 assert(residual !=
NULL);
654 assert(excess !=
NULL);
655 assert(edgearr !=
NULL);
656 assert(headarr !=
NULL);
657 assert(edgecurr !=
NULL);
658 assert(edgestart !=
NULL);
659 assert(headactive !=
NULL);
660 assert(headinactive !=
NULL);
677 for( i = nnodes - 1; i >= 0; i-- )
698 activeinsert(i, 1, next, headactive, actminloc, actmaxloc, glbmaxloc);
710 assert(nnodes <= p->edges);
712 for( i = 0; i <
nnodes; i++ )
716 edgecurr[i] = edgestart[i];
720 residual[i] = capa[i];
723 for( e = nnodes; e < nedges; e++ )
724 residual[e] = capa[e];
731 for( q = edgestart[s], end = edgestart[s + 1]; q != end; q++ )
735 if( residual[e] == 0 )
741 assert(residual[e] == capa[e]);
743 residual[
flipedge(e)] += residual[e];
744 excess[i] += residual[e];
749 for( i = 0; i <
nnodes; i++ )
764 assert(excess[s] == 0);
776 activeinsert(i, 1, next, headactive, actminloc, actmaxloc, glbmaxloc);
789 (void)bfs(p, s, t, dist, temp, w, capa, edgestart, edgearr, headarr);
792 for( i = 0; i <
nnodes; i++ )
795 if( (*dormmax) == 1 )
810 assert(dist[t] == 0);
813 for( q = edgestart[s], end = edgestart[s + 1]; q != end; q++ )
817 if( residual[e] == 0 )
822 assert(residual[e] == capa[e]);
824 residual[
flipedge(e)] += residual[e];
825 excess[i] += residual[e];
832 for( i = 0; i <
nnodes; i++ )
844 activeinsert(i, dist[i], next, headactive, actminloc, actmaxloc, glbmaxloc);
848 if( dist[i] > (glbmaxloc) )
864 assert(is_valid(p, s, t, capa, w));
873 const int rootcutsize,
877 int* RESTRICT headactive,
878 int* RESTRICT headinactive,
879 int* RESTRICT edgecurr,
883 int* RESTRICT excess,
884 int* RESTRICT residual,
886 const int* edgestart,
916 assert(s < p->knots);
918 assert(t < p->knots);
920 assert(capa !=
NULL);
922 assert(dist !=
NULL);
923 assert(prev !=
NULL);
924 assert(next !=
NULL);
925 assert(temp !=
NULL);
926 assert(residual !=
NULL);
927 assert(excess !=
NULL);
928 assert(edgearr !=
NULL);
929 assert(headarr !=
NULL);
930 assert(edgecurr !=
NULL);
931 assert(edgestart !=
NULL);
932 assert(headactive !=
NULL);
933 assert(headinactive !=
NULL);
949 for( i = nnodes - 1; i >= 0; i-- )
958 edgecurr[i] = edgestart[i];
960 else if( w[i] > (dormmaxloc) )
969 for( i = nnodes - 1; i >= 0; i-- )
975 if( (w[i] == 0) || (w[i] >= wt) )
979 edgecurr[i] = edgestart[i];
981 else if( w[i] > (dormmaxloc) )
998 for( j = 0; j < visited; j++ )
1000 assert(visited <= nnodes);
1006 assert(dist[i] >= 0);
1007 assert(dist[i] < visited);
1010 for( l = edgestart[i], end = edgestart[i + 1]; l != end; l++ )
1015 if( dist[k] < 0 && w[k] == 0 )
1017 if( residual[edgearr[l]] > 0 )
1019 dist[k] = dist[i] + 1;
1020 temp[visited++] = k;
1021 assert(dist[k] < nnodes);
1026 activeinsert(k, dist[k], next, headactive, actminloc, actmaxloc, glbmaxloc);
1030 if( dist[k] > (glbmaxloc) )
1031 glbmaxloc = dist[k];
1042 dormmaxlocp1 = dormmaxloc + 1;
1043 for( i = nnodes - 1; i >= 0; i-- )
1046 if( dist[i] < 0 && w[i] == 0 )
1049 w[i] = dormmaxlocp1;
1057 for( i = nnodes - 1; i >= 0; i-- )
1069 for( j = edgestart[i], end = edgestart[i + 1]; j != end; j++ )
1071 headnode = headarr[j];
1076 assert(residual[
flipedge(a)] == 0);
1081 residual[
a] = capa[
a];
1088 assert(dist[t] == 0);
1089 assert(temp[0] == t);
1092 for( i = 1; i < visited && 0; i++ )
1102 activeinsert(k, dist[k], next, headactive, actminloc, actmaxloc, glbmaxloc);
1106 if( dist[k] > (glbmaxloc) )
1107 glbmaxloc = dist[k];
1114 *dormmax = dormmaxloc;
1115 *actmin = actminloc;
1116 *actmax = actmaxloc;
1117 *glbmax = glbmaxloc;
1120 assert(is_valid(p, s, t, capa, w));
1129 const int nnodesreal,
1130 const int nedgesreal,
1131 const int rootcutsize,
1135 const int* edgestart,
1170 int relabelupdatebnd;
1174 assert(s < p->knots);
1176 assert(t < p->knots);
1178 assert(capa !=
NULL);
1207 initialise(p, s, t, rootcutsize, rootcut, capa, dist, headactive, headinactive, edgecurr, next, prev, temp, e, r, w, edgestart,
1208 edgearr, headarr, &dormmax, &actmin, &actmax, &glbmax);
1210 reinitialise(p, s, t, rootcutsize, rootcut, capa, dist, headactive, headinactive, edgecurr, next, prev, temp, e, r, w, edgestart,
1211 edgearr, headarr, &dormmax, &actmin, &actmax, &glbmax);
1214 while( actmax >= actmin )
1217 if( headactive[actmax] < 0 )
1223 i = headactive[actmax];
1225 assert(actmax <= glbmax);
1226 assert(dist[i] == actmax);
1235 end = edgestart[i + 1];
1237 assert(end > edgestart[i]);
1243 for( j = edgecurr[i]; j != end; j++ )
1249 if( w[headarr[j]] == 0 )
1251 headnode = headarr[j];
1253 assert(w[headnode] == 0);
1254 assert(headnode != s);
1256 dminus1 = dist[i] - 1;
1259 if( dist[headnode] == dminus1 )
1261 assert(
Min(e[i], r[j]) > 0);
1264 if( e[headnode] == 0 )
1269 inactivedelete(headnode, dminus1, next, prev, headinactive, nextnode, prevnode);
1272 activeinsert(headnode, dminus1, next, headactive, actmin, actmax, glbmax);
1280 e[headnode] += r[j];
1281 r[edgearr[j]] += r[j];
1289 r[edgearr[j]] += e[i];
1291 e[headnode] += e[i];
1312 if( (headactive[dist[i]] < 0) && (headinactive[dist[i]] < 0) )
1317 assert(dormmax <= nnodes);
1318 assert(dist[i] < nnodes);
1321 for( j = dist[i] + 1; j <= glbmax; j++ )
1323 assert(headactive[j] ==
Q_NULL);
1325 for( l = headinactive[j]; l >= 0; l = next[l] )
1330 headinactive[j] =
Q_NULL;
1333 actmax = dist[i] - 1;
1342 assert(end == edgestart[i + 1]);
1354 for( ; j != end; j++ )
1360 if( w[headarr[j]] == 0 )
1363 if( dist[headarr[j]] < mindist )
1365 mindist = dist[headarr[j]];
1369 if( dist[headarr[j]] <= mindist )
1371 if( dist[headarr[j]] < mindist )
1373 mindist = dist[headarr[j]];
1377 minnode = headarr[j];
1378 maxresnode = headarr[j];
1380 else if( r[j] > maxresval )
1384 maxresnode = headarr[j];
1391 if( (++mindist) <
nnodes )
1393 assert(minedgestart >= 0);
1394 assert(r[minedgestart] > 0);
1399 if( glbmax < mindist )
1402 assert(maxresnode >= 0);
1403 assert(maxresnode == headarr[maxresedge]);
1406 if( r[minedgestart] >= e[i] )
1409 if( e[minnode] == 0 )
1413 inactivedelete(minnode, dist[minnode], next, prev, headinactive, nextnode, prevnode);
1414 activeinsert(minnode, dist[minnode], next, headactive, actmin, actmax, glbmax);
1418 r[edgearr[minedgestart]] += e[i];
1419 r[minedgestart] -= e[i];
1425 edgecurr[i] = minedgestart;
1432 if( e[minnode] == 0 )
1436 inactivedelete(minnode, dist[minnode], next, prev, headinactive, nextnode, prevnode);
1437 activeinsert(minnode, dist[minnode], next, headactive, actmin, actmax, glbmax);
1441 e[i] -= r[minedgestart];
1442 e[minnode] += r[minedgestart];
1443 r[edgearr[minedgestart]] += r[minedgestart];
1444 r[minedgestart] = 0;
1448 if( maxresval >= e[i] && minedgestart != maxresedge )
1451 if( e[maxresnode] == 0 )
1453 if( maxresnode != t )
1456 inactivedelete(maxresnode, dist[maxresnode], next, prev, headinactive, nextnode, prevnode);
1459 activeinsert(maxresnode, dist[maxresnode], next, headactive, actmin, actmax, glbmax);
1463 r[edgearr[maxresedge]] += e[i];
1464 r[maxresedge] -= e[i];
1465 e[maxresnode] += e[i];
1470 edgecurr[i] = minedgestart;
1475 edgecurr[i] = minedgestart + 1;
1486 assert(dormmax <= nnodes);
1488 assert(!((headactive[dist[i]] ==
Q_NULL) && (headinactive[dist[i]] ==
Q_NULL)));
1490 if( relabeltrigger > relabelupdatebnd )
1492 if( actmax < actmin )
1496 globalrelabel(p, s, t, dist, headactive, headinactive, edgecurr, next, prev,
1497 e, r, w, edgestart, edgearr, headarr, &actmin, &actmax, &glbmax, &dormmax);
1518 if( relabeltrigger > relabelupdatebnd )
1520 if( actmax < actmin )
1524 globalrelabel(p, s, t, dist, headactive, headinactive, edgecurr, next, prev,
1525 e, r, w, edgestart, edgearr, headarr, &actmin, &actmax, &glbmax, &dormmax);
1534 if( !is_valid_arr(p, s, t, edgestart, headarr, edgearr, r, capa, w) )
1535 printf(
"flow is not valid \n");
1536 assert(is_valid_arr(p, s, t, edgestart, headarr, edgearr, r, capa, w));
1542 cut_sum(p, capa, w);
1546 assert(is_valid(p, s, t, capa, w));
1551 static void cut_statist(
void)
1553 (void)printf(
"Mincut Statistics:\n");
1554 (void)printf(
"Node-Searches=%d, Cut Sums=%d\n",
1556 (void)printf(
"S-Pushes=%d, N-Pushes=%d, X-Pushes=%d, M-Pushes=%d\n",
1557 s_pushes, n_pushes, x_pushes, m_pushes);
1558 (void)printf(
"Relabels=%d, S-Sleeps=%d, M-Sleeps=%d\n\n",
1559 relabels, s_sleeps, m_sleeps);
1572 static void cut_sum(
1583 assert(capa !=
NULL);
1586 for(k = 0; k < p->
edges; k++)
1591 if ((w[i] && !w[j]) || (!w[i] && w[j]))
1595 (void)printf(
"Cut Sum=%d\n", sum);
1605 static int is_valid(
1634 for (j = 0; j < p->
knots; j++)
1640 if( dist[j] > dist[p->
head[k]] + 1 )
1642 printf(
"distance fail! %d->%d (%d)\n", j, p->
head[k], k);
1650 for(j = 0; j < p->
knots; j++)
1653 if ((q[j] >= 0) && (
a[q[j]] != j))
1654 return((
void)fprintf(stderr,
"Queue Error 1 Knot %d\n", j),
FALSE);
1656 if (!w[j] && (q[j] < 0) && (e[j] > 0) && (j != t))
1657 return((
void)fprintf(stderr,
"Queue Error 2 Knot %d\n", j),
FALSE);
1659 if (!w[j] && (q[j] >= 0) && (e[j] == 0))
1660 return((
void)fprintf(stderr,
"Queue Error 3 Knot %d\n", j),
FALSE);
1662 if (w[j] && (q[j] >= 0))
1663 return((
void)fprintf(stderr,
"Queue Error 4 Knot %d\n", j),
FALSE);
1666 return((
void)fprintf(stderr,
"Negativ Execess Knot %d\n", j),
FALSE);
1669 return((
void)fprintf(stderr,
"Distance too big Knot %d\n", j),
FALSE);
1678 if( dist[j] > dist[p->
head[k]] + 1 && w[j] == 0 && w[p->
head[k]] == 0 )
1680 printf(
"distance fail! %d->%d (%d)\n", j, p->
head[k], k);
1685 if((w[j] && (w[j] < w[p->
head[k]])))
1687 printf(
"fail %d %d\n", j, p->
head[k]);
1690 if( w[j] && !w[p->
head[k]] )
1692 printf(
"fail2 %d -> %d\n", j, p->
head[k]);
1693 printf(
"w: %d -> w: %d \n", w[j], w[p->
head[k]]);
1694 printf(
"edge %d \n", k);
1697 if ((w[j] && !w[p->
head[k]]) || (w[j] && (w[j] < w[p->
head[k]])))
1699 (void)printf(
"k=%d r[k]=%d head=%d tail=%d w[h]=%d w[t]=%d\n",
1702 return((
void)fprintf(stderr,
"Extended Dormacy Violation Knot %d\n", j),
FALSE);
1707 for(j = 0; j < p->
edges; j++)
1710 return((
void)fprintf(stderr,
"Negativ Residual Edge %d\n", j),
FALSE);
1713 return((
void)fprintf(stderr,
"Wrong Capacity Equation Edge %d\n", j),
FALSE);
1716 return((
void)fprintf(stderr,
"Negativ Flow Edge %d\n", j),
FALSE);
1718 if (r[j] != capa[j] - x[j] + x[
Edge_anti(j)])
1719 return((
void)fprintf(stderr,
"Wrong Residual Equation Edge %d\n", j),
FALSE);
1725 static void show_flow(
1760 for(j = 0; j < p->
edges; j++)
1761 (
void)printf(
"%6d ", j);
1762 (void)fputc(
'\n', stdout);
1764 (void)printf(
"ta:");
1765 for(j = 0; j < p->
edges; j++)
1766 (
void)printf(
"%6d ", p->
tail[j]);
1767 (void)fputc(
'\n', stdout);
1769 (void)printf(
"he:");
1770 for(j = 0; j < p->
edges; j++)
1771 (
void)printf(
"%6d ", p->
head[j]);
1772 (void)fputc(
'\n', stdout);
1774 (void)printf(
"x: ");
1775 for(j = 0; j < p->
edges; j++)
1776 (
void)printf(
"%6d ", x[j]);
1777 (void)fputc(
'\n', stdout);
1779 (void)printf(
"r: ");
1780 for(j = 0; j < p->
edges; j++)
1781 (
void)printf(
"%6d ", r[j]);
1782 (void)fputc(
'\n', stdout);
1784 (void)printf(
"ca:");
1785 for(j = 0; j < p->
edges; j++)
1786 (
void)printf(
"%6d ", capa[j]);
1787 (void)fputc(
'\n', stdout);
1789 (void)printf(
"w: ");
1790 for(j = 0; j < p->
knots; j++)
1791 (
void)printf(
"%2d ", w[j]);
1792 (void)fputc(
'\n', stdout);
1794 (void)printf(
"d: ");
1795 for(j = 0; j < p->
knots; j++)
1797 (void)fputc(
'\n', stdout);
1799 (void)printf(
"n: ");
1800 for(j = 0; j < p->
knots; j++)
1801 (
void)printf(
"%2d ", numb[j]);
1802 (void)fputc(
'\n', stdout);
1804 (void)printf(
"h: ");
1805 for(j = 0; j < p->
knots; j++)
1806 (
void)printf(
"%2d ", head[j]);
1807 (void)fputc(
'\n', stdout);
1809 (void)printf(
"p: ");
1810 for(j = 0; j < p->
knots; j++)
1811 (
void)printf(
"%2d ", prev[j]);
1812 (void)fputc(
'\n', stdout);
1814 (void)printf(
"n: ");
1815 for(j = 0; j < p->
knots; j++)
1816 (
void)printf(
"%2d ", next[j]);
1817 (void)fputc(
'\n', stdout);
1819 (void)printf(
"e: ");
1820 for(j = 0; j < p->
knots; j++)
1821 (
void)printf(
"%2d ", e[j]);
1822 (void)fputc(
'\n', stdout);
1929 inline static void delete(
1937 assert(q_dist !=
NULL);
1938 assert(q_head !=
NULL);
1939 assert(q_prev !=
NULL);
1940 assert(q_next !=
NULL);
1941 assert(q_dist[knot] > 0);
1943 if (q_next[knot] != Q_NM)
1947 if (q_prev[knot] ==
Q_NULL)
1949 assert(q_dist[knot] >= 0);
1950 assert(q_head[q_dist[knot]] == knot);
1952 q_head[q_dist[knot]] = q_next[knot];
1956 assert(q_prev[knot] >= 0);
1957 assert(q_next[q_prev[knot]] == knot);
1959 q_next[q_prev[knot]] = q_next[knot];
1964 if (q_next[knot] !=
Q_NULL)
1966 assert(q_next[knot] >= 0);
1967 assert(q_prev[q_next[knot]] == knot);
1969 q_prev[q_next[knot]] = q_prev[knot];
1971 q_next[knot] = Q_NM;
1972 q_prev[knot] = Q_NM;
1974 assert(q_next[knot] == Q_NM);
1975 assert(q_prev[knot] == Q_NM);
1978 inline static int insert(
1988 assert(q_dist !=
NULL);
1989 assert(q_head !=
NULL);
1990 assert(q_prev !=
NULL);
1991 assert(q_next !=
NULL);
1992 assert(q_dist[knot] > 0);
1995 if( q_prev[knot] == Q_NM )
1998 q_next[knot] = q_head[q_dist[knot]];
2000 if( q_next[knot] !=
Q_NULL )
2001 q_prev[q_next[knot]] = knot;
2003 q_head[q_dist[knot]] = knot;
2005 if( q_dist[knot] < dmin )
2006 dmin = q_dist[knot];
2007 if( q_dist[knot] > (*dlmax) )
2008 *dlmax = q_dist[knot];
2010 assert(q_next[knot] != Q_NM);
2011 assert(q_prev[knot] != Q_NM);
2012 assert(q_dist[knot] >= dmin);
2026 const int* edgestart,
2037 assert(q_temp !=
NULL);
2038 assert(q_dist !=
NULL);
2039 assert(q_numb !=
NULL);
2042 assert(s < p->knots);
2044 assert(t < p->knots);
2047 q_temp[visited++] = t;
2053 for(j = 0; (j < visited) && (visited < p->knots); j++)
2055 assert(visited < p->knots);
2056 assert(j < visited);
2061 assert(i < p->knots);
2062 assert(q_dist[i] >= 0);
2063 assert(q_dist[i] < visited);
2066 assert((j == 0) || (q_dist[i] >= q_dist[q_temp[j - 1]]));
2067 assert((j == visited - 1) || (q_dist[i] <= q_dist[q_temp[j + 1]]));
2071 for( k = edgestart[i], end = edgestart[i + 1]; k != end; k++ )
2077 assert(!w[l] || (q_dist[l] >= 0));
2081 q_dist[l] = q_dist[i] + 1;
2082 q_temp[visited++] = l;
2083 q_numb[q_dist[l]]++;
2085 assert(q_dist[l] < p->
knots);
2124 assert(s < p->knots);
2126 assert(t < p->knots);
2129 assert(q_head !=
NULL);
2130 assert(q_dist !=
NULL);
2131 assert(q_numb !=
NULL);
2132 assert(q_prev !=
NULL);
2133 assert(q_next !=
NULL);
2134 assert(q_temp !=
NULL);
2135 assert(excess !=
NULL);
2136 assert(transx !=
NULL);
2137 assert(residual !=
NULL);
2145 for( i = 0; i <
nnodes; i++ )
2160 q_temp[visited++] = t;
2164 for( j = 0; (j < visited) && (visited < nnodes); j++ )
2166 assert(visited < nnodes);
2167 assert(j < visited);
2173 assert(q_dist[i] < nnodes);
2176 dist1 = q_dist[i] + 1;
2178 assert(dist1 < nnodes);
2186 if( (w[l] < 0) && (residual[
flipedge(k)] > 0) )
2190 q_temp[visited++] = l;
2193 q_numb[q_dist[l]]++;
2198 listinsert(l, dist1, q_next, q_head, (*dmin), (*dlmax));
2200 assert(q_dist[l] < nnodes);
2207 for( i = 0; i <
nnodes; i++ )
2211 w[i] = *dormmax + 1;
2215 *dormmax = (*dormmax) + 1;
2248 const int* edgestart,
2264 assert(s < p->knots);
2266 assert(t < p->knots);
2268 assert(capa !=
NULL);
2270 assert(q_head !=
NULL);
2271 assert(q_dist !=
NULL);
2272 assert(q_numb !=
NULL);
2273 assert(q_prev !=
NULL);
2274 assert(q_next !=
NULL);
2275 assert(q_temp !=
NULL);
2276 assert(excess !=
NULL);
2277 assert(transx !=
NULL);
2278 assert(residual !=
NULL);
2286 actminloc = p->
knots;
2288 for(i = 0; i < p->
knots; i++)
2299 for(k = 0; k < p->
edges; k++)
2302 residual[k] = capa[k];
2306 (void)bfs(p, s, t, q_dist, q_numb, q_temp, w, edgestart, edgearr, headarr);
2310 for(i = 0; i < p->
knots; i++)
2312 w[i] = *dormmax + 1;
2323 assert(q_dist[s] > 0);
2325 assert(q_dist[t] == 0);
2329 q_numb[q_dist[s]]--;
2333 for( q = edgestart[s], end = edgestart[s + 1]; q != end; q++ )
2342 transx[k] = capa[k];
2346 excess[j] += transx[k];
2350 listinsert(j, q_dist[j], q_next, q_head, actminloc, (*dlmax));
2354 assert(excess[j] > 0);
2358 assert((p->
mincut_x)[k] <= capa[k]);
2362 show_flow(p, capa, w);
2365 assert(is_valid(p, s, t, capa, w));
2384 const int* edgestart,
2399 assert(s < p->knots);
2401 assert(t < p->knots);
2403 assert(capa !=
NULL);
2405 assert(q_head !=
NULL);
2406 assert(q_dist !=
NULL);
2407 assert(q_numb !=
NULL);
2408 assert(q_prev !=
NULL);
2409 assert(q_next !=
NULL);
2410 assert(q_temp !=
NULL);
2411 assert(excess !=
NULL);
2412 assert(transx !=
NULL);
2413 assert(residual !=
NULL);
2418 wt = (w[t] == 0) ? p->
knots + 1 : w[t];
2419 actminloc = p->
knots;
2423 for( i = 0; i < p->knots; i++ )
2430 if( (w[i] == 0) || (w[i] >= wt) )
2435 else if( w[i] > *dormmax )
2440 visited = bfs(p, s, t, q_dist, q_numb, q_temp, w, edgestart, edgearr, headarr);
2444 for( i = 0; i < p->
knots; i++ )
2447 w[i] = *dormmax + 1;
2448 else if( (w[i] == 0) && (q_dist[i] > *dlmax) )
2454 for( k = 0; k < p->
edges; k += 2 )
2464 excess[i] += transx[k + 1] - transx[k];
2465 excess[j] += transx[k] - transx[k + 1];
2467 residual[k] = capa[k];
2469 residual[k + 1] = capa[k + 1];
2474 assert(q_dist[t] == 0);
2475 assert(q_temp[0] == t);
2479 for( i = 1; i < visited; i++ )
2481 assert(w[q_temp[i]] == 0);
2482 assert(q_temp[i] != s);
2483 assert(q_temp[i] != t);
2485 if (excess[q_temp[i]] > 0)
2487 listinsert(q_temp[i], q_dist[q_temp[i]], q_next, q_head, actminloc, *dlmax);
2491 show_flow(p, capa, w);
2494 assert(is_valid(p, s, t, capa, w));
2513 const int rootcutsize,
2517 const int* edgestart,
2547 int relabelupdatebnd;
2552 assert(s < p->knots);
2554 assert(t < p->knots);
2556 assert(capa !=
NULL);
2583 initialise(p, s, t, capa, dist, numb, head, prev, next, temp, e, x, r, w, edgestart,
2584 edgearr, headarr, &dormmax, &dlmax);
2586 reinitialise(p, s, t, capa, dist, numb, head, prev, next, temp, e, x, r, w, edgestart,
2587 edgearr, headarr, &dormmax, &dlmax);
2590 while( dlmax >= dmin )
2592 if( (head[dlmax] ==
Q_NULL) )
2603 assert(dist[i] == dlmax);
2605 startind = edgestart[i];
2606 end = edgestart[i + 1];
2607 glbadd = (end - startind);
2625 for( j = startind; j != end; j++ )
2628 if( r[edgearr[j]] > 0 )
2631 if( w[headarr[j]] == 0 )
2634 headnode = headarr[j];
2637 if( di1 != dist[headnode] )
2639 assert(dist[i] <= dist[headnode]);
2641 if( (dist[headnode] < min_dist) || ((dist[headnode] == min_dist) && (r[k] > min_capa)) )
2643 min_knot = headnode;
2644 min_dist = dist[min_knot];
2651 assert(
Min(e[i], r[k]) > 0);
2653 assert(headnode == p->
head[k]);
2655 if( e[headnode] == 0 && headnode != t )
2657 listinsert(headnode, dist[headnode], next, head, dmin, (dlmax));
2663 (e[i] == r[k]) ? x_pushes++ : n_pushes++;
2668 e[headnode] += e[i];
2671 assert(e[headnode] > 0);
2672 assert(w[headnode] == 0);
2675 assert(r[k] == capa[k] - x[k] + x[
Edge_anti(k)]);
2682 e[headnode] += r[k];
2688 assert(r[k] == capa[k] - x[k] + x[
Edge_anti(k)]);
2711 assert(numb[dist[i]] > 0);
2713 if( numb[dist[i]] == 1 )
2720 assert(dormmax <= nnodes);
2722 for( k = 0; k <
nnodes; k++ )
2725 if (!w[k] && (dist[i] < dist[k]))
2744 assert(dormmax <= nnodes);
2754 assert(min_dist < nnodes);
2755 assert(min_capa > 0);
2756 assert(min_knot >= 0);
2757 assert(min_arc >= 0);
2763 dist[i] = min_dist + 1;
2767 assert(dist[i] < nnodes);
2769 assert(min_capa > 0);
2770 assert(min_capa == r[min_arc]);
2771 assert(p->
head[min_arc] == min_knot);
2772 assert(p->
tail[min_arc] == i);
2773 assert(dist[i] == dist[min_knot] + 1);
2774 assert(w[min_knot] == 0);
2776 if (e[i] <= min_capa)
2778 if( (e[p->
head[min_arc]] == 0) && (p->
head[min_arc] != t) )
2786 e[min_knot] += e[i];
2789 assert(r[min_arc] + r[
Edge_anti(min_arc)] == capa[min_arc] + capa[
Edge_anti(min_arc)]);
2790 assert(r[min_arc] >= 0);
2791 assert(r[min_arc] == capa[min_arc] - x[min_arc] + x[
Edge_anti(min_arc)]);
2796 if( relabeltrigger > relabelupdatebnd )
2799 globalrelabel(p, s, t, dist, numb, head, prev, next, temp, e, x, r, w, &dormmax, &dlmax, &dmin);
2808 if( relabeltrigger > relabelupdatebnd )
2811 globalrelabel(p, s, t, dist, numb, head, prev, next, temp, e, x, r, w, &dormmax, &dlmax, &dmin);
2822 fptr = fopen(
"f2",
"a");
2824 fprintf(fptr,
"t: %d flow %d \n", t, e[t]);
2833 cut_sum(p, capa, w);
2836 show_flow(p, capa, w);
2839 assert(is_valid(p, s, t, capa, w));
2844 static void cut_statist(
void)
2846 (void)printf(
"Mincut Statistics:\n");
2847 (void)printf(
"Node-Searches=%d, Cut Sums=%d\n",
2849 (void)printf(
"S-Pushes=%d, N-Pushes=%d, X-Pushes=%d, M-Pushes=%d\n",
2850 s_pushes, n_pushes, x_pushes, m_pushes);
2851 (void)printf(
"Relabels=%d, S-Sleeps=%d, M-Sleeps=%d\n\n",
2852 relabels, s_sleeps, m_sleeps);
2865 static void cut_sum(
2876 assert(capa !=
NULL);
2879 for(k = 0; k < p->
edges; k++)
2884 if ((w[i] && !w[j]) || (!w[i] && w[j]))
2888 (void)printf(
"Cut Sum=%d\n", sum);
2895 static int is_valid(
2917 for(j = 0; j < p->
knots; j++)
2920 if ((q[j] >= 0) && (
a[q[j]] != j))
2921 return((
void)fprintf(stderr,
"Queue Error 1 Knot %d\n", j),
FALSE);
2923 if (!w[j] && (q[j] < 0) && (e[j] > 0) && (j != t))
2924 return((
void)fprintf(stderr,
"Queue Error 2 Knot %d\n", j),
FALSE);
2926 if (!w[j] && (q[j] >= 0) && (e[j] == 0))
2927 return((
void)fprintf(stderr,
"Queue Error 3 Knot %d\n", j),
FALSE);
2929 if (w[j] && (q[j] >= 0))
2930 return((
void)fprintf(stderr,
"Queue Error 4 Knot %d\n", j),
FALSE);
2933 return((
void)fprintf(stderr,
"Negativ Execess Knot %d\n", j),
FALSE);
2936 return((
void)fprintf(stderr,
"Distance too big Knot %d\n", j),
FALSE);
2944 if ((w[j] && !w[p->
head[k]]) || (w[j] && (w[j] < w[p->
head[k]])))
2946 (void)printf(
"k=%d r[k]=%d head=%d tail=%d w[h]=%d w[t]=%d\n",
2949 return((
void)fprintf(stderr,
"Extended Dormacy Violation Knot %d\n", j),
FALSE);
2954 for(j = 0; j < p->
edges; j++)
2957 return((
void)fprintf(stderr,
"Negativ Residual Edge %d\n", j),
FALSE);
2960 return((
void)fprintf(stderr,
"Negativ Flow Edge %d\n", j),
FALSE);
2963 return((
void)fprintf(stderr,
"Wrong Capacity Equation Edge %d\n", j),
FALSE);
2965 if (r[j] != capa[j] - x[j] + x[
Edge_anti(j)])
2966 return((
void)fprintf(stderr,
"Wrong Residual Equation Edge %d\n", j),
FALSE);
2971 static void show_flow(
3006 for(j = 0; j < p->
edges; j++)
3007 (
void)printf(
"%6d ", j);
3008 (void)fputc(
'\n', stdout);
3010 (void)printf(
"ta:");
3011 for(j = 0; j < p->
edges; j++)
3012 (
void)printf(
"%6d ", p->
tail[j]);
3013 (void)fputc(
'\n', stdout);
3015 (void)printf(
"he:");
3016 for(j = 0; j < p->
edges; j++)
3017 (
void)printf(
"%6d ", p->
head[j]);
3018 (void)fputc(
'\n', stdout);
3020 (void)printf(
"x: ");
3021 for(j = 0; j < p->
edges; j++)
3022 (
void)printf(
"%6d ", x[j]);
3023 (void)fputc(
'\n', stdout);
3025 (void)printf(
"r: ");
3026 for(j = 0; j < p->
edges; j++)
3027 (
void)printf(
"%6d ", r[j]);
3028 (void)fputc(
'\n', stdout);
3030 (void)printf(
"ca:");
3031 for(j = 0; j < p->
edges; j++)
3032 (
void)printf(
"%6d ", capa[j]);
3033 (void)fputc(
'\n', stdout);
3035 (void)printf(
"w: ");
3036 for(j = 0; j < p->
knots; j++)
3037 (
void)printf(
"%2d ", w[j]);
3038 (void)fputc(
'\n', stdout);
3040 (void)printf(
"d: ");
3041 for(j = 0; j < p->
knots; j++)
3043 (void)fputc(
'\n', stdout);
3045 (void)printf(
"n: ");
3046 for(j = 0; j < p->
knots; j++)
3047 (
void)printf(
"%2d ", numb[j]);
3048 (void)fputc(
'\n', stdout);
3050 (void)printf(
"h: ");
3051 for(j = 0; j < p->
knots; j++)
3052 (
void)printf(
"%2d ", head[j]);
3053 (void)fputc(
'\n', stdout);
3055 (void)printf(
"p: ");
3056 for(j = 0; j < p->
knots; j++)
3057 (
void)printf(
"%2d ", prev[j]);
3058 (void)fputc(
'\n', stdout);
3060 (void)printf(
"n: ");
3061 for(j = 0; j < p->
knots; j++)
3062 (
void)printf(
"%2d ", next[j]);
3063 (void)fputc(
'\n', stdout);
3065 (void)printf(
"e: ");
3066 for(j = 0; j < p->
knots; j++)
3067 (
void)printf(
"%2d ", e[j]);
3068 (void)fputc(
'\n', stdout);
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
static void globalrelabel(const GRAPH *p, const int s, const int t, int *RESTRICT dist, int *RESTRICT headactive, int *RESTRICT headinactive, int *RESTRICT edgecurr, int *RESTRICT next, int *RESTRICT prev, int *RESTRICT excess, int *RESTRICT residual, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, int *actmin, int *actmax, int *glbmax, int *dormmax)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPallocMemoryArray(scip, ptr, num)
#define activeinsert(node, nodedist, next, headactive, actmin, actmax, glbmax)
int *RESTRICT mincut_temp
enum SCIP_Retcode SCIP_RETCODE
#define activedelete(node, nodedist, next, headactive)
#define inactivedelete(node, nodedist, next, prev, headinactive, nextnode, prevnode)
#define GLOBALRELABEL_ADD
int *RESTRICT mincut_dist
static void initialise(const GRAPH *p, const int s, const int t, const int rootcutsize, const int *rootcut, const int *capa, int *RESTRICT dist, int *RESTRICT headactive, int *RESTRICT headinactive, int *RESTRICT edgecurr, int *RESTRICT next, int *RESTRICT prev, int *RESTRICT temp, int *RESTRICT excess, int *RESTRICT residual, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, int *dormmax, int *actmin, int *actmax, int *glbmax)
static void reinitialise(const GRAPH *p, const int s, const int t, const int rootcutsize, const int *rootcut, const int *capa, int *RESTRICT dist, int *RESTRICT headactive, int *RESTRICT headinactive, int *RESTRICT edgecurr, int *RESTRICT next, int *RESTRICT prev, int *RESTRICT temp, int *RESTRICT excess, int *RESTRICT residual, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, int *dormmax, int *actmin, int *actmax, int *glbmax)
int *RESTRICT mincut_head_inact
SCIP_RETCODE graph_mincut_init(SCIP *scip, GRAPH *p)
void graph_mincut_exec(const GRAPH *p, const int s, const int t, const int nnodesreal, const int nedgesreal, const int rootcutsize, const int *rootcut, const int *capa, int *RESTRICT w, const int *edgestart, const int *edgearr, const int *headarr, const SCIP_Bool rerun)
int *RESTRICT mincut_head
#define GLOBALRELABEL_MULT
int *RESTRICT mincut_prev
includes various files containing graph methods used for Steiner tree problems
int *RESTRICT mincut_numb
void graph_mincut_exit(SCIP *scip, GRAPH *p)
#define listinsert(node, nodedist, next, headactive, actmin, actmax)
#define listdelete(node, nodedist, next, headactive)
#define inactiveinsert(node, nodedist, next, prev, headinactive, nextnode)
int *RESTRICT mincut_next