2 #ifndef HUGO_EDMONDS_KARP_H
3 #define HUGO_EDMONDS_KARP_H
9 #include <bfs_iterator.h>
14 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
17 typedef typename Graph::Node Node;
18 typedef typename Graph::NodeIt NodeIt;
20 typedef typename Graph::SymEdgeIt OldSymEdgeIt;
23 const CapacityMap& capacity;
25 ResGraph(const Graph& _G, FlowMap& _flow,
26 const CapacityMap& _capacity) :
27 G(_G), flow(_flow), capacity(_capacity) { }
32 friend class OutEdgeIt;
35 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
37 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
41 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
43 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
44 return (resG->capacity.get(sym)-resG->flow.get(sym));
46 return (resG->flow.get(sym));
49 bool valid() const { return sym.valid(); }
50 void augment(Number a) const {
51 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
52 resG->flow.set(sym, resG->flow.get(sym)+a);
55 resG->flow.set(sym, resG->flow.get(sym)-a);
61 class OutEdgeIt : public Edge {
62 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
65 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
67 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
69 sym=resG->G.template first<OldSymEdgeIt>(v);
70 while( sym.valid() && !(free()>0) ) { ++sym; }
73 OutEdgeIt& operator++() {
75 while( sym.valid() && !(free()>0) ) { ++sym; }
80 void /*getF*/first(OutEdgeIt& e, Node v) const {
81 e=OutEdgeIt(*this, v);
83 void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
85 template< typename It >
92 template< typename It >
93 It first(Node v) const {
99 Node tail(Edge e) const { return G.aNode(e.sym); }
100 Node head(Edge e) const { return G.bNode(e.sym); }
102 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
103 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
105 int id(Node v) const { return G.id(v); }
107 template <typename S>
109 typename Graph::NodeMap<S> node_map;
111 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
112 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
113 void set(Node nit, S a) { node_map.set(nit, a); }
114 S get(Node nit) const { return node_map.get(nit); }
115 S& operator[](Node nit) { return node_map[nit]; }
116 const S& operator[](Node nit) const { return node_map[nit]; }
122 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
125 typedef typename Graph::Node Node;
126 typedef typename Graph::NodeIt NodeIt;
128 //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
129 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
130 typedef typename Graph::InEdgeIt OldInEdgeIt;
134 const CapacityMap& capacity;
136 ResGraph2(const Graph& _G, FlowMap& _flow,
137 const CapacityMap& _capacity) :
138 G(_G), flow(_flow), capacity(_capacity) { }
143 friend class OutEdgeIt;
146 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
148 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
152 bool out_or_in; //true, iff out
154 Edge() : out_or_in(true) { }
155 Number free() const {
157 return (resG->capacity.get(out)-resG->flow.get(out));
159 return (resG->flow.get(in));
163 return out_or_in && out.valid() || in.valid(); }
164 void augment(Number a) const {
166 resG->flow.set(out, resG->flow.get(out)+a);
168 resG->flow.set(in, resG->flow.get(in)-a);
173 class OutEdgeIt : public Edge {
174 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
178 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
180 out=resG->G.template first<OldOutEdgeIt>(v);
181 while( out.valid() && !(free()>0) ) { ++out; }
184 in=resG->G.template first<OldInEdgeIt>(v);
185 while( in.valid() && !(free()>0) ) { ++in; }
189 OutEdgeIt& operator++() {
191 Node v=resG->G.aNode(out);
193 while( out.valid() && !(free()>0) ) { ++out; }
196 in=resG->G.template first<OldInEdgeIt>(v);
197 while( in.valid() && !(free()>0) ) { ++in; }
201 while( in.valid() && !(free()>0) ) { ++in; }
207 void /*getF*/first(OutEdgeIt& e, Node v) const {
208 e=OutEdgeIt(*this, v);
210 void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
212 template< typename It >
219 template< typename It >
220 It first(Node v) const {
226 Node tail(Edge e) const {
227 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
228 Node head(Edge e) const {
229 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
231 Node aNode(OutEdgeIt e) const {
232 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
233 Node bNode(OutEdgeIt e) const {
234 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
236 int id(Node v) const { return G.id(v); }
238 template <typename S>
240 typename Graph::NodeMap<S> node_map;
242 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
243 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
244 void set(Node nit, S a) { node_map.set(nit, a); }
245 S get(Node nit) const { return node_map.get(nit); }
250 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
253 typedef typename GraphWrapper::Node Node;
254 typedef typename GraphWrapper::Edge Edge;
255 typedef typename GraphWrapper::EdgeIt EdgeIt;
256 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
257 typedef typename GraphWrapper::InEdgeIt InEdgeIt;
265 const CapacityMap* capacity;
266 typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap >
268 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
269 typedef typename AugGraph::Edge AugEdge;
272 MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
273 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
274 bool augmentOnShortestPath() {
275 AugGraph res_graph(gw, *flow, *capacity);
278 typedef typename AugGraph::NodeMap<bool> ReachedMap;
279 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
280 res_bfs.pushAndSetReached(s);
282 typename AugGraph::NodeMap<AugEdge> pred(res_graph);
283 pred.set(s, AugEdge(INVALID));
285 typename AugGraph::NodeMap<Number> free(res_graph);
287 //searching for augmenting path
288 while ( !res_bfs.finished() ) {
289 AugOutEdgeIt e=res_bfs;
290 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
291 Node v=res_graph.tail(e);
292 Node w=res_graph.head(e);
294 if (res_graph.valid(pred.get(v))) {
295 free.set(w, std::min(free.get(v), res_graph.free(e)));
297 free.set(w, res_graph.free(e));
299 if (res_graph.head(e)==t) { _augment=true; break; }
303 } //end of searching augmenting path
307 Number augment_value=free.get(t);
308 while (res_graph.valid(pred.get(n))) {
309 AugEdge e=pred.get(n);
310 res_graph.augment(e, augment_value);
318 template<typename MapGraphWrapper>
322 typename MapGraphWrapper::NodeMap<int> dist;
324 DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
325 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
326 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
327 bool get(const typename MapGraphWrapper::Edge& e) const {
328 return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
332 template<typename MutableGraph> bool augmentOnBlockingFlow() {
335 AugGraph res_graph(gw, *flow, *capacity);
337 typedef typename AugGraph::NodeMap<bool> ReachedMap;
338 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
340 bfs.pushAndSetReached(s);
341 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
342 DistanceMap<AugGraph> dist(res_graph);
343 while ( !bfs.finished() ) {
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
346 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
349 } //computing distances from s in the residual graph
352 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
353 FilterResGraph filter_res_graph(res_graph, dist);
354 typename AugGraph::NodeMap<typename MutableGraph::Node>
355 res_graph_to_F(res_graph);
356 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
357 res_graph_to_F.set(n, F.addNode());
360 typename MutableGraph::Node sF=res_graph_to_F.get(s);
361 typename MutableGraph::Node tF=res_graph_to_F.get(t);
363 typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
364 typename MutableGraph::EdgeMap<Number> residual_capacity(F);
366 //Making F to the graph containing the edges of the residual graph
367 //which are in some shortest paths
368 for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) {
369 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
370 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
371 original_edge.update();
372 original_edge.set(f, e);
373 residual_capacity.update();
374 residual_capacity.set(f, res_graph.free(e));
382 //computing blocking flow with dfs
383 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
384 DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
385 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
386 pred.set(sF, typename MutableGraph::Edge(INVALID));
387 //invalid iterators for sources
389 typename MutableGraph::NodeMap<Number> free(F);
391 dfs.pushAndSetReached(sF);
392 while (!dfs.finished()) {
394 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
395 if (dfs.isBNodeNewlyReached()) {
396 typename MutableGraph::Node v=F.aNode(dfs);
397 typename MutableGraph::Node w=F.bNode(dfs);
399 if (F.valid(pred.get(v))) {
400 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
402 free.set(w, residual_capacity.get(dfs));
411 F.erase(typename MutableGraph::OutEdgeIt(dfs));
417 typename MutableGraph::Node n=tF;
418 Number augment_value=free.get(tF);
419 while (F.valid(pred.get(n))) {
420 typename MutableGraph::Edge e=pred.get(n);
421 res_graph.augment(original_edge.get(e), augment_value);
423 if (residual_capacity.get(e)==augment_value)
426 residual_capacity.set(e, residual_capacity.get(e)-augment_value);
435 template<typename MutableGraph> bool augmentOnBlockingFlow1() {
438 AugGraph res_graph(gw, *flow, *capacity);
440 //bfs for distances on the residual graph
441 typedef typename AugGraph::NodeMap<bool> ReachedMap;
442 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
443 bfs.pushAndSetReached(s);
444 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
446 //F will contain the physical copy of the residual graph
447 //with the set of edges which areon shortest paths
449 typename AugGraph::NodeMap<typename MutableGraph::Node>
450 res_graph_to_F(res_graph);
451 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
452 res_graph_to_F.set(n, F.addNode());
454 typename MutableGraph::Node sF=res_graph_to_F.get(s);
455 typename MutableGraph::Node tF=res_graph_to_F.get(t);
456 typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
457 typename MutableGraph::EdgeMap<Number> residual_capacity(F);
459 while ( !bfs.finished() ) {
461 if (res_graph.valid(e)) {
462 if (bfs.isBNodeNewlyReached()) {
463 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
464 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
465 original_edge.update();
466 original_edge.set(f, e);
467 residual_capacity.update();
468 residual_capacity.set(f, res_graph.free(e));
470 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
471 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
472 original_edge.update();
473 original_edge.set(f, e);
474 residual_capacity.update();
475 residual_capacity.set(f, res_graph.free(e));
480 } //computing distances from s in the residual graph
486 //computing blocking flow with dfs
487 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
488 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
489 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
490 pred.set(sF, typename MutableGraph::Edge(INVALID));
491 //invalid iterators for sources
493 typename MutableGraph::NodeMap<Number> free(F);
495 dfs.pushAndSetReached(sF);
496 while (!dfs.finished()) {
498 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
499 if (dfs.isBNodeNewlyReached()) {
500 typename MutableGraph::Node v=F.aNode(dfs);
501 typename MutableGraph::Node w=F.bNode(dfs);
503 if (F.valid(pred.get(v))) {
504 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
506 free.set(w, residual_capacity.get(dfs));
515 F.erase(typename MutableGraph::OutEdgeIt(dfs));
521 typename MutableGraph::Node n=tF;
522 Number augment_value=free.get(tF);
523 while (F.valid(pred.get(n))) {
524 typename MutableGraph::Edge e=pred.get(n);
525 res_graph.augment(original_edge.get(e), augment_value);
527 if (residual_capacity.get(e)==augment_value)
530 residual_capacity.set(e, residual_capacity.get(e)-augment_value);
539 // bool augmentOnBlockingFlow2() {
540 // bool _augment=false;
542 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
543 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
544 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
545 // typedef typename EAugGraph::Edge EAugEdge;
547 // EAugGraph res_graph(*G, *flow, *capacity);
549 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
551 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
552 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
553 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
555 // bfs.pushAndSetReached(s);
557 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
558 // NodeMap<int>& dist=res_graph.dist;
560 // while ( !bfs.finished() ) {
561 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
562 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
563 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
566 // } //computing distances from s in the residual graph
568 // bool __augment=true;
570 // while (__augment) {
573 // //computing blocking flow with dfs
574 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
575 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
577 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
578 // pred.set(s, EAugEdge(INVALID));
579 // //invalid iterators for sources
581 // typename EAugGraph::NodeMap<Number> free(res_graph);
583 // dfs.pushAndSetReached(s);
584 // while (!dfs.finished()) {
586 // if (res_graph.valid(EAugOutEdgeIt(dfs))) {
587 // if (dfs.isBNodeNewlyReached()) {
589 // typename EAugGraph::Node v=res_graph.aNode(dfs);
590 // typename EAugGraph::Node w=res_graph.bNode(dfs);
592 // pred.set(w, EAugOutEdgeIt(dfs));
593 // if (res_graph.valid(pred.get(v))) {
594 // free.set(w, std::min(free.get(v), res_graph.free(dfs)));
596 // free.set(w, res_graph.free(dfs));
605 // res_graph.erase(dfs);
612 // typename EAugGraph::Node n=t;
613 // Number augment_value=free.get(t);
614 // while (res_graph.valid(pred.get(n))) {
615 // EAugEdge e=pred.get(n);
616 // res_graph.augment(e, augment_value);
617 // n=res_graph.tail(e);
618 // if (res_graph.free(e)==0)
619 // res_graph.erase(e);
628 // //int num_of_augmentations=0;
629 // while (augmentOnShortestPath()) {
630 // //while (augmentOnBlockingFlow<MutableGraph>()) {
631 // //std::cout << ++num_of_augmentations << " ";
632 // //std::cout<<std::endl;
635 // template<typename MutableGraph> void run() {
636 // //int num_of_augmentations=0;
637 // //while (augmentOnShortestPath()) {
638 // while (augmentOnBlockingFlow<MutableGraph>()) {
639 // //std::cout << ++num_of_augmentations << " ";
640 // //std::cout<<std::endl;
646 for(gw.first(e, s); gw.valid(e); gw.next(e)) {
654 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
655 // class MaxMatching {
657 // typedef typename Graph::Node Node;
658 // typedef typename Graph::NodeIt NodeIt;
659 // typedef typename Graph::Edge Edge;
660 // typedef typename Graph::EdgeIt EdgeIt;
661 // typedef typename Graph::OutEdgeIt OutEdgeIt;
662 // typedef typename Graph::InEdgeIt InEdgeIt;
664 // typedef typename Graph::NodeMap<bool> SMap;
665 // typedef typename Graph::NodeMap<bool> TMap;
673 // const CapacityMap* capacity;
674 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
675 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
676 // typedef typename AugGraph::Edge AugEdge;
677 // typename Graph::NodeMap<int> used; //0
680 // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
681 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
682 // bool augmentOnShortestPath() {
683 // AugGraph res_graph(*G, *flow, *capacity);
684 // bool _augment=false;
686 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
687 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
688 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
689 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
690 // if ((S->get(s)) && (used.get(s)<1) ) {
692 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
693 // //u+=flow->get(e);
695 // res_bfs.pushAndSetReached(s);
696 // pred.set(s, AugEdge(INVALID));
701 // typename AugGraph::NodeMap<Number> free(res_graph);
704 // //searching for augmenting path
705 // while ( !res_bfs.finished() ) {
706 // AugOutEdgeIt e=res_bfs;
707 // if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
708 // Node v=res_graph.tail(e);
709 // Node w=res_graph.head(e);
711 // if (res_graph.valid(pred.get(v))) {
712 // free.set(w, std::min(free.get(v), res_graph.free(e)));
714 // free.set(w, res_graph.free(e));
716 // n=res_graph.head(e);
717 // if (T->get(n) && (used.get(n)<1) ) {
719 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
720 // //u+=flow->get(f);
729 // } //end of searching augmenting path
733 // used.set(n, 1); //mind2 vegen jav
734 // Number augment_value=free.get(n);
735 // while (res_graph.valid(pred.get(n))) {
736 // AugEdge e=pred.get(n);
737 // res_graph.augment(e, augment_value);
738 // n=res_graph.tail(e);
740 // used.set(n, 1); //mind2 vegen jav
746 // // template<typename MutableGraph> bool augmentOnBlockingFlow() {
747 // // bool _augment=false;
749 // // AugGraph res_graph(*G, *flow, *capacity);
751 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
752 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
758 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
759 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
760 // // if (S->get(s)) {
762 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
763 // // u+=flow->get(e);
765 // // res_bfs.pushAndSetReached(s);
766 // // //pred.set(s, AugEdge(INVALID));
774 // // //bfs.pushAndSetReached(s);
775 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
776 // // while ( !bfs.finished() ) {
777 // // AugOutEdgeIt e=bfs;
778 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
779 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
783 // // } //computing distances from s in the residual graph
785 // // MutableGraph F;
786 // // typename AugGraph::NodeMap<typename MutableGraph::Node>
787 // // res_graph_to_F(res_graph);
788 // // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
789 // // res_graph_to_F.set(n, F.addNode());
792 // // typename MutableGraph::Node sF=res_graph_to_F.get(s);
793 // // typename MutableGraph::Node tF=res_graph_to_F.get(t);
795 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
796 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
798 // // //Making F to the graph containing the edges of the residual graph
799 // // //which are in some shortest paths
800 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
801 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
802 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
803 // // original_edge.update();
804 // // original_edge.set(f, e);
805 // // residual_capacity.update();
806 // // residual_capacity.set(f, res_graph.free(e));
810 // // bool __augment=true;
812 // // while (__augment) {
813 // // __augment=false;
814 // // //computing blocking flow with dfs
815 // // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
816 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
817 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
818 // // pred.set(sF, typename MutableGraph::Edge(INVALID));
819 // // //invalid iterators for sources
821 // // typename MutableGraph::NodeMap<Number> free(F);
823 // // dfs.pushAndSetReached(sF);
824 // // while (!dfs.finished()) {
826 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
827 // // if (dfs.isBNodeNewlyReached()) {
828 // // typename MutableGraph::Node v=F.aNode(dfs);
829 // // typename MutableGraph::Node w=F.bNode(dfs);
830 // // pred.set(w, dfs);
831 // // if (F.valid(pred.get(v))) {
832 // // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
834 // // free.set(w, residual_capacity.get(dfs));
837 // // __augment=true;
843 // // F.erase(typename MutableGraph::OutEdgeIt(dfs));
848 // // if (__augment) {
849 // // typename MutableGraph::Node n=tF;
850 // // Number augment_value=free.get(tF);
851 // // while (F.valid(pred.get(n))) {
852 // // typename MutableGraph::Edge e=pred.get(n);
853 // // res_graph.augment(original_edge.get(e), augment_value);
855 // // if (residual_capacity.get(e)==augment_value)
858 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
864 // // return _augment;
866 // bool augmentOnBlockingFlow2() {
867 // bool _augment=false;
869 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
870 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
871 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
872 // typedef typename EAugGraph::Edge EAugEdge;
874 // EAugGraph res_graph(*G, *flow, *capacity);
876 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
878 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
879 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
880 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
883 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
884 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
887 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
890 // bfs.pushAndSetReached(s);
891 // //pred.set(s, AugEdge(INVALID));
897 // //bfs.pushAndSetReached(s);
899 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
900 // NodeMap<int>& dist=res_graph.dist;
902 // while ( !bfs.finished() ) {
903 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
904 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
905 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
908 // } //computing distances from s in the residual graph
910 // bool __augment=true;
912 // while (__augment) {
915 // //computing blocking flow with dfs
916 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
917 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
919 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
920 // //pred.set(s, EAugEdge(INVALID));
921 // //invalid iterators for sources
923 // typename EAugGraph::NodeMap<Number> free(res_graph);
926 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
927 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
930 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
933 // dfs.pushAndSetReached(s);
934 // //pred.set(s, AugEdge(INVALID));
941 // //dfs.pushAndSetReached(s);
942 // typename EAugGraph::Node n;
943 // while (!dfs.finished()) {
945 // if (res_graph.valid(EAugOutEdgeIt(dfs))) {
946 // if (dfs.isBNodeNewlyReached()) {
948 // typename EAugGraph::Node v=res_graph.aNode(dfs);
949 // typename EAugGraph::Node w=res_graph.bNode(dfs);
951 // pred.set(w, EAugOutEdgeIt(dfs));
952 // if (res_graph.valid(pred.get(v))) {
953 // free.set(w, std::min(free.get(v), res_graph.free(dfs)));
955 // free.set(w, res_graph.free(dfs));
961 // for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
970 // res_graph.erase(dfs);
977 // // typename EAugGraph::Node n=t;
978 // Number augment_value=free.get(n);
979 // while (res_graph.valid(pred.get(n))) {
980 // EAugEdge e=pred.get(n);
981 // res_graph.augment(e, augment_value);
982 // n=res_graph.tail(e);
983 // if (res_graph.free(e)==0)
984 // res_graph.erase(e);
993 // //int num_of_augmentations=0;
994 // while (augmentOnShortestPath()) {
995 // //while (augmentOnBlockingFlow<MutableGraph>()) {
996 // //std::cout << ++num_of_augmentations << " ";
997 // //std::cout<<std::endl;
1000 // // template<typename MutableGraph> void run() {
1001 // // //int num_of_augmentations=0;
1002 // // //while (augmentOnShortestPath()) {
1003 // // while (augmentOnBlockingFlow<MutableGraph>()) {
1004 // // //std::cout << ++num_of_augmentations << " ";
1005 // // //std::cout<<std::endl;
1008 // Number flowValue() {
1011 // for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1023 // // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1024 // // class MaxFlow2 {
1026 // // typedef typename Graph::Node Node;
1027 // // typedef typename Graph::Edge Edge;
1028 // // typedef typename Graph::EdgeIt EdgeIt;
1029 // // typedef typename Graph::OutEdgeIt OutEdgeIt;
1030 // // typedef typename Graph::InEdgeIt InEdgeIt;
1032 // // const Graph& G;
1033 // // std::list<Node>& S;
1034 // // std::list<Node>& T;
1035 // // FlowMap& flow;
1036 // // const CapacityMap& capacity;
1037 // // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1038 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1039 // // typedef typename AugGraph::Edge AugEdge;
1040 // // typename Graph::NodeMap<bool> SMap;
1041 // // typename Graph::NodeMap<bool> TMap;
1043 // // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1044 // // for(typename std::list<Node>::const_iterator i=S.begin();
1045 // // i!=S.end(); ++i) {
1046 // // SMap.set(*i, true);
1048 // // for (typename std::list<Node>::const_iterator i=T.begin();
1049 // // i!=T.end(); ++i) {
1050 // // TMap.set(*i, true);
1053 // // bool augment() {
1054 // // AugGraph res_graph(G, flow, capacity);
1055 // // bool _augment=false;
1056 // // Node reached_t_node;
1058 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1059 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1060 // // for(typename std::list<Node>::const_iterator i=S.begin();
1061 // // i!=S.end(); ++i) {
1062 // // res_bfs.pushAndSetReached(*i);
1064 // // //res_bfs.pushAndSetReached(s);
1066 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1067 // // //filled up with invalid iterators
1069 // // typename AugGraph::NodeMap<Number> free(res_graph);
1071 // // //searching for augmenting path
1072 // // while ( !res_bfs.finished() ) {
1073 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1074 // // if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1075 // // Node v=res_graph.tail(e);
1076 // // Node w=res_graph.head(e);
1077 // // pred.set(w, e);
1078 // // if (pred.get(v).valid()) {
1079 // // free.set(w, std::min(free.get(v), e.free()));
1081 // // free.set(w, e.free());
1083 // // if (TMap.get(res_graph.head(e))) {
1084 // // _augment=true;
1085 // // reached_t_node=res_graph.head(e);
1091 // // } //end of searching augmenting path
1093 // // if (_augment) {
1094 // // Node n=reached_t_node;
1095 // // Number augment_value=free.get(reached_t_node);
1096 // // while (pred.get(n).valid()) {
1097 // // AugEdge e=pred.get(n);
1098 // // e.augment(augment_value);
1099 // // n=res_graph.tail(e);
1103 // // return _augment;
1106 // // while (augment()) { }
1108 // // Number flowValue() {
1110 // // for(typename std::list<Node>::const_iterator i=S.begin();
1111 // // i!=S.end(); ++i) {
1112 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1113 // // a+=flow.get(e);
1115 // // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1116 // // a-=flow.get(e);
1126 #endif //HUGO_EDMONDS_KARP_H