12 #include <maps.h> |
12 #include <maps.h> |
13 #include <for_each_macros.h> |
13 #include <for_each_macros.h> |
14 |
14 |
15 namespace hugo { |
15 namespace hugo { |
16 |
16 |
17 template <typename Graph, typename Number, |
17 template <typename Graph, typename Num, |
18 typename CapacityMap, typename FlowMap> |
18 typename CapMap, typename FlowMap> |
19 class MaxFlow { |
19 class MaxFlow { |
20 protected: |
20 protected: |
21 typedef typename Graph::Node Node; |
21 typedef typename Graph::Node Node; |
22 typedef typename Graph::Edge Edge; |
22 typedef typename Graph::Edge Edge; |
23 typedef typename Graph::EdgeIt EdgeIt; |
23 typedef typename Graph::EdgeIt EdgeIt; |
24 typedef typename Graph::OutEdgeIt OutEdgeIt; |
24 typedef typename Graph::OutEdgeIt OutEdgeIt; |
25 typedef typename Graph::InEdgeIt InEdgeIt; |
25 typedef typename Graph::InEdgeIt InEdgeIt; |
26 const Graph* g; |
26 const Graph* g; |
27 Node s; |
27 Node s; |
28 Node t; |
28 Node t; |
29 const CapacityMap* capacity; |
29 const CapMap* capacity; |
30 FlowMap* flow; |
30 FlowMap* flow; |
31 typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW; |
31 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; |
32 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
32 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
33 typedef typename ResGW::Edge ResGWEdge; |
33 typedef typename ResGW::Edge ResGWEdge; |
34 //typedef typename ResGW::template NodeMap<bool> ReachedMap; |
34 //typedef typename ResGW::template NodeMap<bool> ReachedMap; |
35 typedef typename Graph::template NodeMap<bool> ReachedMap; |
35 typedef typename Graph::template NodeMap<bool> ReachedMap; |
36 ReachedMap level; |
36 ReachedMap level; |
37 //reached is called level because of compatibility with preflow |
37 //reached is called level because of compatibility with preflow |
38 public: |
38 public: |
39 |
39 |
40 MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity, |
40 MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity, |
41 FlowMap& _flow) : |
41 FlowMap& _flow) : |
42 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { } |
42 g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { } |
43 |
43 |
44 bool augmentOnShortestPath() { |
44 bool augmentOnShortestPath() { |
45 ResGW res_graph(*g, *capacity, *flow); |
45 ResGW res_graph(*g, *capacity, *flow); |
143 } |
143 } |
144 |
144 |
145 typename MG::Node sF=res_graph_to_F[s]; |
145 typename MG::Node sF=res_graph_to_F[s]; |
146 typename MG::Node tF=res_graph_to_F[t]; |
146 typename MG::Node tF=res_graph_to_F[t]; |
147 typename MG::template EdgeMap<ResGWEdge> original_edge(F); |
147 typename MG::template EdgeMap<ResGWEdge> original_edge(F); |
148 typename MG::template EdgeMap<Number> residual_capacity(F); |
148 typename MG::template EdgeMap<Num> residual_capacity(F); |
149 |
149 |
150 //Making F to the graph containing the edges of the residual graph |
150 //Making F to the graph containing the edges of the residual graph |
151 //which are in some shortest paths |
151 //which are in some shortest paths |
152 { |
152 { |
153 typename FilterResGW::EdgeIt e; |
153 typename FilterResGW::EdgeIt e; |
171 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); |
171 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); |
172 typename MG::template NodeMap<typename MG::Edge> pred(F); |
172 typename MG::template NodeMap<typename MG::Edge> pred(F); |
173 pred.set(sF, INVALID); |
173 pred.set(sF, INVALID); |
174 //invalid iterators for sources |
174 //invalid iterators for sources |
175 |
175 |
176 typename MG::template NodeMap<Number> free(F); |
176 typename MG::template NodeMap<Num> free(F); |
177 |
177 |
178 dfs.pushAndSetReached(sF); |
178 dfs.pushAndSetReached(sF); |
179 while (!dfs.finished()) { |
179 while (!dfs.finished()) { |
180 ++dfs; |
180 ++dfs; |
181 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
181 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
246 } |
246 } |
247 |
247 |
248 typename MG::Node sF=res_graph_to_F[s]; |
248 typename MG::Node sF=res_graph_to_F[s]; |
249 typename MG::Node tF=res_graph_to_F[t]; |
249 typename MG::Node tF=res_graph_to_F[t]; |
250 typename MG::template EdgeMap<ResGWEdge> original_edge(F); |
250 typename MG::template EdgeMap<ResGWEdge> original_edge(F); |
251 typename MG::template EdgeMap<Number> residual_capacity(F); |
251 typename MG::template EdgeMap<Num> residual_capacity(F); |
252 |
252 |
253 while ( !bfs.finished() ) { |
253 while ( !bfs.finished() ) { |
254 ResGWOutEdgeIt e=bfs; |
254 ResGWOutEdgeIt e=bfs; |
255 if (res_graph.valid(e)) { |
255 if (res_graph.valid(e)) { |
256 if (bfs.isBNodeNewlyReached()) { |
256 if (bfs.isBNodeNewlyReached()) { |
281 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); |
281 DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F); |
282 typename MG::template NodeMap<typename MG::Edge> pred(F); |
282 typename MG::template NodeMap<typename MG::Edge> pred(F); |
283 pred.set(sF, INVALID); |
283 pred.set(sF, INVALID); |
284 //invalid iterators for sources |
284 //invalid iterators for sources |
285 |
285 |
286 typename MG::template NodeMap<Number> free(F); |
286 typename MG::template NodeMap<Num> free(F); |
287 |
287 |
288 dfs.pushAndSetReached(sF); |
288 dfs.pushAndSetReached(sF); |
289 while (!dfs.finished()) { |
289 while (!dfs.finished()) { |
290 ++dfs; |
290 ++dfs; |
291 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
291 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
383 template NodeMap<typename ErasingResGW::OutEdgeIt> |
383 template NodeMap<typename ErasingResGW::OutEdgeIt> |
384 pred(erasing_res_graph); |
384 pred(erasing_res_graph); |
385 pred.set(s, INVALID); |
385 pred.set(s, INVALID); |
386 //invalid iterators for sources |
386 //invalid iterators for sources |
387 |
387 |
388 typename ErasingResGW::template NodeMap<Number> |
388 typename ErasingResGW::template NodeMap<Num> |
389 free1(erasing_res_graph); |
389 free1(erasing_res_graph); |
390 |
390 |
391 dfs.pushAndSetReached( |
391 dfs.pushAndSetReached( |
392 typename ErasingResGW::Node( |
392 typename ErasingResGW::Node( |
393 typename FilterResGW::Node( |
393 typename FilterResGW::Node( |
425 } |
425 } |
426 } |
426 } |
427 |
427 |
428 if (__augment) { |
428 if (__augment) { |
429 typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t)); |
429 typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t)); |
430 // typename ResGW::NodeMap<Number> a(res_graph); |
430 // typename ResGW::NodeMap<Num> a(res_graph); |
431 // typename ResGW::Node b; |
431 // typename ResGW::Node b; |
432 // Number j=a[b]; |
432 // Num j=a[b]; |
433 // typename FilterResGW::NodeMap<Number> a1(filter_res_graph); |
433 // typename FilterResGW::NodeMap<Num> a1(filter_res_graph); |
434 // typename FilterResGW::Node b1; |
434 // typename FilterResGW::Node b1; |
435 // Number j1=a1[b1]; |
435 // Num j1=a1[b1]; |
436 // typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph); |
436 // typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph); |
437 // typename ErasingResGW::Node b2; |
437 // typename ErasingResGW::Node b2; |
438 // Number j2=a2[b2]; |
438 // Num j2=a2[b2]; |
439 Number augment_value=free1[n]; |
439 Num augment_value=free1[n]; |
440 while (erasing_res_graph.valid(pred[n])) { |
440 while (erasing_res_graph.valid(pred[n])) { |
441 typename ErasingResGW::OutEdgeIt e=pred[n]; |
441 typename ErasingResGW::OutEdgeIt e=pred[n]; |
442 res_graph.augment(e, augment_value); |
442 res_graph.augment(e, augment_value); |
443 n=erasing_res_graph.tail(e); |
443 n=erasing_res_graph.tail(e); |
444 if (res_graph.resCap(e)==0) |
444 if (res_graph.resCap(e)==0) |
467 //std::cout << ++num_of_augmentations << " "; |
467 //std::cout << ++num_of_augmentations << " "; |
468 //std::cout<<std::endl; |
468 //std::cout<<std::endl; |
469 } |
469 } |
470 } |
470 } |
471 |
471 |
472 Number flowValue() { |
472 Num flowValue() { |
473 Number a=0; |
473 Num a=0; |
474 OutEdgeIt e; |
474 OutEdgeIt e; |
475 for(g->first(e, s); g->valid(e); g->next(e)) { |
475 for(g->first(e, s); g->valid(e); g->next(e)) { |
476 a+=(*flow)[e]; |
476 a+=(*flow)[e]; |
477 } |
477 } |
478 return a; |
478 return a; |
479 } |
479 } |
480 |
480 |
481 }; |
481 }; |
482 |
482 |
483 |
483 |
484 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
484 // template <typename Graph, typename Num, typename FlowMap, typename CapMap> |
485 // class MaxMatching { |
485 // class MaxMatching { |
486 // public: |
486 // public: |
487 // typedef typename Graph::Node Node; |
487 // typedef typename Graph::Node Node; |
488 // typedef typename Graph::NodeIt NodeIt; |
488 // typedef typename Graph::NodeIt NodeIt; |
489 // typedef typename Graph::Edge Edge; |
489 // typedef typename Graph::Edge Edge; |
498 // SMap* S; |
498 // SMap* S; |
499 // TMap* T; |
499 // TMap* T; |
500 // //Node s; |
500 // //Node s; |
501 // //Node t; |
501 // //Node t; |
502 // FlowMap* flow; |
502 // FlowMap* flow; |
503 // const CapacityMap* capacity; |
503 // const CapMap* capacity; |
504 // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
504 // typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph; |
505 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
505 // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
506 // typedef typename AugGraph::Edge AugEdge; |
506 // typedef typename AugGraph::Edge AugEdge; |
507 // typename Graph::NodeMap<int> used; //0 |
507 // typename Graph::NodeMap<int> used; //0 |
508 |
508 |
509 // public: |
509 // public: |
510 // MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : |
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) { } |
511 // G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } |
512 // bool augmentOnShortestPath() { |
512 // bool augmentOnShortestPath() { |
513 // AugGraph res_graph(*G, *flow, *capacity); |
513 // AugGraph res_graph(*G, *flow, *capacity); |
514 // bool _augment=false; |
514 // bool _augment=false; |
515 |
515 |
516 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
516 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
517 // BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); |
517 // BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); |
518 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
518 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
519 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
519 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
520 // if ((S->get(s)) && (used.get(s)<1) ) { |
520 // if ((S->get(s)) && (used.get(s)<1) ) { |
521 // //Number u=0; |
521 // //Num u=0; |
522 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
522 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
523 // //u+=flow->get(e); |
523 // //u+=flow->get(e); |
524 // //if (u<1) { |
524 // //if (u<1) { |
525 // bfs.pushAndSetReached(s); |
525 // bfs.pushAndSetReached(s); |
526 // pred.set(s, AugEdge(INVALID)); |
526 // pred.set(s, AugEdge(INVALID)); |
527 // //} |
527 // //} |
528 // } |
528 // } |
529 // } |
529 // } |
530 |
530 |
531 // typename AugGraph::NodeMap<Number> free(res_graph); |
531 // typename AugGraph::NodeMap<Num> free(res_graph); |
532 |
532 |
533 // Node n; |
533 // Node n; |
534 // //searching for augmenting path |
534 // //searching for augmenting path |
535 // while ( !bfs.finished() ) { |
535 // while ( !bfs.finished() ) { |
536 // AugOutEdgeIt e=bfs; |
536 // AugOutEdgeIt e=bfs; |
559 // } //end of searching augmenting path |
559 // } //end of searching augmenting path |
560 |
560 |
561 // if (_augment) { |
561 // if (_augment) { |
562 // //Node n=t; |
562 // //Node n=t; |
563 // used.set(n, 1); //mind2 vegen jav |
563 // used.set(n, 1); //mind2 vegen jav |
564 // Number augment_value=free.get(n); |
564 // Num augment_value=free.get(n); |
565 // while (res_graph.valid(pred.get(n))) { |
565 // while (res_graph.valid(pred.get(n))) { |
566 // AugEdge e=pred.get(n); |
566 // AugEdge e=pred.get(n); |
567 // res_graph.augment(e, augment_value); |
567 // res_graph.augment(e, augment_value); |
568 // n=res_graph.tail(e); |
568 // n=res_graph.tail(e); |
569 // } |
569 // } |
586 |
586 |
587 |
587 |
588 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
588 // // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
589 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
589 // // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
590 // // if (S->get(s)) { |
590 // // if (S->get(s)) { |
591 // // Number u=0; |
591 // // Num u=0; |
592 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
592 // // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
593 // // u+=flow->get(e); |
593 // // u+=flow->get(e); |
594 // // if (u<1) { |
594 // // if (u<1) { |
595 // // bfs.pushAndSetReached(s); |
595 // // bfs.pushAndSetReached(s); |
596 // // //pred.set(s, AugEdge(INVALID)); |
596 // // //pred.set(s, AugEdge(INVALID)); |
621 |
621 |
622 // // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
622 // // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
623 // // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
623 // // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
624 |
624 |
625 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
625 // // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
626 // // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
626 // // typename MutableGraph::EdgeMap<Num> residual_capacity(F); |
627 |
627 |
628 // // //Making F to the graph containing the edges of the residual graph |
628 // // //Making F to the graph containing the edges of the residual graph |
629 // // //which are in some shortest paths |
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)) { |
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) { |
631 // // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
646 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
646 // // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
647 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
647 // // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
648 // // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
648 // // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
649 // // //invalid iterators for sources |
649 // // //invalid iterators for sources |
650 |
650 |
651 // // typename MutableGraph::NodeMap<Number> free(F); |
651 // // typename MutableGraph::NodeMap<Num> free(F); |
652 |
652 |
653 // // dfs.pushAndSetReached(sF); |
653 // // dfs.pushAndSetReached(sF); |
654 // // while (!dfs.finished()) { |
654 // // while (!dfs.finished()) { |
655 // // ++dfs; |
655 // // ++dfs; |
656 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
656 // // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
675 // // } |
675 // // } |
676 // // } |
676 // // } |
677 |
677 |
678 // // if (__augment) { |
678 // // if (__augment) { |
679 // // typename MutableGraph::Node n=tF; |
679 // // typename MutableGraph::Node n=tF; |
680 // // Number augment_value=free.get(tF); |
680 // // Num augment_value=free.get(tF); |
681 // // while (F.valid(pred.get(n))) { |
681 // // while (F.valid(pred.get(n))) { |
682 // // typename MutableGraph::Edge e=pred.get(n); |
682 // // typename MutableGraph::Edge e=pred.get(n); |
683 // // res_graph.augment(original_edge.get(e), augment_value); |
683 // // res_graph.augment(original_edge.get(e), augment_value); |
684 // // n=F.tail(e); |
684 // // n=F.tail(e); |
685 // // if (residual_capacity.get(e)==augment_value) |
685 // // if (residual_capacity.get(e)==augment_value) |
694 // // return _augment; |
694 // // return _augment; |
695 // // } |
695 // // } |
696 // bool augmentOnBlockingFlow2() { |
696 // bool augmentOnBlockingFlow2() { |
697 // bool _augment=false; |
697 // bool _augment=false; |
698 |
698 |
699 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
699 // //typedef ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> EAugGraph; |
700 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
700 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> > EAugGraph; |
701 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
701 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
702 // typedef typename EAugGraph::Edge EAugEdge; |
702 // typedef typename EAugGraph::Edge EAugEdge; |
703 |
703 |
704 // EAugGraph res_graph(*G, *flow, *capacity); |
704 // EAugGraph res_graph(*G, *flow, *capacity); |
705 |
705 |
706 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
706 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
707 // BfsIterator< |
707 // BfsIterator< |
708 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
708 // ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>, |
709 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
709 // /*typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt,*/ |
710 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
710 // ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::NodeMap<bool> > bfs(res_graph); |
711 |
711 |
712 |
712 |
713 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
713 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
714 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
714 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
715 // if (S->get(s)) { |
715 // if (S->get(s)) { |
716 // Number u=0; |
716 // Num u=0; |
717 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
717 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
718 // u+=flow->get(e); |
718 // u+=flow->get(e); |
719 // if (u<1) { |
719 // if (u<1) { |
720 // bfs.pushAndSetReached(s); |
720 // bfs.pushAndSetReached(s); |
721 // //pred.set(s, AugEdge(INVALID)); |
721 // //pred.set(s, AugEdge(INVALID)); |
724 // } |
724 // } |
725 |
725 |
726 |
726 |
727 // //bfs.pushAndSetReached(s); |
727 // //bfs.pushAndSetReached(s); |
728 |
728 |
729 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
729 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>:: |
730 // NodeMap<int>& dist=res_graph.dist; |
730 // NodeMap<int>& dist=res_graph.dist; |
731 |
731 |
732 // while ( !bfs.finished() ) { |
732 // while ( !bfs.finished() ) { |
733 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
733 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs; |
734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
735 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
735 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
736 // } |
736 // } |
737 // ++bfs; |
737 // ++bfs; |
738 // } //computing distances from s in the residual graph |
738 // } //computing distances from s in the residual graph |
748 // dfs(res_graph); |
748 // dfs(res_graph); |
749 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
749 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
750 // //pred.set(s, EAugEdge(INVALID)); |
750 // //pred.set(s, EAugEdge(INVALID)); |
751 // //invalid iterators for sources |
751 // //invalid iterators for sources |
752 |
752 |
753 // typename EAugGraph::NodeMap<Number> free(res_graph); |
753 // typename EAugGraph::NodeMap<Num> free(res_graph); |
754 |
754 |
755 |
755 |
756 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
756 // //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
757 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
757 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
758 // if (S->get(s)) { |
758 // if (S->get(s)) { |
759 // Number u=0; |
759 // Num u=0; |
760 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
760 // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
761 // u+=flow->get(e); |
761 // u+=flow->get(e); |
762 // if (u<1) { |
762 // if (u<1) { |
763 // dfs.pushAndSetReached(s); |
763 // dfs.pushAndSetReached(s); |
764 // //pred.set(s, AugEdge(INVALID)); |
764 // //pred.set(s, AugEdge(INVALID)); |
803 |
803 |
804 // } |
804 // } |
805 |
805 |
806 // if (__augment) { |
806 // if (__augment) { |
807 // // typename EAugGraph::Node n=t; |
807 // // typename EAugGraph::Node n=t; |
808 // Number augment_value=free.get(n); |
808 // Num augment_value=free.get(n); |
809 // while (res_graph.valid(pred.get(n))) { |
809 // while (res_graph.valid(pred.get(n))) { |
810 // EAugEdge e=pred.get(n); |
810 // EAugEdge e=pred.get(n); |
811 // res_graph.augment(e, augment_value); |
811 // res_graph.augment(e, augment_value); |
812 // n=res_graph.tail(e); |
812 // n=res_graph.tail(e); |
813 // if (res_graph.free(e)==0) |
813 // if (res_graph.free(e)==0) |
848 |
848 |
849 |
849 |
850 |
850 |
851 |
851 |
852 |
852 |
853 // // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
853 // // template <typename Graph, typename Num, typename FlowMap, typename CapMap> |
854 // // class MaxFlow2 { |
854 // // class MaxFlow2 { |
855 // // public: |
855 // // public: |
856 // // typedef typename Graph::Node Node; |
856 // // typedef typename Graph::Node Node; |
857 // // typedef typename Graph::Edge Edge; |
857 // // typedef typename Graph::Edge Edge; |
858 // // typedef typename Graph::EdgeIt EdgeIt; |
858 // // typedef typename Graph::EdgeIt EdgeIt; |
861 // // private: |
861 // // private: |
862 // // const Graph& G; |
862 // // const Graph& G; |
863 // // std::list<Node>& S; |
863 // // std::list<Node>& S; |
864 // // std::list<Node>& T; |
864 // // std::list<Node>& T; |
865 // // FlowMap& flow; |
865 // // FlowMap& flow; |
866 // // const CapacityMap& capacity; |
866 // // const CapMap& capacity; |
867 // // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
867 // // typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph; |
868 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
868 // // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
869 // // typedef typename AugGraph::Edge AugEdge; |
869 // // typedef typename AugGraph::Edge AugEdge; |
870 // // typename Graph::NodeMap<bool> SMap; |
870 // // typename Graph::NodeMap<bool> SMap; |
871 // // typename Graph::NodeMap<bool> TMap; |
871 // // typename Graph::NodeMap<bool> TMap; |
872 // // public: |
872 // // public: |
873 // // 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) { |
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(); |
874 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
875 // // i!=S.end(); ++i) { |
875 // // i!=S.end(); ++i) { |
876 // // SMap.set(*i, true); |
876 // // SMap.set(*i, true); |
877 // // } |
877 // // } |
878 // // for (typename std::list<Node>::const_iterator i=T.begin(); |
878 // // for (typename std::list<Node>::const_iterator i=T.begin(); |
894 // // //bfs.pushAndSetReached(s); |
894 // // //bfs.pushAndSetReached(s); |
895 |
895 |
896 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
896 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
897 // // //filled up with invalid iterators |
897 // // //filled up with invalid iterators |
898 |
898 |
899 // // typename AugGraph::NodeMap<Number> free(res_graph); |
899 // // typename AugGraph::NodeMap<Num> free(res_graph); |
900 |
900 |
901 // // //searching for augmenting path |
901 // // //searching for augmenting path |
902 // // while ( !bfs.finished() ) { |
902 // // while ( !bfs.finished() ) { |
903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
904 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
904 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
920 // // ++bfs; |
920 // // ++bfs; |
921 // // } //end of searching augmenting path |
921 // // } //end of searching augmenting path |
922 |
922 |
923 // // if (_augment) { |
923 // // if (_augment) { |
924 // // Node n=reached_t_node; |
924 // // Node n=reached_t_node; |
925 // // Number augment_value=free.get(reached_t_node); |
925 // // Num augment_value=free.get(reached_t_node); |
926 // // while (pred.get(n).valid()) { |
926 // // while (pred.get(n).valid()) { |
927 // // AugEdge e=pred.get(n); |
927 // // AugEdge e=pred.get(n); |
928 // // e.augment(augment_value); |
928 // // e.augment(augment_value); |
929 // // n=res_graph.tail(e); |
929 // // n=res_graph.tail(e); |
930 // // } |
930 // // } |
933 // // return _augment; |
933 // // return _augment; |
934 // // } |
934 // // } |
935 // // void run() { |
935 // // void run() { |
936 // // while (augment()) { } |
936 // // while (augment()) { } |
937 // // } |
937 // // } |
938 // // Number flowValue() { |
938 // // Num flowValue() { |
939 // // Number a=0; |
939 // // Num a=0; |
940 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
940 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
941 // // i!=S.end(); ++i) { |
941 // // i!=S.end(); ++i) { |
942 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { |
942 // // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { |
943 // // a+=flow.get(e); |
943 // // a+=flow.get(e); |
944 // // } |
944 // // } |