.
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 Graph, typename Number, typename FlowMap, typename CapacityMap>
253 typedef typename Graph::Node Node;
254 typedef typename Graph::Edge Edge;
255 typedef typename Graph::EdgeIt EdgeIt;
256 typedef typename Graph::OutEdgeIt OutEdgeIt;
257 typedef typename Graph::InEdgeIt InEdgeIt;
264 const CapacityMap* capacity;
265 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
266 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
267 typedef typename AugGraph::Edge AugEdge;
270 MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
271 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
272 bool augmentOnShortestPath() {
273 AugGraph res_graph(*G, *flow, *capacity);
276 typedef typename AugGraph::NodeMap<bool> ReachedMap;
277 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
278 res_bfs.pushAndSetReached(s);
280 typename AugGraph::NodeMap<AugEdge> pred(res_graph);
281 pred.set(s, AugEdge(INVALID));
283 typename AugGraph::NodeMap<Number> free(res_graph);
285 //searching for augmenting path
286 while ( !res_bfs.finished() ) {
287 AugOutEdgeIt e=res_bfs;
288 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
289 Node v=res_graph.tail(e);
290 Node w=res_graph.head(e);
292 if (res_graph.valid(pred.get(v))) {
293 free.set(w, std::min(free.get(v), res_graph.free(e)));
295 free.set(w, res_graph.free(e));
297 if (res_graph.head(e)==t) { _augment=true; break; }
301 } //end of searching augmenting path
305 Number augment_value=free.get(t);
306 while (res_graph.valid(pred.get(n))) {
307 AugEdge e=pred.get(n);
308 res_graph.augment(e, augment_value);
316 template<typename MutableGraph> bool augmentOnBlockingFlow() {
319 AugGraph res_graph(*G, *flow, *capacity);
321 typedef typename AugGraph::NodeMap<bool> ReachedMap;
322 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
324 bfs.pushAndSetReached(s);
325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
326 while ( !bfs.finished() ) {
328 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
329 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
333 } //computing distances from s in the residual graph
336 typename AugGraph::NodeMap<typename MutableGraph::Node>
337 res_graph_to_F(res_graph);
338 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
339 res_graph_to_F.set(n, F.addNode());
342 typename MutableGraph::Node sF=res_graph_to_F.get(s);
343 typename MutableGraph::Node tF=res_graph_to_F.get(t);
345 typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
346 typename MutableGraph::EdgeMap<Number> residual_capacity(F);
348 //Making F to the graph containing the edges of the residual graph
349 //which are in some shortest paths
350 for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
351 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
352 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
353 original_edge.update();
354 original_edge.set(f, e);
355 residual_capacity.update();
356 residual_capacity.set(f, res_graph.free(e));
364 //computing blocking flow with dfs
365 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
366 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
368 pred.set(sF, typename MutableGraph::Edge(INVALID));
369 //invalid iterators for sources
371 typename MutableGraph::NodeMap<Number> free(F);
373 dfs.pushAndSetReached(sF);
374 while (!dfs.finished()) {
376 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
377 if (dfs.isBNodeNewlyReached()) {
378 typename MutableGraph::Node v=F.aNode(dfs);
379 typename MutableGraph::Node w=F.bNode(dfs);
381 if (F.valid(pred.get(v))) {
382 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
384 free.set(w, residual_capacity.get(dfs));
393 F.erase(typename MutableGraph::OutEdgeIt(dfs));
399 typename MutableGraph::Node n=tF;
400 Number augment_value=free.get(tF);
401 while (F.valid(pred.get(n))) {
402 typename MutableGraph::Edge e=pred.get(n);
403 res_graph.augment(original_edge.get(e), augment_value);
405 if (residual_capacity.get(e)==augment_value)
408 residual_capacity.set(e, residual_capacity.get(e)-augment_value);
416 bool augmentOnBlockingFlow2() {
419 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
420 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
421 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
422 typedef typename EAugGraph::Edge EAugEdge;
424 EAugGraph res_graph(*G, *flow, *capacity);
426 //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
428 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
429 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
430 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
432 bfs.pushAndSetReached(s);
434 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
435 NodeMap<int>& dist=res_graph.dist;
437 while ( !bfs.finished() ) {
438 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
439 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
440 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
443 } //computing distances from s in the residual graph
450 //computing blocking flow with dfs
451 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
452 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
454 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
455 pred.set(s, EAugEdge(INVALID));
456 //invalid iterators for sources
458 typename EAugGraph::NodeMap<Number> free(res_graph);
460 dfs.pushAndSetReached(s);
461 while (!dfs.finished()) {
463 if (res_graph.valid(EAugOutEdgeIt(dfs))) {
464 if (dfs.isBNodeNewlyReached()) {
466 typename EAugGraph::Node v=res_graph.aNode(dfs);
467 typename EAugGraph::Node w=res_graph.bNode(dfs);
469 pred.set(w, EAugOutEdgeIt(dfs));
470 if (res_graph.valid(pred.get(v))) {
471 free.set(w, std::min(free.get(v), res_graph.free(dfs)));
473 free.set(w, res_graph.free(dfs));
482 res_graph.erase(dfs);
489 typename EAugGraph::Node n=t;
490 Number augment_value=free.get(t);
491 while (res_graph.valid(pred.get(n))) {
492 EAugEdge e=pred.get(n);
493 res_graph.augment(e, augment_value);
495 if (res_graph.free(e)==0)
505 //int num_of_augmentations=0;
506 while (augmentOnShortestPath()) {
507 //while (augmentOnBlockingFlow<MutableGraph>()) {
508 //std::cout << ++num_of_augmentations << " ";
509 //std::cout<<std::endl;
512 template<typename MutableGraph> void run() {
513 //int num_of_augmentations=0;
514 //while (augmentOnShortestPath()) {
515 while (augmentOnBlockingFlow<MutableGraph>()) {
516 //std::cout << ++num_of_augmentations << " ";
517 //std::cout<<std::endl;
523 for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
531 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
534 typedef typename Graph::Node Node;
535 typedef typename Graph::NodeIt NodeIt;
536 typedef typename Graph::Edge Edge;
537 typedef typename Graph::EdgeIt EdgeIt;
538 typedef typename Graph::OutEdgeIt OutEdgeIt;
539 typedef typename Graph::InEdgeIt InEdgeIt;
541 typedef typename Graph::NodeMap<bool> SMap;
542 typedef typename Graph::NodeMap<bool> TMap;
550 const CapacityMap* capacity;
551 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
552 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
553 typedef typename AugGraph::Edge AugEdge;
556 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
557 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
558 bool augmentOnShortestPath() {
559 AugGraph res_graph(*G, *flow, *capacity);
562 typedef typename AugGraph::NodeMap<bool> ReachedMap;
563 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
564 typename AugGraph::NodeMap<AugEdge> pred(res_graph);
565 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
568 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
571 res_bfs.pushAndSetReached(s);
572 pred.set(s, AugEdge(INVALID));
577 typename AugGraph::NodeMap<Number> free(res_graph);
580 //searching for augmenting path
581 while ( !res_bfs.finished() ) {
582 AugOutEdgeIt e=res_bfs;
583 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
584 Node v=res_graph.tail(e);
585 Node w=res_graph.head(e);
587 if (res_graph.valid(pred.get(v))) {
588 free.set(w, std::min(free.get(v), res_graph.free(e)));
590 free.set(w, res_graph.free(e));
595 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
605 } //end of searching augmenting path
609 Number augment_value=free.get(n);
610 while (res_graph.valid(pred.get(n))) {
611 AugEdge e=pred.get(n);
612 res_graph.augment(e, augment_value);
620 // template<typename MutableGraph> bool augmentOnBlockingFlow() {
621 // bool _augment=false;
623 // AugGraph res_graph(*G, *flow, *capacity);
625 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
626 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
632 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
633 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
636 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
639 // res_bfs.pushAndSetReached(s);
640 // //pred.set(s, AugEdge(INVALID));
648 // //bfs.pushAndSetReached(s);
649 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
650 // while ( !bfs.finished() ) {
651 // AugOutEdgeIt e=bfs;
652 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
653 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
657 // } //computing distances from s in the residual graph
660 // typename AugGraph::NodeMap<typename MutableGraph::Node>
661 // res_graph_to_F(res_graph);
662 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
663 // res_graph_to_F.set(n, F.addNode());
666 // typename MutableGraph::Node sF=res_graph_to_F.get(s);
667 // typename MutableGraph::Node tF=res_graph_to_F.get(t);
669 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
670 // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
672 // //Making F to the graph containing the edges of the residual graph
673 // //which are in some shortest paths
674 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
675 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
676 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
677 // original_edge.update();
678 // original_edge.set(f, e);
679 // residual_capacity.update();
680 // residual_capacity.set(f, res_graph.free(e));
684 // bool __augment=true;
686 // while (__augment) {
688 // //computing blocking flow with dfs
689 // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
690 // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
691 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
692 // pred.set(sF, typename MutableGraph::Edge(INVALID));
693 // //invalid iterators for sources
695 // typename MutableGraph::NodeMap<Number> free(F);
697 // dfs.pushAndSetReached(sF);
698 // while (!dfs.finished()) {
700 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
701 // if (dfs.isBNodeNewlyReached()) {
702 // typename MutableGraph::Node v=F.aNode(dfs);
703 // typename MutableGraph::Node w=F.bNode(dfs);
705 // if (F.valid(pred.get(v))) {
706 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
708 // free.set(w, residual_capacity.get(dfs));
717 // F.erase(typename MutableGraph::OutEdgeIt(dfs));
723 // typename MutableGraph::Node n=tF;
724 // Number augment_value=free.get(tF);
725 // while (F.valid(pred.get(n))) {
726 // typename MutableGraph::Edge e=pred.get(n);
727 // res_graph.augment(original_edge.get(e), augment_value);
729 // if (residual_capacity.get(e)==augment_value)
732 // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
740 bool augmentOnBlockingFlow2() {
743 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
744 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
745 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
746 typedef typename EAugGraph::Edge EAugEdge;
748 EAugGraph res_graph(*G, *flow, *capacity);
750 //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
752 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
753 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
754 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
757 //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
758 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
761 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
764 bfs.pushAndSetReached(s);
765 //pred.set(s, AugEdge(INVALID));
771 //bfs.pushAndSetReached(s);
773 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
774 NodeMap<int>& dist=res_graph.dist;
776 while ( !bfs.finished() ) {
777 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
778 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
779 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
782 } //computing distances from s in the residual graph
789 //computing blocking flow with dfs
790 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
791 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
793 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
794 //pred.set(s, EAugEdge(INVALID));
795 //invalid iterators for sources
797 typename EAugGraph::NodeMap<Number> free(res_graph);
800 //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
801 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
804 for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
807 dfs.pushAndSetReached(s);
808 //pred.set(s, AugEdge(INVALID));
815 //dfs.pushAndSetReached(s);
816 typename EAugGraph::Node n;
817 while (!dfs.finished()) {
819 if (res_graph.valid(EAugOutEdgeIt(dfs))) {
820 if (dfs.isBNodeNewlyReached()) {
822 typename EAugGraph::Node v=res_graph.aNode(dfs);
823 typename EAugGraph::Node w=res_graph.bNode(dfs);
825 pred.set(w, EAugOutEdgeIt(dfs));
826 if (res_graph.valid(pred.get(v))) {
827 free.set(w, std::min(free.get(v), res_graph.free(dfs)));
829 free.set(w, res_graph.free(dfs));
835 for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
844 res_graph.erase(dfs);
851 // typename EAugGraph::Node n=t;
852 Number augment_value=free.get(n);
853 while (res_graph.valid(pred.get(n))) {
854 EAugEdge e=pred.get(n);
855 res_graph.augment(e, augment_value);
857 if (res_graph.free(e)==0)
867 //int num_of_augmentations=0;
868 while (augmentOnShortestPath()) {
869 //while (augmentOnBlockingFlow<MutableGraph>()) {
870 //std::cout << ++num_of_augmentations << " ";
871 //std::cout<<std::endl;
874 // template<typename MutableGraph> void run() {
875 // //int num_of_augmentations=0;
876 // //while (augmentOnShortestPath()) {
877 // while (augmentOnBlockingFlow<MutableGraph>()) {
878 // //std::cout << ++num_of_augmentations << " ";
879 // //std::cout<<std::endl;
885 for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
897 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
900 // typedef typename Graph::Node Node;
901 // typedef typename Graph::Edge Edge;
902 // typedef typename Graph::EdgeIt EdgeIt;
903 // typedef typename Graph::OutEdgeIt OutEdgeIt;
904 // typedef typename Graph::InEdgeIt InEdgeIt;
907 // std::list<Node>& S;
908 // std::list<Node>& T;
910 // const CapacityMap& capacity;
911 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
912 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
913 // typedef typename AugGraph::Edge AugEdge;
914 // typename Graph::NodeMap<bool> SMap;
915 // typename Graph::NodeMap<bool> TMap;
917 // 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) {
918 // for(typename std::list<Node>::const_iterator i=S.begin();
919 // i!=S.end(); ++i) {
920 // SMap.set(*i, true);
922 // for (typename std::list<Node>::const_iterator i=T.begin();
923 // i!=T.end(); ++i) {
924 // TMap.set(*i, true);
928 // AugGraph res_graph(G, flow, capacity);
929 // bool _augment=false;
930 // Node reached_t_node;
932 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
933 // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
934 // for(typename std::list<Node>::const_iterator i=S.begin();
935 // i!=S.end(); ++i) {
936 // res_bfs.pushAndSetReached(*i);
938 // //res_bfs.pushAndSetReached(s);
940 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
941 // //filled up with invalid iterators
943 // typename AugGraph::NodeMap<Number> free(res_graph);
945 // //searching for augmenting path
946 // while ( !res_bfs.finished() ) {
947 // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
948 // if (e.valid() && res_bfs.isBNodeNewlyReached()) {
949 // Node v=res_graph.tail(e);
950 // Node w=res_graph.head(e);
952 // if (pred.get(v).valid()) {
953 // free.set(w, std::min(free.get(v), e.free()));
955 // free.set(w, e.free());
957 // if (TMap.get(res_graph.head(e))) {
959 // reached_t_node=res_graph.head(e);
965 // } //end of searching augmenting path
968 // Node n=reached_t_node;
969 // Number augment_value=free.get(reached_t_node);
970 // while (pred.get(n).valid()) {
971 // AugEdge e=pred.get(n);
972 // e.augment(augment_value);
973 // n=res_graph.tail(e);
980 // while (augment()) { }
982 // Number flowValue() {
984 // for(typename std::list<Node>::const_iterator i=S.begin();
985 // i!=S.end(); ++i) {
986 // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
989 // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1001 #endif //EDMONDS_KARP_H