246 S get(Node nit) const { return node_map.get(nit); } |
246 S get(Node nit) const { return node_map.get(nit); } |
247 }; |
247 }; |
248 }; |
248 }; |
249 |
249 |
250 |
250 |
251 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap> |
251 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
252 class MaxFlow { |
252 class MaxFlow { |
253 protected: |
253 protected: |
254 typedef GraphWrapper GW; |
254 typedef typename Graph::Node Node; |
255 typedef typename GW::Node Node; |
255 typedef typename Graph::Edge Edge; |
256 typedef typename GW::Edge Edge; |
256 typedef typename Graph::EdgeIt EdgeIt; |
257 typedef typename GW::EdgeIt EdgeIt; |
257 typedef typename Graph::OutEdgeIt OutEdgeIt; |
258 typedef typename GW::OutEdgeIt OutEdgeIt; |
258 typedef typename Graph::InEdgeIt InEdgeIt; |
259 typedef typename GW::InEdgeIt InEdgeIt; |
259 const Graph* g; |
260 //const Graph* G; |
|
261 //GW gw; |
|
262 const GW* g; |
|
263 Node s; |
260 Node s; |
264 Node t; |
261 Node t; |
265 FlowMap* flow; |
262 FlowMap* flow; |
266 const CapacityMap* capacity; |
263 const CapacityMap* capacity; |
267 typedef ResGraphWrapper<const GW, Number, FlowMap, CapacityMap > ResGW; |
264 typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW; |
268 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
265 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
269 typedef typename ResGW::Edge ResGWEdge; |
266 typedef typename ResGW::Edge ResGWEdge; |
270 public: |
267 public: |
271 |
268 |
272 MaxFlow(const GW& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
269 MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
273 g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
270 g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
274 |
271 |
275 bool augmentOnShortestPath() { |
272 bool augmentOnShortestPath() { |
276 ResGW res_graph(*g, *flow, *capacity); |
273 ResGW res_graph(*g, *flow, *capacity); |
277 bool _augment=false; |
274 bool _augment=false; |
643 |
640 |
644 } //while (__augment) |
641 } //while (__augment) |
645 |
642 |
646 return _augment; |
643 return _augment; |
647 } |
644 } |
648 |
|
649 // bool augmentOnBlockingFlow2() { |
|
650 // bool _augment=false; |
|
651 |
|
652 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
653 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
654 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
655 // typedef typename EAugGraph::Edge EAugEdge; |
|
656 |
|
657 // EAugGraph res_graph(*G, *flow, *capacity); |
|
658 |
|
659 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
660 // BfsIterator5< |
|
661 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
662 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
|
663 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
664 |
|
665 // bfs.pushAndSetReached(s); |
|
666 |
|
667 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
668 // NodeMap<int>& dist=res_graph.dist; |
|
669 |
|
670 // while ( !bfs.finished() ) { |
|
671 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
672 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
673 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
674 // } |
|
675 // ++bfs; |
|
676 // } //computing distances from s in the residual graph |
|
677 |
|
678 // bool __augment=true; |
|
679 |
|
680 // while (__augment) { |
|
681 |
|
682 // __augment=false; |
|
683 // //computing blocking flow with dfs |
|
684 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
685 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
|
686 // dfs(res_graph); |
|
687 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
|
688 // pred.set(s, EAugEdge(INVALID)); |
|
689 // //invalid iterators for sources |
|
690 |
|
691 // typename EAugGraph::NodeMap<Number> free(res_graph); |
|
692 |
|
693 // dfs.pushAndSetReached(s); |
|
694 // while (!dfs.finished()) { |
|
695 // ++dfs; |
|
696 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
697 // if (dfs.isBNodeNewlyReached()) { |
|
698 |
|
699 // typename EAugGraph::Node v=res_graph.aNode(dfs); |
|
700 // typename EAugGraph::Node w=res_graph.bNode(dfs); |
|
701 |
|
702 // pred.set(w, EAugOutEdgeIt(dfs)); |
|
703 // if (res_graph.valid(pred.get(v))) { |
|
704 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
|
705 // } else { |
|
706 // free.set(w, res_graph.free(dfs)); |
|
707 // } |
|
708 |
|
709 // if (w==t) { |
|
710 // __augment=true; |
|
711 // _augment=true; |
|
712 // break; |
|
713 // } |
|
714 // } else { |
|
715 // res_graph.erase(dfs); |
|
716 // } |
|
717 // } |
|
718 |
|
719 // } |
|
720 |
|
721 // if (__augment) { |
|
722 // typename EAugGraph::Node n=t; |
|
723 // Number augment_value=free.get(t); |
|
724 // while (res_graph.valid(pred.get(n))) { |
|
725 // EAugEdge e=pred.get(n); |
|
726 // res_graph.augment(e, augment_value); |
|
727 // n=res_graph.tail(e); |
|
728 // if (res_graph.free(e)==0) |
|
729 // res_graph.erase(e); |
|
730 // } |
|
731 // } |
|
732 |
|
733 // } |
|
734 |
|
735 // return _augment; |
|
736 // } |
|
737 |
645 |
738 void run() { |
646 void run() { |
739 //int num_of_augmentations=0; |
647 //int num_of_augmentations=0; |
740 while (augmentOnShortestPath()) { |
648 while (augmentOnShortestPath()) { |
741 //while (augmentOnBlockingFlow<MutableGraph>()) { |
649 //while (augmentOnBlockingFlow<MutableGraph>()) { |