1.1 --- a/src/work/edmonds_karp.h Wed Mar 17 16:10:33 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Wed Mar 17 17:04:41 2004 +0000
1.3 @@ -564,10 +564,10 @@
1.4 typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.5 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.6 if (S->get(s)) {
1.7 - Number f=0;
1.8 + Number u=0;
1.9 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.10 - f+=flow->get(e);
1.11 - if (f<1) {
1.12 + u+=flow->get(e);
1.13 + if (u<1) {
1.14 res_bfs.pushAndSetReached(s);
1.15 pred.set(s, AugEdge(INVALID));
1.16 }
1.17 @@ -589,10 +589,15 @@
1.18 } else {
1.19 free.set(w, res_graph.free(e));
1.20 }
1.21 - if (T->get(res_graph.head(e))) {
1.22 - n=res_graph.head(e);
1.23 - _augment=true;
1.24 - break;
1.25 + n=res_graph.head(e);
1.26 + if (T->get(n)) {
1.27 + Number u=0;
1.28 + for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.29 + u+=flow->get(f);
1.30 + if (u<1) {
1.31 + _augment=true;
1.32 + break;
1.33 + }
1.34 }
1.35 }
1.36
1.37 @@ -620,7 +625,27 @@
1.38 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.39 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.40
1.41 -// bfs.pushAndSetReached(s);
1.42 +
1.43 +
1.44 +
1.45 +
1.46 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.47 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.48 +// if (S->get(s)) {
1.49 +// Number u=0;
1.50 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.51 +// u+=flow->get(e);
1.52 +// if (u<1) {
1.53 +// res_bfs.pushAndSetReached(s);
1.54 +// //pred.set(s, AugEdge(INVALID));
1.55 +// }
1.56 +// }
1.57 +// }
1.58 +
1.59 +
1.60 +
1.61 +
1.62 +// //bfs.pushAndSetReached(s);
1.63 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.64 // while ( !bfs.finished() ) {
1.65 // AugOutEdgeIt e=bfs;
1.66 @@ -712,94 +737,132 @@
1.67
1.68 // return _augment;
1.69 // }
1.70 -// bool augmentOnBlockingFlow2() {
1.71 -// bool _augment=false;
1.72 + bool augmentOnBlockingFlow2() {
1.73 + bool _augment=false;
1.74
1.75 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.76 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.77 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.78 -// typedef typename EAugGraph::Edge EAugEdge;
1.79 + //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.80 + typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.81 + typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.82 + typedef typename EAugGraph::Edge EAugEdge;
1.83
1.84 -// EAugGraph res_graph(*G, *flow, *capacity);
1.85 + EAugGraph res_graph(*G, *flow, *capacity);
1.86
1.87 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.88 -// BfsIterator4<
1.89 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.90 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.91 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.92 + //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.93 + BfsIterator4<
1.94 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.95 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.96 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.97 +
1.98 +
1.99 + //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.100 + for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.101 + if (S->get(s)) {
1.102 + Number u=0;
1.103 + for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.104 + u+=flow->get(e);
1.105 + if (u<1) {
1.106 + bfs.pushAndSetReached(s);
1.107 + //pred.set(s, AugEdge(INVALID));
1.108 + }
1.109 + }
1.110 + }
1.111 +
1.112
1.113 -// bfs.pushAndSetReached(s);
1.114 + //bfs.pushAndSetReached(s);
1.115
1.116 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.117 -// NodeMap<int>& dist=res_graph.dist;
1.118 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.119 + NodeMap<int>& dist=res_graph.dist;
1.120
1.121 -// while ( !bfs.finished() ) {
1.122 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.123 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.124 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.125 -// }
1.126 -// ++bfs;
1.127 -// } //computing distances from s in the residual graph
1.128 + while ( !bfs.finished() ) {
1.129 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.130 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.131 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.132 + }
1.133 + ++bfs;
1.134 + } //computing distances from s in the residual graph
1.135
1.136 -// bool __augment=true;
1.137 + bool __augment=true;
1.138
1.139 -// while (__augment) {
1.140 + while (__augment) {
1.141
1.142 -// __augment=false;
1.143 -// //computing blocking flow with dfs
1.144 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.145 -// DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.146 -// dfs(res_graph);
1.147 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
1.148 -// pred.set(s, EAugEdge(INVALID));
1.149 -// //invalid iterators for sources
1.150 + __augment=false;
1.151 + //computing blocking flow with dfs
1.152 + typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.153 + DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.154 + dfs(res_graph);
1.155 + typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1.156 + //pred.set(s, EAugEdge(INVALID));
1.157 + //invalid iterators for sources
1.158
1.159 -// typename EAugGraph::NodeMap<Number> free(res_graph);
1.160 + typename EAugGraph::NodeMap<Number> free(res_graph);
1.161
1.162 -// dfs.pushAndSetReached(s);
1.163 -// while (!dfs.finished()) {
1.164 -// ++dfs;
1.165 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.166 -// if (dfs.isBNodeNewlyReached()) {
1.167 +
1.168 + //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.169 + for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.170 + if (S->get(s)) {
1.171 + Number u=0;
1.172 + for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.173 + u+=flow->get(e);
1.174 + if (u<1) {
1.175 + dfs.pushAndSetReached(s);
1.176 + //pred.set(s, AugEdge(INVALID));
1.177 + }
1.178 + }
1.179 + }
1.180 +
1.181 +
1.182 +
1.183 + //dfs.pushAndSetReached(s);
1.184 + typename EAugGraph::Node n;
1.185 + while (!dfs.finished()) {
1.186 + ++dfs;
1.187 + if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.188 + if (dfs.isBNodeNewlyReached()) {
1.189
1.190 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
1.191 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
1.192 + typename EAugGraph::Node v=res_graph.aNode(dfs);
1.193 + typename EAugGraph::Node w=res_graph.bNode(dfs);
1.194
1.195 -// pred.set(w, EAugOutEdgeIt(dfs));
1.196 -// if (res_graph.valid(pred.get(v))) {
1.197 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.198 -// } else {
1.199 -// free.set(w, res_graph.free(dfs));
1.200 -// }
1.201 -
1.202 -// if (w==t) {
1.203 -// __augment=true;
1.204 -// _augment=true;
1.205 -// break;
1.206 -// }
1.207 -// } else {
1.208 -// res_graph.erase(dfs);
1.209 -// }
1.210 -// }
1.211 + pred.set(w, EAugOutEdgeIt(dfs));
1.212 + if (res_graph.valid(pred.get(v))) {
1.213 + free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.214 + } else {
1.215 + free.set(w, res_graph.free(dfs));
1.216 + }
1.217 +
1.218 + n=w;
1.219 + if (T->get(w)) {
1.220 + Number u=0;
1.221 + for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.222 + u+=flow->get(f);
1.223 + if (u<1) {
1.224 + __augment=true;
1.225 + _augment=true;
1.226 + break;
1.227 + }
1.228 + }
1.229 + } else {
1.230 + res_graph.erase(dfs);
1.231 + }
1.232 + }
1.233
1.234 -// }
1.235 + }
1.236
1.237 -// if (__augment) {
1.238 -// typename EAugGraph::Node n=t;
1.239 -// Number augment_value=free.get(t);
1.240 -// while (res_graph.valid(pred.get(n))) {
1.241 -// EAugEdge e=pred.get(n);
1.242 -// res_graph.augment(e, augment_value);
1.243 -// n=res_graph.tail(e);
1.244 -// if (res_graph.free(e)==0)
1.245 -// res_graph.erase(e);
1.246 -// }
1.247 -// }
1.248 + if (__augment) {
1.249 + // typename EAugGraph::Node n=t;
1.250 + Number augment_value=free.get(n);
1.251 + while (res_graph.valid(pred.get(n))) {
1.252 + EAugEdge e=pred.get(n);
1.253 + res_graph.augment(e, augment_value);
1.254 + n=res_graph.tail(e);
1.255 + if (res_graph.free(e)==0)
1.256 + res_graph.erase(e);
1.257 + }
1.258 + }
1.259
1.260 -// }
1.261 + }
1.262
1.263 -// return _augment;
1.264 -// }
1.265 + return _augment;
1.266 + }
1.267 void run() {
1.268 //int num_of_augmentations=0;
1.269 while (augmentOnShortestPath()) {