1.1 --- a/src/work/edmonds_karp.h Tue Mar 30 17:47:51 2004 +0000
1.2 +++ b/src/work/edmonds_karp.h Wed Mar 31 15:50:21 2004 +0000
1.3 @@ -249,64 +249,63 @@
1.4
1.5 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
1.6 class MaxFlow {
1.7 - public:
1.8 - typedef typename GraphWrapper::Node Node;
1.9 - typedef typename GraphWrapper::Edge Edge;
1.10 - typedef typename GraphWrapper::EdgeIt EdgeIt;
1.11 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.12 - typedef typename GraphWrapper::InEdgeIt InEdgeIt;
1.13 -
1.14 - private:
1.15 + protected:
1.16 + typedef GraphWrapper GW;
1.17 + typedef typename GW::Node Node;
1.18 + typedef typename GW::Edge Edge;
1.19 + typedef typename GW::EdgeIt EdgeIt;
1.20 + typedef typename GW::OutEdgeIt OutEdgeIt;
1.21 + typedef typename GW::InEdgeIt InEdgeIt;
1.22 //const Graph* G;
1.23 - GraphWrapper gw;
1.24 + GW gw;
1.25 Node s;
1.26 Node t;
1.27 FlowMap* flow;
1.28 const CapacityMap* capacity;
1.29 - typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap >
1.30 - AugGraph;
1.31 - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.32 - typedef typename AugGraph::Edge AugEdge;
1.33 + typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
1.34 + typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.35 + typedef typename ResGW::Edge ResGWEdge;
1.36 + public:
1.37
1.38 - public:
1.39 - MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.40 + MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.41 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
1.42 +
1.43 bool augmentOnShortestPath() {
1.44 - AugGraph res_graph(gw, *flow, *capacity);
1.45 + ResGW res_graph(gw, *flow, *capacity);
1.46 bool _augment=false;
1.47
1.48 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.49 - BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.50 - res_bfs.pushAndSetReached(s);
1.51 + typedef typename ResGW::NodeMap<bool> ReachedMap;
1.52 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.53 + bfs.pushAndSetReached(s);
1.54
1.55 - typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.56 - pred.set(s, AugEdge(INVALID));
1.57 + typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
1.58 + pred.set(s, INVALID);
1.59
1.60 - typename AugGraph::NodeMap<Number> free(res_graph);
1.61 + typename ResGW::NodeMap<Number> free(res_graph);
1.62
1.63 //searching for augmenting path
1.64 - while ( !res_bfs.finished() ) {
1.65 - AugOutEdgeIt e=res_bfs;
1.66 - if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
1.67 + while ( !bfs.finished() ) {
1.68 + ResGWOutEdgeIt e=bfs;
1.69 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.70 Node v=res_graph.tail(e);
1.71 Node w=res_graph.head(e);
1.72 pred.set(w, e);
1.73 if (res_graph.valid(pred.get(v))) {
1.74 - free.set(w, std::min(free.get(v), res_graph.free(e)));
1.75 + free.set(w, std::min(free.get(v), res_graph.resCap(e)));
1.76 } else {
1.77 - free.set(w, res_graph.free(e));
1.78 + free.set(w, res_graph.resCap(e));
1.79 }
1.80 if (res_graph.head(e)==t) { _augment=true; break; }
1.81 }
1.82
1.83 - ++res_bfs;
1.84 + ++bfs;
1.85 } //end of searching augmenting path
1.86
1.87 if (_augment) {
1.88 Node n=t;
1.89 Number augment_value=free.get(t);
1.90 while (res_graph.valid(pred.get(n))) {
1.91 - AugEdge e=pred.get(n);
1.92 + ResGWEdge e=pred.get(n);
1.93 res_graph.augment(e, augment_value);
1.94 n=res_graph.tail(e);
1.95 }
1.96 @@ -330,48 +329,47 @@
1.97 };
1.98
1.99 template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.100 + typedef MutableGraph MG;
1.101 bool _augment=false;
1.102
1.103 - AugGraph res_graph(gw, *flow, *capacity);
1.104 + ResGW res_graph(gw, *flow, *capacity);
1.105
1.106 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.107 - BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.108 + typedef typename ResGW::NodeMap<bool> ReachedMap;
1.109 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.110
1.111 bfs.pushAndSetReached(s);
1.112 - //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.113 - DistanceMap<AugGraph> dist(res_graph);
1.114 + //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
1.115 + DistanceMap<ResGW> dist(res_graph);
1.116 while ( !bfs.finished() ) {
1.117 - AugOutEdgeIt e=bfs;
1.118 + ResGWOutEdgeIt e=bfs;
1.119 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.120 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.121 }
1.122 ++bfs;
1.123 } //computing distances from s in the residual graph
1.124
1.125 - MutableGraph F;
1.126 - typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
1.127 - FilterResGraph filter_res_graph(res_graph, dist);
1.128 - typename AugGraph::NodeMap<typename MutableGraph::Node>
1.129 - res_graph_to_F(res_graph);
1.130 - for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.131 + MG F;
1.132 + typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
1.133 + FilterResGW filter_res_graph(res_graph, dist);
1.134 + typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
1.135 + for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.136 res_graph_to_F.set(n, F.addNode());
1.137 }
1.138 -
1.139 - typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.140 - typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.141
1.142 - typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.143 - typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.144 + typename MG::Node sF=res_graph_to_F.get(s);
1.145 + typename MG::Node tF=res_graph_to_F.get(t);
1.146 + typename MG::EdgeMap<ResGWEdge> original_edge(F);
1.147 + typename MG::EdgeMap<Number> residual_capacity(F);
1.148
1.149 //Making F to the graph containing the edges of the residual graph
1.150 //which are in some shortest paths
1.151 - for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
1.152 + for(typename FilterResGW::EdgeIt e=filter_res_graph.template first<typename FilterResGW::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
1.153 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.154 - typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.155 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.156 original_edge.update();
1.157 original_edge.set(f, e);
1.158 residual_capacity.update();
1.159 - residual_capacity.set(f, res_graph.free(e));
1.160 + residual_capacity.set(f, res_graph.resCap(e));
1.161 //}
1.162 }
1.163
1.164 @@ -380,21 +378,21 @@
1.165 while (__augment) {
1.166 __augment=false;
1.167 //computing blocking flow with dfs
1.168 - typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.169 - DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
1.170 - typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.171 - pred.set(sF, typename MutableGraph::Edge(INVALID));
1.172 + typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
1.173 + DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
1.174 + typename MG::NodeMap<typename MG::Edge> pred(F);
1.175 + pred.set(sF, INVALID);
1.176 //invalid iterators for sources
1.177
1.178 - typename MutableGraph::NodeMap<Number> free(F);
1.179 + typename MG::NodeMap<Number> free(F);
1.180
1.181 dfs.pushAndSetReached(sF);
1.182 while (!dfs.finished()) {
1.183 ++dfs;
1.184 - if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.185 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
1.186 if (dfs.isBNodeNewlyReached()) {
1.187 - typename MutableGraph::Node v=F.aNode(dfs);
1.188 - typename MutableGraph::Node w=F.bNode(dfs);
1.189 + typename MG::Node v=F.aNode(dfs);
1.190 + typename MG::Node w=F.bNode(dfs);
1.191 pred.set(w, dfs);
1.192 if (F.valid(pred.get(v))) {
1.193 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.194 @@ -408,16 +406,16 @@
1.195 }
1.196
1.197 } else {
1.198 - F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.199 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
1.200 }
1.201 }
1.202 }
1.203
1.204 if (__augment) {
1.205 - typename MutableGraph::Node n=tF;
1.206 + typename MG::Node n=tF;
1.207 Number augment_value=free.get(tF);
1.208 while (F.valid(pred.get(n))) {
1.209 - typename MutableGraph::Edge e=pred.get(n);
1.210 + typename MG::Edge e=pred.get(n);
1.211 res_graph.augment(original_edge.get(e), augment_value);
1.212 n=F.tail(e);
1.213 if (residual_capacity.get(e)==augment_value)
1.214 @@ -433,46 +431,47 @@
1.215 }
1.216
1.217 template<typename MutableGraph> bool augmentOnBlockingFlow1() {
1.218 + typedef MutableGraph MG;
1.219 bool _augment=false;
1.220
1.221 - AugGraph res_graph(gw, *flow, *capacity);
1.222 + ResGW res_graph(gw, *flow, *capacity);
1.223
1.224 //bfs for distances on the residual graph
1.225 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.226 - BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
1.227 + typedef typename ResGW::NodeMap<bool> ReachedMap;
1.228 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.229 bfs.pushAndSetReached(s);
1.230 - typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.231 + typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
1.232
1.233 //F will contain the physical copy of the residual graph
1.234 - //with the set of edges which areon shortest paths
1.235 - MutableGraph F;
1.236 - typename AugGraph::NodeMap<typename MutableGraph::Node>
1.237 - res_graph_to_F(res_graph);
1.238 - for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.239 + //with the set of edges which are on shortest paths
1.240 + MG F;
1.241 + typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
1.242 + for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.243 res_graph_to_F.set(n, F.addNode());
1.244 }
1.245 - typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.246 - typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.247 - typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.248 - typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.249 +
1.250 + typename MG::Node sF=res_graph_to_F.get(s);
1.251 + typename MG::Node tF=res_graph_to_F.get(t);
1.252 + typename MG::EdgeMap<ResGWEdge> original_edge(F);
1.253 + typename MG::EdgeMap<Number> residual_capacity(F);
1.254
1.255 while ( !bfs.finished() ) {
1.256 - AugOutEdgeIt e=bfs;
1.257 + ResGWOutEdgeIt e=bfs;
1.258 if (res_graph.valid(e)) {
1.259 if (bfs.isBNodeNewlyReached()) {
1.260 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.261 - typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.262 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.263 original_edge.update();
1.264 original_edge.set(f, e);
1.265 residual_capacity.update();
1.266 - residual_capacity.set(f, res_graph.free(e));
1.267 + residual_capacity.set(f, res_graph.resCap(e));
1.268 } else {
1.269 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
1.270 - typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.271 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.272 original_edge.update();
1.273 original_edge.set(f, e);
1.274 residual_capacity.update();
1.275 - residual_capacity.set(f, res_graph.free(e));
1.276 + residual_capacity.set(f, res_graph.resCap(e));
1.277 }
1.278 }
1.279 }
1.280 @@ -484,21 +483,21 @@
1.281 while (__augment) {
1.282 __augment=false;
1.283 //computing blocking flow with dfs
1.284 - typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
1.285 - DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
1.286 - typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.287 - pred.set(sF, typename MutableGraph::Edge(INVALID));
1.288 + typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
1.289 + DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
1.290 + typename MG::NodeMap<typename MG::Edge> pred(F);
1.291 + pred.set(sF, INVALID);
1.292 //invalid iterators for sources
1.293
1.294 - typename MutableGraph::NodeMap<Number> free(F);
1.295 + typename MG::NodeMap<Number> free(F);
1.296
1.297 dfs.pushAndSetReached(sF);
1.298 while (!dfs.finished()) {
1.299 ++dfs;
1.300 - if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.301 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
1.302 if (dfs.isBNodeNewlyReached()) {
1.303 - typename MutableGraph::Node v=F.aNode(dfs);
1.304 - typename MutableGraph::Node w=F.bNode(dfs);
1.305 + typename MG::Node v=F.aNode(dfs);
1.306 + typename MG::Node w=F.bNode(dfs);
1.307 pred.set(w, dfs);
1.308 if (F.valid(pred.get(v))) {
1.309 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.310 @@ -512,16 +511,16 @@
1.311 }
1.312
1.313 } else {
1.314 - F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.315 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
1.316 }
1.317 }
1.318 }
1.319
1.320 if (__augment) {
1.321 - typename MutableGraph::Node n=tF;
1.322 + typename MG::Node n=tF;
1.323 Number augment_value=free.get(tF);
1.324 while (F.valid(pred.get(n))) {
1.325 - typename MutableGraph::Edge e=pred.get(n);
1.326 + typename MG::Edge e=pred.get(n);
1.327 res_graph.augment(original_edge.get(e), augment_value);
1.328 n=F.tail(e);
1.329 if (residual_capacity.get(e)==augment_value)
1.330 @@ -536,6 +535,106 @@
1.331 return _augment;
1.332 }
1.333
1.334 + bool augmentOnBlockingFlow2() {
1.335 + bool _augment=false;
1.336 +
1.337 + ResGW res_graph(gw, *flow, *capacity);
1.338 +
1.339 + typedef typename ResGW::NodeMap<bool> ReachedMap;
1.340 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.341 +
1.342 + bfs.pushAndSetReached(s);
1.343 + DistanceMap<ResGW> dist(res_graph);
1.344 + while ( !bfs.finished() ) {
1.345 + ResGWOutEdgeIt e=bfs;
1.346 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.347 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.348 + }
1.349 + ++bfs;
1.350 + } //computing distances from s in the residual graph
1.351 +
1.352 + //Subgraph containing the edges on some shortest paths
1.353 + typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
1.354 + FilterResGW filter_res_graph(res_graph, dist);
1.355 +
1.356 + //Subgraph, which is able to delete edges which are already
1.357 + //met by the dfs
1.358 + typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
1.359 + first_out_edges(filter_res_graph);
1.360 + typename FilterResGW::NodeIt v;
1.361 + for(filter_res_graph.first(v); filter_res_graph.valid(v);
1.362 + filter_res_graph.next(v))
1.363 + {
1.364 + typename FilterResGW::OutEdgeIt e;
1.365 + filter_res_graph.first(e, v);
1.366 + first_out_edges.set(v, e);
1.367 + }
1.368 + typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
1.369 + NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
1.370 + ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
1.371 +
1.372 + bool __augment=true;
1.373 +
1.374 + while (__augment) {
1.375 +
1.376 + __augment=false;
1.377 + //computing blocking flow with dfs
1.378 + typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
1.379 + DfsIterator5< ErasingResGW, BlockingReachedMap >
1.380 + dfs(erasing_res_graph);
1.381 + typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
1.382 + pred(erasing_res_graph);
1.383 + pred.set(s, INVALID);
1.384 + //invalid iterators for sources
1.385 +
1.386 + typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
1.387 +
1.388 + dfs.pushAndSetReached(s);
1.389 + while (!dfs.finished()) {
1.390 + ++dfs;
1.391 + if (erasing_res_graph.valid(
1.392 + /*typename ErasingResGW::OutEdgeIt*/(dfs)))
1.393 + {
1.394 + if (dfs.isBNodeNewlyReached()) {
1.395 +
1.396 + typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
1.397 + typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
1.398 +
1.399 + pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
1.400 + if (erasing_res_graph.valid(pred.get(v))) {
1.401 + free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
1.402 + } else {
1.403 + free.set(w, res_graph.resCap(dfs));
1.404 + }
1.405 +
1.406 + if (w==t) {
1.407 + __augment=true;
1.408 + _augment=true;
1.409 + break;
1.410 + }
1.411 + } else {
1.412 + erasing_res_graph.erase(dfs);
1.413 + }
1.414 + }
1.415 + }
1.416 +
1.417 + if (__augment) {
1.418 + typename ErasingResGW::Node n=t;
1.419 + Number augment_value=free.get(n);
1.420 + while (erasing_res_graph.valid(pred.get(n))) {
1.421 + typename ErasingResGW::OutEdgeIt e=pred.get(n);
1.422 + res_graph.augment(e, augment_value);
1.423 + n=erasing_res_graph.tail(e);
1.424 + if (res_graph.resCap(e)==0)
1.425 + erasing_res_graph.erase(e);
1.426 + }
1.427 + }
1.428 +
1.429 + } //while (__augment)
1.430 +
1.431 + return _augment;
1.432 + }
1.433 +
1.434 // bool augmentOnBlockingFlow2() {
1.435 // bool _augment=false;
1.436
1.437 @@ -624,22 +723,25 @@
1.438
1.439 // return _augment;
1.440 // }
1.441 -// void run() {
1.442 -// //int num_of_augmentations=0;
1.443 -// while (augmentOnShortestPath()) {
1.444 -// //while (augmentOnBlockingFlow<MutableGraph>()) {
1.445 -// //std::cout << ++num_of_augmentations << " ";
1.446 -// //std::cout<<std::endl;
1.447 -// }
1.448 -// }
1.449 -// template<typename MutableGraph> void run() {
1.450 -// //int num_of_augmentations=0;
1.451 -// //while (augmentOnShortestPath()) {
1.452 -// while (augmentOnBlockingFlow<MutableGraph>()) {
1.453 -// //std::cout << ++num_of_augmentations << " ";
1.454 -// //std::cout<<std::endl;
1.455 -// }
1.456 -// }
1.457 +
1.458 + void run() {
1.459 + //int num_of_augmentations=0;
1.460 + while (augmentOnShortestPath()) {
1.461 + //while (augmentOnBlockingFlow<MutableGraph>()) {
1.462 + //std::cout << ++num_of_augmentations << " ";
1.463 + //std::cout<<std::endl;
1.464 + }
1.465 + }
1.466 +
1.467 + template<typename MutableGraph> void run() {
1.468 + //int num_of_augmentations=0;
1.469 + //while (augmentOnShortestPath()) {
1.470 + while (augmentOnBlockingFlow<MutableGraph>()) {
1.471 + //std::cout << ++num_of_augmentations << " ";
1.472 + //std::cout<<std::endl;
1.473 + }
1.474 + }
1.475 +
1.476 Number flowValue() {
1.477 Number a=0;
1.478 OutEdgeIt e;
1.479 @@ -648,6 +750,7 @@
1.480 }
1.481 return a;
1.482 }
1.483 +
1.484 };
1.485
1.486
1.487 @@ -684,7 +787,7 @@
1.488 // bool _augment=false;
1.489
1.490 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.491 -// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.492 +// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
1.493 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.494 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.495 // if ((S->get(s)) && (used.get(s)<1) ) {
1.496 @@ -692,7 +795,7 @@
1.497 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.498 // //u+=flow->get(e);
1.499 // //if (u<1) {
1.500 -// res_bfs.pushAndSetReached(s);
1.501 +// bfs.pushAndSetReached(s);
1.502 // pred.set(s, AugEdge(INVALID));
1.503 // //}
1.504 // }
1.505 @@ -702,9 +805,9 @@
1.506
1.507 // Node n;
1.508 // //searching for augmenting path
1.509 -// while ( !res_bfs.finished() ) {
1.510 -// AugOutEdgeIt e=res_bfs;
1.511 -// if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
1.512 +// while ( !bfs.finished() ) {
1.513 +// AugOutEdgeIt e=bfs;
1.514 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.515 // Node v=res_graph.tail(e);
1.516 // Node w=res_graph.head(e);
1.517 // pred.set(w, e);
1.518 @@ -725,7 +828,7 @@
1.519 // }
1.520 // }
1.521
1.522 -// ++res_bfs;
1.523 +// ++bfs;
1.524 // } //end of searching augmenting path
1.525
1.526 // if (_augment) {
1.527 @@ -762,7 +865,7 @@
1.528 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.529 // // u+=flow->get(e);
1.530 // // if (u<1) {
1.531 -// // res_bfs.pushAndSetReached(s);
1.532 +// // bfs.pushAndSetReached(s);
1.533 // // //pred.set(s, AugEdge(INVALID));
1.534 // // }
1.535 // // }
1.536 @@ -1056,12 +1159,12 @@
1.537 // // Node reached_t_node;
1.538
1.539 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.540 -// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.541 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.542 // // for(typename std::list<Node>::const_iterator i=S.begin();
1.543 // // i!=S.end(); ++i) {
1.544 -// // res_bfs.pushAndSetReached(*i);
1.545 +// // bfs.pushAndSetReached(*i);
1.546 // // }
1.547 -// // //res_bfs.pushAndSetReached(s);
1.548 +// // //bfs.pushAndSetReached(s);
1.549
1.550 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.551 // // //filled up with invalid iterators
1.552 @@ -1069,9 +1172,9 @@
1.553 // // typename AugGraph::NodeMap<Number> free(res_graph);
1.554
1.555 // // //searching for augmenting path
1.556 -// // while ( !res_bfs.finished() ) {
1.557 -// // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.558 -// // if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.559 +// // while ( !bfs.finished() ) {
1.560 +// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.561 +// // if (e.valid() && bfs.isBNodeNewlyReached()) {
1.562 // // Node v=res_graph.tail(e);
1.563 // // Node w=res_graph.head(e);
1.564 // // pred.set(w, e);
1.565 @@ -1087,7 +1190,7 @@
1.566 // // }
1.567 // // }
1.568
1.569 -// // ++res_bfs;
1.570 +// // ++bfs;
1.571 // // } //end of searching augmenting path
1.572
1.573 // // if (_augment) {
2.1 --- a/src/work/marci/edmonds_karp_demo.cc Tue Mar 30 17:47:51 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp_demo.cc Wed Mar 31 15:50:21 2004 +0000
2.3 @@ -90,7 +90,6 @@
2.4
2.5
2.6 {
2.7 - //std::cout << "SmartGraph..." << std::endl;
2.8 typedef TrivGraphWrapper<const Graph> GW;
2.9 GW gw(G);
2.10 std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
2.11 @@ -122,7 +121,6 @@
2.12 }
2.13
2.14 {
2.15 - //std::cout << "SmartGraph..." << std::endl;
2.16 typedef TrivGraphWrapper<const Graph> GW;
2.17 GW gw(G);
2.18 std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
2.19 @@ -153,32 +151,36 @@
2.20 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.21 }
2.22
2.23 -// {
2.24 -// std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
2.25 -// Graph::EdgeMap<int> flow(G); //0 flow
2.26 + {
2.27 + typedef TrivGraphWrapper<const Graph> GW;
2.28 + GW gw(G);
2.29 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
2.30 + GW::EdgeMap<int> flow(G); //0 flow
2.31
2.32 -// Timer ts;
2.33 -// ts.reset();
2.34 + Timer ts;
2.35 + ts.reset();
2.36
2.37 -// MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.38 -// int i=0;
2.39 -// while (max_flow_test.augmentOnBlockingFlow2()) {
2.40 -// // for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.41 -// // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.42 -// // }
2.43 -// // std::cout<<std::endl;
2.44 -// ++i;
2.45 + typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
2.46 + EMW cw(cap);
2.47 + MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
2.48 + int i=0;
2.49 + while (max_flow_test.augmentOnBlockingFlow2()) {
2.50 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
2.51 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.52 // }
2.53 +// std::cout<<std::endl;
2.54 + ++i;
2.55 + }
2.56
2.57 -// // std::cout << "maximum flow: "<< std::endl;
2.58 -// // for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
2.59 -// // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.60 -// // }
2.61 -// // std::cout<<std::endl;
2.62 -// std::cout << "elapsed time: " << ts << std::endl;
2.63 -// std::cout << "number of augmentation phases: " << i << std::endl;
2.64 -// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.65 +// std::cout << "maximum flow: "<< std::endl;
2.66 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
2.67 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.68 // }
2.69 +// std::cout<<std::endl;
2.70 + std::cout << "elapsed time: " << ts << std::endl;
2.71 + std::cout << "number of augmentation phases: " << i << std::endl;
2.72 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.73 + }
2.74
2.75 {
2.76 typedef TrivGraphWrapper<const Graph> GW;
2.77 @@ -189,7 +191,6 @@
2.78 Timer ts;
2.79 ts.reset();
2.80
2.81 - //CM cm;
2.82 typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
2.83 EMW cw(cap);
2.84 MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
3.1 --- a/src/work/marci/graph_wrapper.h Tue Mar 30 17:47:51 2004 +0000
3.2 +++ b/src/work/marci/graph_wrapper.h Wed Mar 31 15:50:21 2004 +0000
3.3 @@ -999,11 +999,11 @@
3.4 protected:
3.5 OutEdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
3.6 resG.gw.first(out, v);
3.7 - while( resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
3.8 + while( resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
3.9 if (!resG.gw.valid(out)) {
3.10 out_or_in=0;
3.11 resG.gw.first(in, v);
3.12 - while( resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
3.13 + while( resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
3.14 }
3.15 }
3.16 // public:
3.17 @@ -1011,15 +1011,15 @@
3.18 // if (out_or_in) {
3.19 // Node v=/*resG->*/G->aNode(out);
3.20 // ++out;
3.21 -// while( out.valid() && !(Edge::free()>0) ) { ++out; }
3.22 +// while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
3.23 // if (!out.valid()) {
3.24 // out_or_in=0;
3.25 // G->first(in, v);
3.26 -// while( in.valid() && !(Edge::free()>0) ) { ++in; }
3.27 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.28 // }
3.29 // } else {
3.30 // ++in;
3.31 -// while( in.valid() && !(Edge::free()>0) ) { ++in; }
3.32 +// while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.33 // }
3.34 // return *this;
3.35 // }
3.36 @@ -1037,52 +1037,52 @@
3.37 EdgeIt(const Invalid& i) : Edge(i) { }
3.38 EdgeIt(const ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap>& resG) : Edge() {
3.39 resG.gw.first(v);
3.40 - if (resG.gw.valid(v)) resG.gw.first(out, v); else out=/*OldOutEdgeIt*/(INVALID);
3.41 - while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
3.42 + if (resG.gw.valid(v)) resG.gw.first(out, v); else out=INVALID;
3.43 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
3.44 while (resG.gw.valid(v) && !resG.gw.valid(out)) {
3.45 resG.gw.next(v);
3.46 if (resG.gw.valid(v)) resG.gw.first(out, v);
3.47 - while (resG.gw.valid(out) && !(resG.free(out)>0) ) { resG.gw.next(out); }
3.48 + while (resG.gw.valid(out) && !(resG.resCap(out)>0) ) { resG.gw.next(out); }
3.49 }
3.50 if (!resG.gw.valid(out)) {
3.51 out_or_in=0;
3.52 resG.gw.first(v);
3.53 - if (resG.gw.valid(v)) resG.gw.first(in, v); else in=/*OldInEdgeIt*/(INVALID);
3.54 - while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
3.55 + if (resG.gw.valid(v)) resG.gw.first(in, v); else in=INVALID;
3.56 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
3.57 while (resG.gw.valid(v) && !resG.gw.valid(in)) {
3.58 resG.gw.next(v);
3.59 if (resG.gw.valid(v)) resG.gw.first(in, v);
3.60 - while (resG.gw.valid(in) && !(resG.free(in)>0) ) { resG.gw.next(in); }
3.61 + while (resG.gw.valid(in) && !(resG.resCap(in)>0) ) { resG.gw.next(in); }
3.62 }
3.63 }
3.64 }
3.65 // EdgeIt& operator++() {
3.66 // if (out_or_in) {
3.67 // ++out;
3.68 -// while (out.valid() && !(Edge::free()>0) ) { ++out; }
3.69 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
3.70 // while (v.valid() && !out.valid()) {
3.71 // ++v;
3.72 // if (v.valid()) G->first(out, v);
3.73 -// while (out.valid() && !(Edge::free()>0) ) { ++out; }
3.74 +// while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
3.75 // }
3.76 // if (!out.valid()) {
3.77 // out_or_in=0;
3.78 // G->first(v);
3.79 // if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
3.80 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
3.81 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.82 // while (v.valid() && !in.valid()) {
3.83 // ++v;
3.84 // if (v.valid()) G->first(in, v);
3.85 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
3.86 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.87 // }
3.88 // }
3.89 // } else {
3.90 // ++in;
3.91 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
3.92 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.93 // while (v.valid() && !in.valid()) {
3.94 // ++v;
3.95 // if (v.valid()) G->first(in, v);
3.96 -// while (in.valid() && !(Edge::free()>0) ) { ++in; }
3.97 +// while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.98 // }
3.99 // }
3.100 // return *this;
3.101 @@ -1105,15 +1105,15 @@
3.102 if (e.out_or_in) {
3.103 Node v=gw.aNode(e.out);
3.104 gw.next(e.out);
3.105 - while( gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
3.106 + while( gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
3.107 if (!gw.valid(e.out)) {
3.108 e.out_or_in=0;
3.109 gw.first(e.in, v);
3.110 - while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
3.111 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
3.112 }
3.113 } else {
3.114 gw.next(e.in);
3.115 - while( gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
3.116 + while( gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
3.117 }
3.118 return e;
3.119 }
3.120 @@ -1121,30 +1121,30 @@
3.121 EdgeIt& next(EdgeIt& e) const {
3.122 if (e.out_or_in) {
3.123 gw.next(e.out);
3.124 - while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
3.125 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
3.126 while (gw.valid(e.v) && !gw.valid(e.out)) {
3.127 gw.next(e.v);
3.128 if (gw.valid(e.v)) gw.first(e.out, e.v);
3.129 - while (gw.valid(e.out) && !(free(e.out)>0) ) { gw.next(e.out); }
3.130 + while (gw.valid(e.out) && !(resCap(e.out)>0) ) { gw.next(e.out); }
3.131 }
3.132 if (!gw.valid(e.out)) {
3.133 e.out_or_in=0;
3.134 gw.first(e.v);
3.135 - if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=/*OldInEdgeIt*/(INVALID);
3.136 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
3.137 + if (gw.valid(e.v)) gw.first(e.in, e.v); else e.in=INVALID;
3.138 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
3.139 while (gw.valid(e.v) && !gw.valid(e.in)) {
3.140 gw.next(e.v);
3.141 if (gw.valid(e.v)) gw.first(e.in, e.v);
3.142 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
3.143 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
3.144 }
3.145 }
3.146 } else {
3.147 gw.next(e.in);
3.148 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
3.149 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
3.150 while (gw.valid(e.v) && !gw.valid(e.in)) {
3.151 gw.next(e.v);
3.152 if (gw.valid(e.v)) gw.first(e.in, e.v);
3.153 - while (gw.valid(e.in) && !(free(e.in)>0) ) { gw.next(e.in); }
3.154 + while (gw.valid(e.in) && !(resCap(e.in)>0) ) { gw.next(e.in); }
3.155 }
3.156 }
3.157 return e;
3.158 @@ -1193,18 +1193,18 @@
3.159 flow->set(e.in, flow->get(e.in)-a);
3.160 }
3.161
3.162 - Number free(const Edge& e) const {
3.163 + Number resCap(const Edge& e) const {
3.164 if (e.out_or_in)
3.165 return (capacity->get(e.out)-flow->get(e.out));
3.166 else
3.167 return (flow->get(e.in));
3.168 }
3.169
3.170 - Number free(OldOutEdgeIt out) const {
3.171 + Number resCap(OldOutEdgeIt out) const {
3.172 return (capacity->get(out)-flow->get(out));
3.173 }
3.174
3.175 - Number free(OldInEdgeIt in) const {
3.176 + Number resCap(OldInEdgeIt in) const {
3.177 return (flow->get(in));
3.178 }
3.179
3.180 @@ -1247,6 +1247,59 @@
3.181 };
3.182 };
3.183
3.184 + //Subgraph on the same node-set and partial edge-set
3.185 + template<typename GraphWrapper, typename FirstOutEdgesMap>
3.186 + class ErasingFirstGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
3.187 + protected:
3.188 + FirstOutEdgesMap* first_out_edges;
3.189 + public:
3.190 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
3.191 + typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
3.192 + typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge Edge;
3.193 + typedef typename GraphWrapperSkeleton<GraphWrapper>::EdgeIt EdgeIt;
3.194 + typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt InEdgeIt;
3.195 + typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt OutEdgeIt;
3.196 +
3.197 + ErasingFirstGraphWrapper(GraphWrapper _gw, FirstOutEdgesMap& _first_out_edges) :
3.198 + GraphWrapperSkeleton<GraphWrapper>(_gw), first_out_edges(&_first_out_edges) { }
3.199 +
3.200 + template<typename I> I& first(I& i) const {
3.201 + gw.first(i);
3.202 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
3.203 + return i;
3.204 + }
3.205 + OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.206 + e=first_out_edges->get(n);
3.207 + return e;
3.208 + }
3.209 + template<typename I, typename P> I& first(I& i, const P& p) const {
3.210 + gw.first(i, p);
3.211 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
3.212 + return i;
3.213 + }
3.214 +
3.215 + //template<typename I> I getNext(const I& i) const {
3.216 + // return gw.getNext(i);
3.217 + //}
3.218 + template<typename I> I& next(I &i) const {
3.219 + gw.next(i);
3.220 + //while (gw.valid(i) && !filter_map->get(i)) { gw.next(i); }
3.221 + return i;
3.222 + }
3.223 +
3.224 + template< typename It > It first() const {
3.225 + It e; this->first(e); return e; }
3.226 +
3.227 + template< typename It > It first(const Node& v) const {
3.228 + It e; this->first(e, v); return e; }
3.229 +
3.230 + void erase(const OutEdgeIt& e) const {
3.231 + OutEdgeIt f=e;
3.232 + this->next(f);
3.233 + first_out_edges->set(this->tail(e), f);
3.234 + }
3.235 + };
3.236 +
3.237 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.238 // class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
3.239 // protected: