DirPath fejlodes.
Kiserleti struktura a forditasi idoben kapcsolhato konzisztencia es range
ellenorzesekre.
2 #ifndef HUGO_EDMONDS_KARP_H
3 #define HUGO_EDMONDS_KARP_H
9 #include <bfs_iterator.h>
11 #include <graph_wrapper.h>
13 #include <for_each_macros.h>
17 template <typename Graph, typename Num,
18 typename CapMap, typename FlowMap>
21 typedef typename Graph::Node Node;
22 typedef typename Graph::Edge Edge;
23 typedef typename Graph::EdgeIt EdgeIt;
24 typedef typename Graph::OutEdgeIt OutEdgeIt;
25 typedef typename Graph::InEdgeIt InEdgeIt;
29 const CapMap* capacity;
31 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
32 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
33 typedef typename ResGW::Edge ResGWEdge;
34 //typedef typename ResGW::template NodeMap<bool> ReachedMap;
35 typedef typename Graph::template NodeMap<bool> ReachedMap;
37 //reached is called level because of compatibility with preflow
40 MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity,
42 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
44 bool augmentOnShortestPath() {
45 ResGW res_graph(*g, *capacity, *flow);
48 //ReachedMap level(res_graph);
49 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
50 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
51 bfs.pushAndSetReached(s);
53 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
56 typename ResGW::template NodeMap<Num> free(res_graph);
58 //searching for augmenting path
59 while ( !bfs.finished() ) {
61 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
62 Node v=res_graph.tail(e);
63 Node w=res_graph.head(e);
65 if (res_graph.valid(pred[v])) {
66 free.set(w, std::min(free[v], res_graph.resCap(e)));
68 free.set(w, res_graph.resCap(e));
70 if (res_graph.head(e)==t) { _augment=true; break; }
74 } //end of searching augmenting path
78 Num augment_value=free[t];
79 while (res_graph.valid(pred[n])) {
81 res_graph.augment(e, augment_value);
89 template<typename MapGraphWrapper>
92 const MapGraphWrapper* g;
93 typename MapGraphWrapper::template NodeMap<int> dist;
95 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
96 void set(const typename MapGraphWrapper::Node& n, int a) {
99 int operator[](const typename MapGraphWrapper::Node& n)
101 // int get(const typename MapGraphWrapper::Node& n) const {
103 // bool get(const typename MapGraphWrapper::Edge& e) const {
104 // return (dist.get(g->tail(e))<dist.get(g->head(e))); }
105 bool operator[](const typename MapGraphWrapper::Edge& e) const {
106 return (dist[g->tail(e)]<dist[g->head(e)]);
110 template<typename MutableGraph> bool augmentOnBlockingFlow() {
111 typedef MutableGraph MG;
114 ResGW res_graph(*g, *capacity, *flow);
116 //ReachedMap level(res_graph);
117 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
118 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
120 bfs.pushAndSetReached(s);
121 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
122 DistanceMap<ResGW> dist(res_graph);
123 while ( !bfs.finished() ) {
124 ResGWOutEdgeIt e=bfs;
125 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
126 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
129 } //computing distances from s in the residual graph
132 ConstMap<typename ResGW::Node, bool> true_map(true);
133 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
134 DistanceMap<ResGW> > FilterResGW;
135 FilterResGW filter_res_graph(res_graph, true_map, dist);
136 typename ResGW::template NodeMap<typename MG::Node>
137 res_graph_to_F(res_graph);
139 typename ResGW::NodeIt n;
140 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
141 res_graph_to_F.set(n, F.addNode());
145 typename MG::Node sF=res_graph_to_F[s];
146 typename MG::Node tF=res_graph_to_F[t];
147 typename MG::template EdgeMap<ResGWEdge> original_edge(F);
148 typename MG::template EdgeMap<Num> residual_capacity(F);
150 //Making F to the graph containing the edges of the residual graph
151 //which are in some shortest paths
153 typename FilterResGW::EdgeIt e;
154 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
155 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
157 original_edge.update();
158 original_edge.set(f, e);
159 residual_capacity.update();
160 residual_capacity.set(f, res_graph.resCap(e));
169 //computing blocking flow with dfs
171 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
172 typename MG::template NodeMap<typename MG::Edge> pred(F);
173 pred.set(sF, INVALID);
174 //invalid iterators for sources
176 typename MG::template NodeMap<Num> free(F);
178 dfs.pushAndSetReached(sF);
179 while (!dfs.finished()) {
181 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
182 if (dfs.isBNodeNewlyReached()) {
183 typename MG::Node v=F.aNode(dfs);
184 typename MG::Node w=F.bNode(dfs);
186 if (F.valid(pred[v])) {
187 free.set(w, std::min(free[v], residual_capacity[dfs]));
189 free.set(w, residual_capacity[dfs]);
198 F.erase(/*typename MG::OutEdgeIt*/(dfs));
204 typename MG::Node n=tF;
205 Num augment_value=free[tF];
206 while (F.valid(pred[n])) {
207 typename MG::Edge e=pred[n];
208 res_graph.augment(original_edge[e], augment_value);
210 if (residual_capacity[e]==augment_value)
213 residual_capacity.set(e, residual_capacity[e]-augment_value);
222 template<typename MutableGraph> bool augmentOnBlockingFlow1() {
223 typedef MutableGraph MG;
226 ResGW res_graph(*g, *capacity, *flow);
228 //bfs for distances on the residual graph
229 //ReachedMap level(res_graph);
230 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
231 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
232 bfs.pushAndSetReached(s);
233 typename ResGW::template NodeMap<int>
234 dist(res_graph); //filled up with 0's
236 //F will contain the physical copy of the residual graph
237 //with the set of edges which are on shortest paths
239 typename ResGW::template NodeMap<typename MG::Node>
240 res_graph_to_F(res_graph);
242 typename ResGW::NodeIt n;
243 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
244 res_graph_to_F.set(n, F.addNode());
248 typename MG::Node sF=res_graph_to_F[s];
249 typename MG::Node tF=res_graph_to_F[t];
250 typename MG::template EdgeMap<ResGWEdge> original_edge(F);
251 typename MG::template EdgeMap<Num> residual_capacity(F);
253 while ( !bfs.finished() ) {
254 ResGWOutEdgeIt e=bfs;
255 if (res_graph.valid(e)) {
256 if (bfs.isBNodeNewlyReached()) {
257 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
259 original_edge.update();
260 original_edge.set(f, e);
261 residual_capacity.update();
262 residual_capacity.set(f, res_graph.resCap(e));
264 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
266 original_edge.update();
267 original_edge.set(f, e);
268 residual_capacity.update();
269 residual_capacity.set(f, res_graph.resCap(e));
274 } //computing distances from s in the residual graph
280 //computing blocking flow with dfs
281 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
282 typename MG::template NodeMap<typename MG::Edge> pred(F);
283 pred.set(sF, INVALID);
284 //invalid iterators for sources
286 typename MG::template NodeMap<Num> free(F);
288 dfs.pushAndSetReached(sF);
289 while (!dfs.finished()) {
291 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
292 if (dfs.isBNodeNewlyReached()) {
293 typename MG::Node v=F.aNode(dfs);
294 typename MG::Node w=F.bNode(dfs);
296 if (F.valid(pred[v])) {
297 free.set(w, std::min(free[v], residual_capacity[dfs]));
299 free.set(w, residual_capacity[dfs]);
308 F.erase(/*typename MG::OutEdgeIt*/(dfs));
314 typename MG::Node n=tF;
315 Num augment_value=free[tF];
316 while (F.valid(pred[n])) {
317 typename MG::Edge e=pred[n];
318 res_graph.augment(original_edge[e], augment_value);
320 if (residual_capacity[e]==augment_value)
323 residual_capacity.set(e, residual_capacity[e]-augment_value);
332 bool augmentOnBlockingFlow2() {
335 ResGW res_graph(*g, *capacity, *flow);
337 //ReachedMap level(res_graph);
338 FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
339 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
341 bfs.pushAndSetReached(s);
342 DistanceMap<ResGW> dist(res_graph);
343 while ( !bfs.finished() ) {
344 ResGWOutEdgeIt e=bfs;
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
346 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
349 } //computing distances from s in the residual graph
351 //Subgraph containing the edges on some shortest paths
352 ConstMap<typename ResGW::Node, bool> true_map(true);
353 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
354 DistanceMap<ResGW> > FilterResGW;
355 FilterResGW filter_res_graph(res_graph, true_map, dist);
357 //Subgraph, which is able to delete edges which are already
359 typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
360 first_out_edges(filter_res_graph);
361 typename FilterResGW::NodeIt v;
362 for(filter_res_graph.first(v); filter_res_graph.valid(v);
363 filter_res_graph.next(v))
365 typename FilterResGW::OutEdgeIt e;
366 filter_res_graph.first(e, v);
367 first_out_edges.set(v, e);
369 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
370 template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
371 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
378 //computing blocking flow with dfs
379 DfsIterator< ErasingResGW,
380 typename ErasingResGW::template NodeMap<bool> >
381 dfs(erasing_res_graph);
382 typename ErasingResGW::
383 template NodeMap<typename ErasingResGW::OutEdgeIt>
384 pred(erasing_res_graph);
385 pred.set(s, INVALID);
386 //invalid iterators for sources
388 typename ErasingResGW::template NodeMap<Num>
389 free1(erasing_res_graph);
391 dfs.pushAndSetReached(
392 typename ErasingResGW::Node(
393 typename FilterResGW::Node(
394 typename ResGW::Node(s)
398 while (!dfs.finished()) {
400 if (erasing_res_graph.valid(
401 typename ErasingResGW::OutEdgeIt(dfs)))
403 if (dfs.isBNodeNewlyReached()) {
405 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
406 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
408 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
409 if (erasing_res_graph.valid(pred[v])) {
410 free1.set(w, std::min(free1[v], res_graph.resCap(
411 typename ErasingResGW::OutEdgeIt(dfs))));
413 free1.set(w, res_graph.resCap(
414 typename ErasingResGW::OutEdgeIt(dfs)));
423 erasing_res_graph.erase(dfs);
429 typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
430 // typename ResGW::NodeMap<Num> a(res_graph);
431 // typename ResGW::Node b;
433 // typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
434 // typename FilterResGW::Node b1;
436 // typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
437 // typename ErasingResGW::Node b2;
439 Num augment_value=free1[n];
440 while (erasing_res_graph.valid(pred[n])) {
441 typename ErasingResGW::OutEdgeIt e=pred[n];
442 res_graph.augment(e, augment_value);
443 n=erasing_res_graph.tail(e);
444 if (res_graph.resCap(e)==0)
445 erasing_res_graph.erase(e);
449 } //while (__augment)
455 //int num_of_augmentations=0;
456 while (augmentOnShortestPath()) {
457 //while (augmentOnBlockingFlow<MutableGraph>()) {
458 //std::cout << ++num_of_augmentations << " ";
459 //std::cout<<std::endl;
463 template<typename MutableGraph> void run() {
464 //int num_of_augmentations=0;
465 //while (augmentOnShortestPath()) {
466 while (augmentOnBlockingFlow<MutableGraph>()) {
467 //std::cout << ++num_of_augmentations << " ";
468 //std::cout<<std::endl;
475 for(g->first(e, s); g->valid(e); g->next(e)) {
484 // template <typename Graph, typename Num, typename FlowMap, typename CapMap>
485 // class MaxMatching {
487 // typedef typename Graph::Node Node;
488 // typedef typename Graph::NodeIt NodeIt;
489 // typedef typename Graph::Edge Edge;
490 // typedef typename Graph::EdgeIt EdgeIt;
491 // typedef typename Graph::OutEdgeIt OutEdgeIt;
492 // typedef typename Graph::InEdgeIt InEdgeIt;
494 // typedef typename Graph::NodeMap<bool> SMap;
495 // typedef typename Graph::NodeMap<bool> TMap;
503 // const CapMap* capacity;
504 // typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
505 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
506 // typedef typename AugGraph::Edge AugEdge;
507 // typename Graph::NodeMap<int> used; //0
510 // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapMap& _capacity) :
511 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
512 // bool augmentOnShortestPath() {
513 // AugGraph res_graph(*G, *flow, *capacity);
514 // bool _augment=false;
516 // typedef typename AugGraph::NodeMap<bool> ReachedMap;
517 // BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
518 // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
519 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
520 // if ((S->get(s)) && (used.get(s)<1) ) {
522 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
523 // //u+=flow->get(e);
525 // bfs.pushAndSetReached(s);
526 // pred.set(s, AugEdge(INVALID));
531 // typename AugGraph::NodeMap<Num> free(res_graph);
534 // //searching for augmenting path
535 // while ( !bfs.finished() ) {
536 // AugOutEdgeIt e=bfs;
537 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
538 // Node v=res_graph.tail(e);
539 // Node w=res_graph.head(e);
541 // if (res_graph.valid(pred.get(v))) {
542 // free.set(w, std::min(free.get(v), res_graph.free(e)));
544 // free.set(w, res_graph.free(e));
546 // n=res_graph.head(e);
547 // if (T->get(n) && (used.get(n)<1) ) {
549 // //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
550 // //u+=flow->get(f);
559 // } //end of searching augmenting path
563 // used.set(n, 1); //mind2 vegen jav
564 // Num augment_value=free.get(n);
565 // while (res_graph.valid(pred.get(n))) {
566 // AugEdge e=pred.get(n);
567 // res_graph.augment(e, augment_value);
568 // n=res_graph.tail(e);
570 // used.set(n, 1); //mind2 vegen jav
576 // // template<typename MutableGraph> bool augmentOnBlockingFlow() {
577 // // bool _augment=false;
579 // // AugGraph res_graph(*G, *flow, *capacity);
581 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
582 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
588 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
589 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
590 // // if (S->get(s)) {
592 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
593 // // u+=flow->get(e);
595 // // bfs.pushAndSetReached(s);
596 // // //pred.set(s, AugEdge(INVALID));
604 // // //bfs.pushAndSetReached(s);
605 // // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
606 // // while ( !bfs.finished() ) {
607 // // AugOutEdgeIt e=bfs;
608 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
609 // // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
613 // // } //computing distances from s in the residual graph
615 // // MutableGraph F;
616 // // typename AugGraph::NodeMap<typename MutableGraph::Node>
617 // // res_graph_to_F(res_graph);
618 // // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
619 // // res_graph_to_F.set(n, F.addNode());
622 // // typename MutableGraph::Node sF=res_graph_to_F.get(s);
623 // // typename MutableGraph::Node tF=res_graph_to_F.get(t);
625 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
626 // // typename MutableGraph::EdgeMap<Num> residual_capacity(F);
628 // // //Making F to the graph containing the edges of the residual graph
629 // // //which are in some shortest paths
630 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
631 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
633 // // original_edge.update();
634 // // original_edge.set(f, e);
635 // // residual_capacity.update();
636 // // residual_capacity.set(f, res_graph.free(e));
640 // // bool __augment=true;
642 // // while (__augment) {
643 // // __augment=false;
644 // // //computing blocking flow with dfs
645 // // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
646 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
647 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
648 // // pred.set(sF, typename MutableGraph::Edge(INVALID));
649 // // //invalid iterators for sources
651 // // typename MutableGraph::NodeMap<Num> free(F);
653 // // dfs.pushAndSetReached(sF);
654 // // while (!dfs.finished()) {
656 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
657 // // if (dfs.isBNodeNewlyReached()) {
658 // // typename MutableGraph::Node v=F.aNode(dfs);
659 // // typename MutableGraph::Node w=F.bNode(dfs);
660 // // pred.set(w, dfs);
661 // // if (F.valid(pred.get(v))) {
662 // // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
664 // // free.set(w, residual_capacity.get(dfs));
667 // // __augment=true;
673 // // F.erase(typename MutableGraph::OutEdgeIt(dfs));
678 // // if (__augment) {
679 // // typename MutableGraph::Node n=tF;
680 // // Num augment_value=free.get(tF);
681 // // while (F.valid(pred.get(n))) {
682 // // typename MutableGraph::Edge e=pred.get(n);
683 // // res_graph.augment(original_edge.get(e), augment_value);
685 // // if (residual_capacity.get(e)==augment_value)
688 // // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
694 // // return _augment;
696 // bool augmentOnBlockingFlow2() {
697 // bool _augment=false;
699 // //typedef ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> EAugGraph;
700 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> > EAugGraph;
701 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
702 // typedef typename EAugGraph::Edge EAugEdge;
704 // EAugGraph res_graph(*G, *flow, *capacity);
706 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
708 // ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>,
709 // /*typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt,*/
710 // ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::NodeMap<bool> > bfs(res_graph);
713 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
714 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
717 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
720 // bfs.pushAndSetReached(s);
721 // //pred.set(s, AugEdge(INVALID));
727 // //bfs.pushAndSetReached(s);
729 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::
730 // NodeMap<int>& dist=res_graph.dist;
732 // while ( !bfs.finished() ) {
733 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
735 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
738 // } //computing distances from s in the residual graph
740 // bool __augment=true;
742 // while (__augment) {
745 // //computing blocking flow with dfs
746 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
747 // DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
749 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
750 // //pred.set(s, EAugEdge(INVALID));
751 // //invalid iterators for sources
753 // typename EAugGraph::NodeMap<Num> free(res_graph);
756 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
757 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
760 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
763 // dfs.pushAndSetReached(s);
764 // //pred.set(s, AugEdge(INVALID));
771 // //dfs.pushAndSetReached(s);
772 // typename EAugGraph::Node n;
773 // while (!dfs.finished()) {
775 // if (res_graph.valid(EAugOutEdgeIt(dfs))) {
776 // if (dfs.isBNodeNewlyReached()) {
778 // typename EAugGraph::Node v=res_graph.aNode(dfs);
779 // typename EAugGraph::Node w=res_graph.bNode(dfs);
781 // pred.set(w, EAugOutEdgeIt(dfs));
782 // if (res_graph.valid(pred.get(v))) {
783 // free.set(w, std::min(free.get(v), res_graph.free(dfs)));
785 // free.set(w, res_graph.free(dfs));
791 // for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
800 // res_graph.erase(dfs);
807 // // typename EAugGraph::Node n=t;
808 // Num augment_value=free.get(n);
809 // while (res_graph.valid(pred.get(n))) {
810 // EAugEdge e=pred.get(n);
811 // res_graph.augment(e, augment_value);
812 // n=res_graph.tail(e);
813 // if (res_graph.free(e)==0)
814 // res_graph.erase(e);
823 // //int num_of_augmentations=0;
824 // while (augmentOnShortestPath()) {
825 // //while (augmentOnBlockingFlow<MutableGraph>()) {
826 // //std::cout << ++num_of_augmentations << " ";
827 // //std::cout<<std::endl;
830 // // template<typename MutableGraph> void run() {
831 // // //int num_of_augmentations=0;
832 // // //while (augmentOnShortestPath()) {
833 // // while (augmentOnBlockingFlow<MutableGraph>()) {
834 // // //std::cout << ++num_of_augmentations << " ";
835 // // //std::cout<<std::endl;
841 // for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
853 // // template <typename Graph, typename Num, typename FlowMap, typename CapMap>
854 // // class MaxFlow2 {
856 // // typedef typename Graph::Node Node;
857 // // typedef typename Graph::Edge Edge;
858 // // typedef typename Graph::EdgeIt EdgeIt;
859 // // typedef typename Graph::OutEdgeIt OutEdgeIt;
860 // // typedef typename Graph::InEdgeIt InEdgeIt;
862 // // const Graph& G;
863 // // std::list<Node>& S;
864 // // std::list<Node>& T;
866 // // const CapMap& capacity;
867 // // typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
868 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
869 // // typedef typename AugGraph::Edge AugEdge;
870 // // typename Graph::NodeMap<bool> SMap;
871 // // typename Graph::NodeMap<bool> TMap;
873 // // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
874 // // for(typename std::list<Node>::const_iterator i=S.begin();
875 // // i!=S.end(); ++i) {
876 // // SMap.set(*i, true);
878 // // for (typename std::list<Node>::const_iterator i=T.begin();
879 // // i!=T.end(); ++i) {
880 // // TMap.set(*i, true);
883 // // bool augment() {
884 // // AugGraph res_graph(G, flow, capacity);
885 // // bool _augment=false;
886 // // Node reached_t_node;
888 // // typedef typename AugGraph::NodeMap<bool> ReachedMap;
889 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
890 // // for(typename std::list<Node>::const_iterator i=S.begin();
891 // // i!=S.end(); ++i) {
892 // // bfs.pushAndSetReached(*i);
894 // // //bfs.pushAndSetReached(s);
896 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
897 // // //filled up with invalid iterators
899 // // typename AugGraph::NodeMap<Num> free(res_graph);
901 // // //searching for augmenting path
902 // // while ( !bfs.finished() ) {
903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
904 // // if (e.valid() && bfs.isBNodeNewlyReached()) {
905 // // Node v=res_graph.tail(e);
906 // // Node w=res_graph.head(e);
907 // // pred.set(w, e);
908 // // if (pred.get(v).valid()) {
909 // // free.set(w, std::min(free.get(v), e.free()));
911 // // free.set(w, e.free());
913 // // if (TMap.get(res_graph.head(e))) {
915 // // reached_t_node=res_graph.head(e);
921 // // } //end of searching augmenting path
923 // // if (_augment) {
924 // // Node n=reached_t_node;
925 // // Num augment_value=free.get(reached_t_node);
926 // // while (pred.get(n).valid()) {
927 // // AugEdge e=pred.get(n);
928 // // e.augment(augment_value);
929 // // n=res_graph.tail(e);
933 // // return _augment;
936 // // while (augment()) { }
938 // // Num flowValue() {
940 // // for(typename std::list<Node>::const_iterator i=S.begin();
941 // // i!=S.end(); ++i) {
942 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
943 // // a+=flow.get(e);
945 // // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
946 // // a-=flow.get(e);
956 #endif //HUGO_EDMONDS_KARP_H