Naming conventions...
2 #ifndef HUGO_EDMONDS_KARP_H
3 #define HUGO_EDMONDS_KARP_H
9 #include <bfs_iterator.h>
11 #include <graph_wrapper.h>
16 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
19 typedef typename Graph::Node Node;
20 typedef typename Graph::NodeIt NodeIt;
22 typedef typename Graph::SymEdgeIt OldSymEdgeIt;
25 const CapacityMap& capacity;
27 ResGraph(const Graph& _G, FlowMap& _flow,
28 const CapacityMap& _capacity) :
29 G(_G), flow(_flow), capacity(_capacity) { }
34 friend class OutEdgeIt;
37 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
39 const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
43 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
45 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
46 return (resG->capacity.get(sym)-resG->flow.get(sym));
48 return (resG->flow.get(sym));
51 bool valid() const { return sym.valid(); }
52 void augment(Number a) const {
53 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
54 resG->flow.set(sym, resG->flow.get(sym)+a);
57 resG->flow.set(sym, resG->flow.get(sym)-a);
63 class OutEdgeIt : public Edge {
64 friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
67 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
69 OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
71 sym=resG->G.template first<OldSymEdgeIt>(v);
72 while( sym.valid() && !(free()>0) ) { ++sym; }
75 OutEdgeIt& operator++() {
77 while( sym.valid() && !(free()>0) ) { ++sym; }
82 void /*getF*/first(OutEdgeIt& e, Node v) const {
83 e=OutEdgeIt(*this, v);
85 void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
87 template< typename It >
94 template< typename It >
95 It first(Node v) const {
101 Node tail(Edge e) const { return G.aNode(e.sym); }
102 Node head(Edge e) const { return G.bNode(e.sym); }
104 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
105 Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
107 int id(Node v) const { return G.id(v); }
109 template <typename S>
111 typename Graph::NodeMap<S> node_map;
113 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
114 NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
115 void set(Node nit, S a) { node_map.set(nit, a); }
116 S get(Node nit) const { return node_map.get(nit); }
117 S& operator[](Node nit) { return node_map[nit]; }
118 const S& operator[](Node nit) const { return node_map[nit]; }
124 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
127 typedef typename Graph::Node Node;
128 typedef typename Graph::NodeIt NodeIt;
130 //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
131 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
132 typedef typename Graph::InEdgeIt OldInEdgeIt;
136 const CapacityMap& capacity;
138 ResGraph2(const Graph& _G, FlowMap& _flow,
139 const CapacityMap& _capacity) :
140 G(_G), flow(_flow), capacity(_capacity) { }
145 friend class OutEdgeIt;
148 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
150 const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
154 bool out_or_in; //true, iff out
156 Edge() : out_or_in(true) { }
157 Number free() const {
159 return (resG->capacity.get(out)-resG->flow.get(out));
161 return (resG->flow.get(in));
165 return out_or_in && out.valid() || in.valid(); }
166 void augment(Number a) const {
168 resG->flow.set(out, resG->flow.get(out)+a);
170 resG->flow.set(in, resG->flow.get(in)-a);
175 class OutEdgeIt : public Edge {
176 friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
180 OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
182 out=resG->G.template first<OldOutEdgeIt>(v);
183 while( out.valid() && !(free()>0) ) { ++out; }
186 in=resG->G.template first<OldInEdgeIt>(v);
187 while( in.valid() && !(free()>0) ) { ++in; }
191 OutEdgeIt& operator++() {
193 Node v=resG->G.aNode(out);
195 while( out.valid() && !(free()>0) ) { ++out; }
198 in=resG->G.template first<OldInEdgeIt>(v);
199 while( in.valid() && !(free()>0) ) { ++in; }
203 while( in.valid() && !(free()>0) ) { ++in; }
209 void /*getF*/first(OutEdgeIt& e, Node v) const {
210 e=OutEdgeIt(*this, v);
212 void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
214 template< typename It >
221 template< typename It >
222 It first(Node v) const {
228 Node tail(Edge e) const {
229 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
230 Node head(Edge e) const {
231 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
233 Node aNode(OutEdgeIt e) const {
234 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
235 Node bNode(OutEdgeIt e) const {
236 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
238 int id(Node v) const { return G.id(v); }
240 template <typename S>
242 typename Graph::NodeMap<S> node_map;
244 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
245 NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
246 void set(Node nit, S a) { node_map.set(nit, a); }
247 S get(Node nit) const { return node_map.get(nit); }
252 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
255 typedef typename Graph::Node Node;
256 typedef typename Graph::Edge Edge;
257 typedef typename Graph::EdgeIt EdgeIt;
258 typedef typename Graph::OutEdgeIt OutEdgeIt;
259 typedef typename Graph::InEdgeIt InEdgeIt;
264 const CapacityMap* capacity;
265 typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
266 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
267 typedef typename ResGW::Edge ResGWEdge;
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) { }
273 bool augmentOnShortestPath() {
274 ResGW res_graph(*g, *flow, *capacity);
277 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
278 bfs.pushAndSetReached(s);
280 typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
281 pred.set(s, INVALID);
283 typename ResGW::NodeMap<Number> free(res_graph);
285 //searching for augmenting path
286 while ( !bfs.finished() ) {
287 ResGWOutEdgeIt e=bfs;
288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
289 Node v=res_graph.tail(e);
290 Node w=res_graph.head(e);
292 if (res_graph.valid(pred[v])) {
293 free.set(w, std::min(free[v], res_graph.resCap(e)));
295 free.set(w, res_graph.resCap(e));
297 if (res_graph.head(e)==t) { _augment=true; break; }
301 } //end of searching augmenting path
305 Number augment_value=free[t];
306 while (res_graph.valid(pred[n])) {
308 res_graph.augment(e, augment_value);
316 template<typename MapGraphWrapper>
319 const MapGraphWrapper* g;
320 typename MapGraphWrapper::NodeMap<int> dist;
322 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
323 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
324 int operator[](const typename MapGraphWrapper::Node& n)
326 // int get(const typename MapGraphWrapper::Node& n) const {
328 // bool get(const typename MapGraphWrapper::Edge& e) const {
329 // return (dist.get(g->tail(e))<dist.get(g->head(e))); }
330 bool operator[](const typename MapGraphWrapper::Edge& e) const {
331 return (dist[g->tail(e)]<dist[g->head(e)]);
335 template<typename MutableGraph> bool augmentOnBlockingFlow() {
336 typedef MutableGraph MG;
339 ResGW res_graph(*g, *flow, *capacity);
341 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
343 bfs.pushAndSetReached(s);
344 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
345 DistanceMap<ResGW> dist(res_graph);
346 while ( !bfs.finished() ) {
347 ResGWOutEdgeIt e=bfs;
348 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
349 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
352 } //computing distances from s in the residual graph
355 ConstMap<typename ResGW::Node, bool> true_map(true);
356 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
357 DistanceMap<ResGW> > FilterResGW;
358 FilterResGW filter_res_graph(res_graph, true_map, dist);
359 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
361 typename ResGW::NodeIt n;
362 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
363 res_graph_to_F.set(n, F.addNode());
367 typename MG::Node sF=res_graph_to_F[s];
368 typename MG::Node tF=res_graph_to_F[t];
369 typename MG::EdgeMap<ResGWEdge> original_edge(F);
370 typename MG::EdgeMap<Number> residual_capacity(F);
372 //Making F to the graph containing the edges of the residual graph
373 //which are in some shortest paths
375 typename FilterResGW::EdgeIt e;
376 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
377 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
378 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
379 original_edge.update();
380 original_edge.set(f, e);
381 residual_capacity.update();
382 residual_capacity.set(f, res_graph.resCap(e));
391 //computing blocking flow with dfs
393 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);
394 typename MG::NodeMap<typename MG::Edge> pred(F);
395 pred.set(sF, INVALID);
396 //invalid iterators for sources
398 typename MG::NodeMap<Number> free(F);
400 dfs.pushAndSetReached(sF);
401 while (!dfs.finished()) {
403 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
404 if (dfs.isBNodeNewlyReached()) {
405 typename MG::Node v=F.aNode(dfs);
406 typename MG::Node w=F.bNode(dfs);
408 if (F.valid(pred[v])) {
409 free.set(w, std::min(free[v], residual_capacity[dfs]));
411 free.set(w, residual_capacity[dfs]);
420 F.erase(/*typename MG::OutEdgeIt*/(dfs));
426 typename MG::Node n=tF;
427 Number augment_value=free[tF];
428 while (F.valid(pred[n])) {
429 typename MG::Edge e=pred[n];
430 res_graph.augment(original_edge[e], augment_value);
432 if (residual_capacity[e]==augment_value)
435 residual_capacity.set(e, residual_capacity[e]-augment_value);
444 template<typename MutableGraph> bool augmentOnBlockingFlow1() {
445 typedef MutableGraph MG;
448 ResGW res_graph(*g, *flow, *capacity);
450 //bfs for distances on the residual graph
451 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
452 bfs.pushAndSetReached(s);
453 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
455 //F will contain the physical copy of the residual graph
456 //with the set of edges which are on shortest paths
458 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
460 typename ResGW::NodeIt n;
461 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
462 res_graph_to_F.set(n, F.addNode());
466 typename MG::Node sF=res_graph_to_F[s];
467 typename MG::Node tF=res_graph_to_F[t];
468 typename MG::EdgeMap<ResGWEdge> original_edge(F);
469 typename MG::EdgeMap<Number> residual_capacity(F);
471 while ( !bfs.finished() ) {
472 ResGWOutEdgeIt e=bfs;
473 if (res_graph.valid(e)) {
474 if (bfs.isBNodeNewlyReached()) {
475 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
476 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
477 original_edge.update();
478 original_edge.set(f, e);
479 residual_capacity.update();
480 residual_capacity.set(f, res_graph.resCap(e));
482 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
483 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
484 original_edge.update();
485 original_edge.set(f, e);
486 residual_capacity.update();
487 residual_capacity.set(f, res_graph.resCap(e));
492 } //computing distances from s in the residual graph
498 //computing blocking flow with dfs
499 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F);
500 typename MG::NodeMap<typename MG::Edge> pred(F);
501 pred.set(sF, INVALID);
502 //invalid iterators for sources
504 typename MG::NodeMap<Number> free(F);
506 dfs.pushAndSetReached(sF);
507 while (!dfs.finished()) {
509 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
510 if (dfs.isBNodeNewlyReached()) {
511 typename MG::Node v=F.aNode(dfs);
512 typename MG::Node w=F.bNode(dfs);
514 if (F.valid(pred[v])) {
515 free.set(w, std::min(free[v], residual_capacity[dfs]));
517 free.set(w, residual_capacity[dfs]);
526 F.erase(/*typename MG::OutEdgeIt*/(dfs));
532 typename MG::Node n=tF;
533 Number augment_value=free[tF];
534 while (F.valid(pred[n])) {
535 typename MG::Edge e=pred[n];
536 res_graph.augment(original_edge[e], augment_value);
538 if (residual_capacity[e]==augment_value)
541 residual_capacity.set(e, residual_capacity[e]-augment_value);
550 bool augmentOnBlockingFlow2() {
553 ResGW res_graph(*g, *flow, *capacity);
555 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph);
557 bfs.pushAndSetReached(s);
558 DistanceMap<ResGW> dist(res_graph);
559 while ( !bfs.finished() ) {
560 ResGWOutEdgeIt e=bfs;
561 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
562 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
565 } //computing distances from s in the residual graph
567 //Subgraph containing the edges on some shortest paths
568 ConstMap<typename ResGW::Node, bool> true_map(true);
569 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
570 DistanceMap<ResGW> > FilterResGW;
571 FilterResGW filter_res_graph(res_graph, true_map, dist);
573 //Subgraph, which is able to delete edges which are already
575 typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
576 first_out_edges(filter_res_graph);
577 typename FilterResGW::NodeIt v;
578 for(filter_res_graph.first(v); filter_res_graph.valid(v);
579 filter_res_graph.next(v))
581 typename FilterResGW::OutEdgeIt e;
582 filter_res_graph.first(e, v);
583 first_out_edges.set(v, e);
585 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
586 NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
587 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
594 //computing blocking flow with dfs
595 DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> >
596 dfs(erasing_res_graph);
597 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
598 pred(erasing_res_graph);
599 pred.set(s, INVALID);
600 //invalid iterators for sources
602 typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph);
604 dfs.pushAndSetReached(
605 typename ErasingResGW::Node(
606 typename FilterResGW::Node(
607 typename ResGW::Node(s)
611 while (!dfs.finished()) {
613 if (erasing_res_graph.valid(
614 typename ErasingResGW::OutEdgeIt(dfs)))
616 if (dfs.isBNodeNewlyReached()) {
618 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
619 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
621 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
622 if (erasing_res_graph.valid(pred[v])) {
623 free1.set(w, std::min(free1[v], res_graph.resCap(
624 typename ErasingResGW::OutEdgeIt(dfs))));
626 free1.set(w, res_graph.resCap(
627 typename ErasingResGW::OutEdgeIt(dfs)));
636 erasing_res_graph.erase(dfs);
642 typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
643 // typename ResGW::NodeMap<Number> a(res_graph);
644 // typename ResGW::Node b;
646 // typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
647 // typename FilterResGW::Node b1;
649 // typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
650 // typename ErasingResGW::Node b2;
652 Number augment_value=free1[n];
653 while (erasing_res_graph.valid(pred[n])) {
654 typename ErasingResGW::OutEdgeIt e=pred[n];
655 res_graph.augment(e, augment_value);
656 n=erasing_res_graph.tail(e);
657 if (res_graph.resCap(e)==0)
658 erasing_res_graph.erase(e);
662 } //while (__augment)
668 //int num_of_augmentations=0;
669 while (augmentOnShortestPath()) {
670 //while (augmentOnBlockingFlow<MutableGraph>()) {
671 //std::cout << ++num_of_augmentations << " ";
672 //std::cout<<std::endl;
676 template<typename MutableGraph> void run() {
677 //int num_of_augmentations=0;
678 //while (augmentOnShortestPath()) {
679 while (augmentOnBlockingFlow<MutableGraph>()) {
680 //std::cout << ++num_of_augmentations << " ";
681 //std::cout<<std::endl;
688 for(g->first(e, s); g->valid(e); g->next(e)) {
697 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
698 // class MaxMatching {
700 // typedef typename Graph::Node Node;
701 // typedef typename Graph::NodeIt NodeIt;
702 // typedef typename Graph::Edge Edge;
703 // typedef typename Graph::EdgeIt EdgeIt;
704 // typedef typename Graph::OutEdgeIt OutEdgeIt;
705 // typedef typename Graph::InEdgeIt InEdgeIt;
707 // typedef typename Graph::NodeMap<bool> SMap;
708 // typedef typename Graph::NodeMap<bool> TMap;
716 // const CapacityMap* capacity;
717 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
718 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
719 // typedef typename AugGraph::Edge AugEdge;
720 // typename Graph::NodeMap<int> used; //0
723 // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
724 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
725 // bool augmentOnShortestPath() {
726 // AugGraph res_graph(*G, *flow, *capacity);
727 // bool _augment=false;
729 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
730 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
731 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
732 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
733 // if ((S->get(s)) && (used.get(s)<1) ) {
735 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
736 // //u+=flow->get(e);
738 // bfs.pushAndSetReached(s);
739 // pred.set(s, AugEdge(INVALID));
744 // typename AugGraph::NodeMap<Number> free(res_graph);
747 // //searching for augmenting path
748 // while ( !bfs.finished() ) {
749 // AugOutEdgeIt e=bfs;
750 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
751 // Node v=res_graph.tail(e);
752 // Node w=res_graph.head(e);
754 // if (res_graph.valid(pred.get(v))) {
755 // free.set(w, std::min(free.get(v), res_graph.free(e)));
757 // free.set(w, res_graph.free(e));
759 // n=res_graph.head(e);
760 // if (T->get(n) && (used.get(n)<1) ) {
762 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
763 // //u+=flow->get(f);
772 // } //end of searching augmenting path
776 // used.set(n, 1); //mind2 vegen jav
777 // Number augment_value=free.get(n);
778 // while (res_graph.valid(pred.get(n))) {
779 // AugEdge e=pred.get(n);
780 // res_graph.augment(e, augment_value);
781 // n=res_graph.tail(e);
783 // used.set(n, 1); //mind2 vegen jav
789 // // template<typename MutableGraph> bool augmentOnBlockingFlow() {
790 // // bool _augment=false;
792 // // AugGraph res_graph(*G, *flow, *capacity);
794 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
795 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
801 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
802 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
803 // // if (S->get(s)) {
805 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
806 // // u+=flow->get(e);
808 // // bfs.pushAndSetReached(s);
809 // // //pred.set(s, AugEdge(INVALID));
817 // // //bfs.pushAndSetReached(s);
818 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
819 // // while ( !bfs.finished() ) {
820 // // AugOutEdgeIt e=bfs;
821 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
822 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
826 // // } //computing distances from s in the residual graph
828 // // MutableGraph F;
829 // // typename AugGraph::NodeMap<typename MutableGraph::Node>
830 // // res_graph_to_F(res_graph);
831 // // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
832 // // res_graph_to_F.set(n, F.addNode());
835 // // typename MutableGraph::Node sF=res_graph_to_F.get(s);
836 // // typename MutableGraph::Node tF=res_graph_to_F.get(t);
838 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
839 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
841 // // //Making F to the graph containing the edges of the residual graph
842 // // //which are in some shortest paths
843 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
844 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
845 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
846 // // original_edge.update();
847 // // original_edge.set(f, e);
848 // // residual_capacity.update();
849 // // residual_capacity.set(f, res_graph.free(e));
853 // // bool __augment=true;
855 // // while (__augment) {
856 // // __augment=false;
857 // // //computing blocking flow with dfs
858 // // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
859 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
860 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
861 // // pred.set(sF, typename MutableGraph::Edge(INVALID));
862 // // //invalid iterators for sources
864 // // typename MutableGraph::NodeMap<Number> free(F);
866 // // dfs.pushAndSetReached(sF);
867 // // while (!dfs.finished()) {
869 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
870 // // if (dfs.isBNodeNewlyReached()) {
871 // // typename MutableGraph::Node v=F.aNode(dfs);
872 // // typename MutableGraph::Node w=F.bNode(dfs);
873 // // pred.set(w, dfs);
874 // // if (F.valid(pred.get(v))) {
875 // // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
877 // // free.set(w, residual_capacity.get(dfs));
880 // // __augment=true;
886 // // F.erase(typename MutableGraph::OutEdgeIt(dfs));
891 // // if (__augment) {
892 // // typename MutableGraph::Node n=tF;
893 // // Number augment_value=free.get(tF);
894 // // while (F.valid(pred.get(n))) {
895 // // typename MutableGraph::Edge e=pred.get(n);
896 // // res_graph.augment(original_edge.get(e), augment_value);
898 // // if (residual_capacity.get(e)==augment_value)
901 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
907 // // return _augment;
909 // bool augmentOnBlockingFlow2() {
910 // bool _augment=false;
912 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
913 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
914 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
915 // typedef typename EAugGraph::Edge EAugEdge;
917 // EAugGraph res_graph(*G, *flow, *capacity);
919 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
921 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
922 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
923 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(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 // bfs.pushAndSetReached(s);
934 // //pred.set(s, AugEdge(INVALID));
940 // //bfs.pushAndSetReached(s);
942 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
943 // NodeMap<int>& dist=res_graph.dist;
945 // while ( !bfs.finished() ) {
946 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
947 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
948 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
951 // } //computing distances from s in the residual graph
953 // bool __augment=true;
955 // while (__augment) {
958 // //computing blocking flow with dfs
959 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
960 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
962 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
963 // //pred.set(s, EAugEdge(INVALID));
964 // //invalid iterators for sources
966 // typename EAugGraph::NodeMap<Number> free(res_graph);
969 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
970 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
973 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
976 // dfs.pushAndSetReached(s);
977 // //pred.set(s, AugEdge(INVALID));
984 // //dfs.pushAndSetReached(s);
985 // typename EAugGraph::Node n;
986 // while (!dfs.finished()) {
988 // if (res_graph.valid(EAugOutEdgeIt(dfs))) {
989 // if (dfs.isBNodeNewlyReached()) {
991 // typename EAugGraph::Node v=res_graph.aNode(dfs);
992 // typename EAugGraph::Node w=res_graph.bNode(dfs);
994 // pred.set(w, EAugOutEdgeIt(dfs));
995 // if (res_graph.valid(pred.get(v))) {
996 // free.set(w, std::min(free.get(v), res_graph.free(dfs)));
998 // free.set(w, res_graph.free(dfs));
1004 // for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1013 // res_graph.erase(dfs);
1020 // // typename EAugGraph::Node n=t;
1021 // Number augment_value=free.get(n);
1022 // while (res_graph.valid(pred.get(n))) {
1023 // EAugEdge e=pred.get(n);
1024 // res_graph.augment(e, augment_value);
1025 // n=res_graph.tail(e);
1026 // if (res_graph.free(e)==0)
1027 // res_graph.erase(e);
1036 // //int num_of_augmentations=0;
1037 // while (augmentOnShortestPath()) {
1038 // //while (augmentOnBlockingFlow<MutableGraph>()) {
1039 // //std::cout << ++num_of_augmentations << " ";
1040 // //std::cout<<std::endl;
1043 // // template<typename MutableGraph> void run() {
1044 // // //int num_of_augmentations=0;
1045 // // //while (augmentOnShortestPath()) {
1046 // // while (augmentOnBlockingFlow<MutableGraph>()) {
1047 // // //std::cout << ++num_of_augmentations << " ";
1048 // // //std::cout<<std::endl;
1051 // Number flowValue() {
1054 // for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1066 // // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1067 // // class MaxFlow2 {
1069 // // typedef typename Graph::Node Node;
1070 // // typedef typename Graph::Edge Edge;
1071 // // typedef typename Graph::EdgeIt EdgeIt;
1072 // // typedef typename Graph::OutEdgeIt OutEdgeIt;
1073 // // typedef typename Graph::InEdgeIt InEdgeIt;
1075 // // const Graph& G;
1076 // // std::list<Node>& S;
1077 // // std::list<Node>& T;
1078 // // FlowMap& flow;
1079 // // const CapacityMap& capacity;
1080 // // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1081 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1082 // // typedef typename AugGraph::Edge AugEdge;
1083 // // typename Graph::NodeMap<bool> SMap;
1084 // // typename Graph::NodeMap<bool> TMap;
1086 // // 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) {
1087 // // for(typename std::list<Node>::const_iterator i=S.begin();
1088 // // i!=S.end(); ++i) {
1089 // // SMap.set(*i, true);
1091 // // for (typename std::list<Node>::const_iterator i=T.begin();
1092 // // i!=T.end(); ++i) {
1093 // // TMap.set(*i, true);
1096 // // bool augment() {
1097 // // AugGraph res_graph(G, flow, capacity);
1098 // // bool _augment=false;
1099 // // Node reached_t_node;
1101 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1102 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1103 // // for(typename std::list<Node>::const_iterator i=S.begin();
1104 // // i!=S.end(); ++i) {
1105 // // bfs.pushAndSetReached(*i);
1107 // // //bfs.pushAndSetReached(s);
1109 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1110 // // //filled up with invalid iterators
1112 // // typename AugGraph::NodeMap<Number> free(res_graph);
1114 // // //searching for augmenting path
1115 // // while ( !bfs.finished() ) {
1116 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1117 // // if (e.valid() && bfs.isBNodeNewlyReached()) {
1118 // // Node v=res_graph.tail(e);
1119 // // Node w=res_graph.head(e);
1120 // // pred.set(w, e);
1121 // // if (pred.get(v).valid()) {
1122 // // free.set(w, std::min(free.get(v), e.free()));
1124 // // free.set(w, e.free());
1126 // // if (TMap.get(res_graph.head(e))) {
1127 // // _augment=true;
1128 // // reached_t_node=res_graph.head(e);
1134 // // } //end of searching augmenting path
1136 // // if (_augment) {
1137 // // Node n=reached_t_node;
1138 // // Number augment_value=free.get(reached_t_node);
1139 // // while (pred.get(n).valid()) {
1140 // // AugEdge e=pred.get(n);
1141 // // e.augment(augment_value);
1142 // // n=res_graph.tail(e);
1146 // // return _augment;
1149 // // while (augment()) { }
1151 // // Number flowValue() {
1153 // // for(typename std::list<Node>::const_iterator i=S.begin();
1154 // // i!=S.end(); ++i) {
1155 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1156 // // a+=flow.get(e);
1158 // // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1159 // // a-=flow.get(e);
1169 #endif //HUGO_EDMONDS_KARP_H