1.1 --- a/src/work/marci/augmenting_flow.h Mon Aug 30 12:01:47 2004 +0000
1.2 +++ b/src/work/marci/augmenting_flow.h Tue Aug 31 11:26:59 2004 +0000
1.3 @@ -1020,7 +1020,7 @@
1.4 break;
1.5 case AFTER_AUGMENTING:
1.6 // std::cout << "AFTER_AUGMENTING" << std::endl;
1.7 - for(g->first(v); g->valid(v); g->next(v)) {
1.8 + for(g->first(v); v!=INVALID; ++v) {
1.9 if (level[v]) {
1.10 M.set(v, true);
1.11 } else {
1.12 @@ -1030,7 +1030,7 @@
1.13 break;
1.14 case AFTER_FAST_AUGMENTING:
1.15 // std::cout << "AFTER_FAST_AUGMENTING" << std::endl;
1.16 - for(g->first(v); g->valid(v); g->next(v)) {
1.17 + for(g->first(v); v!=INVALID; ++v) {
1.18 if (level[v]==number_of_augmentations) {
1.19 M.set(v, true);
1.20 } else {
1.21 @@ -1053,7 +1053,7 @@
1.22 queue.pop();
1.23
1.24 OutEdgeIt e;
1.25 - for(g->first(e,w) ; g->valid(e); g->next(e)) {
1.26 + for(g->first(e,w) ; e!=INVALID; ++e) {
1.27 Node v=g->head(e);
1.28 if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
1.29 queue.push(v);
1.30 @@ -1062,7 +1062,7 @@
1.31 }
1.32
1.33 InEdgeIt f;
1.34 - for(g->first(f,w) ; g->valid(f); g->next(f)) {
1.35 + for(g->first(f,w) ; f!=INVALID; ++f) {
1.36 Node v=g->tail(f);
1.37 if (!M[v] && (*flow)[f] > 0 ) {
1.38 queue.push(v);
1.39 @@ -1133,11 +1133,11 @@
1.40 //searching for augmenting path
1.41 while ( !bfs.finished() ) {
1.42 ResGWOutEdgeIt e=bfs;
1.43 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.44 + if (e!=INVALID && bfs.isBNodeNewlyReached()) {
1.45 Node v=res_graph.tail(e);
1.46 Node w=res_graph.head(e);
1.47 pred.set(w, e);
1.48 - if (res_graph.valid(pred[v])) {
1.49 + if (pred[v]!=INVALID) {
1.50 free.set(w, std::min(free[v], res_graph.resCap(e)));
1.51 } else {
1.52 free.set(w, res_graph.resCap(e));
1.53 @@ -1151,7 +1151,7 @@
1.54 if (_augment) {
1.55 Node n=t;
1.56 Num augment_value=free[t];
1.57 - while (res_graph.valid(pred[n])) {
1.58 + while (pred[n]!=INVALID) {
1.59 ResGWEdge e=pred[n];
1.60 res_graph.augment(e, augment_value);
1.61 n=res_graph.tail(e);
1.62 @@ -1190,11 +1190,11 @@
1.63 //searching for augmenting path
1.64 while ( !bfs.finished() ) {
1.65 ResGWOutEdgeIt e=bfs;
1.66 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.67 + if (e!=INVALID && bfs.isBNodeNewlyReached()) {
1.68 Node v=res_graph.tail(e);
1.69 Node w=res_graph.head(e);
1.70 pred.set(w, e);
1.71 - if (res_graph.valid(pred[v])) {
1.72 + if (pred[v]!=INVALID) {
1.73 free.set(w, std::min(free[v], res_graph.resCap(e)));
1.74 } else {
1.75 free.set(w, res_graph.resCap(e));
1.76 @@ -1208,7 +1208,7 @@
1.77 if (_augment) {
1.78 Node n=t;
1.79 Num augment_value=free[t];
1.80 - while (res_graph.valid(pred[n])) {
1.81 + while (pred[n]!=INVALID) {
1.82 ResGWEdge e=pred[n];
1.83 res_graph.augment(e, augment_value);
1.84 n=res_graph.tail(e);
1.85 @@ -1244,7 +1244,7 @@
1.86 res_graph_to_F(res_graph);
1.87 {
1.88 typename ResGW::NodeIt n;
1.89 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
1.90 + for(res_graph.first(n); n!=INVALID; ++n) {
1.91 res_graph_to_F.set(n, F.addNode());
1.92 }
1.93 }
1.94 @@ -1256,7 +1256,7 @@
1.95
1.96 while ( !bfs.finished() ) {
1.97 ResGWOutEdgeIt e=bfs;
1.98 - if (res_graph.valid(e)) {
1.99 + if (e!=INVALID) {
1.100 if (bfs.isBNodeNewlyReached()) {
1.101 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.102 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
1.103 @@ -1299,7 +1299,7 @@
1.104 typename MG::Node v=F.aNode(dfs);
1.105 typename MG::Node w=F.bNode(dfs);
1.106 pred.set(w, dfs);
1.107 - if (F.valid(pred[v])) {
1.108 + if (pred[v]!=INVALID) {
1.109 free.set(w, std::min(free[v], residual_capacity[dfs]));
1.110 } else {
1.111 free.set(w, residual_capacity[dfs]);
1.112 @@ -1319,7 +1319,7 @@
1.113 if (__augment) {
1.114 typename MG::Node n=tF;
1.115 Num augment_value=free[tF];
1.116 - while (F.valid(pred[n])) {
1.117 + while (pred[n]!=INVALID) {
1.118 typename MG::Edge e=pred[n];
1.119 res_graph.augment(original_edge[e], augment_value);
1.120 n=F.tail(e);
1.121 @@ -1337,8 +1337,6 @@
1.122 }
1.123
1.124
1.125 -
1.126 -
1.127 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.128 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
1.129 {
1.130 @@ -1354,7 +1352,7 @@
1.131 DistanceMap<ResGW> dist(res_graph);
1.132 while ( !bfs.finished() ) {
1.133 ResGWOutEdgeIt e=bfs;
1.134 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.135 + if (e!=INVALID && bfs.isBNodeNewlyReached()) {
1.136 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.137 }
1.138 ++bfs;
1.139 @@ -1371,8 +1369,7 @@
1.140 typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
1.141 first_out_edges(filter_res_graph);
1.142 typename FilterResGW::NodeIt v;
1.143 - for(filter_res_graph.first(v); filter_res_graph.valid(v);
1.144 - filter_res_graph.next(v))
1.145 + for(filter_res_graph.first(v); v!=INVALID; ++v)
1.146 {
1.147 typename FilterResGW::OutEdgeIt e;
1.148 filter_res_graph.first(e, v);
1.149 @@ -1418,7 +1415,7 @@
1.150 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
1.151
1.152 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
1.153 - if (erasing_res_graph.valid(pred[v])) {
1.154 + if (pred[v]!=INVALID) {
1.155 free1.set
1.156 (w, std::min(free1[v], res_graph.resCap
1.157 (typename ErasingResGW::OutEdgeIt(dfs))));