marci@280: #ifndef EDMONDS_KARP_HH marci@280: #define EDMONDS_KARP_HH marci@280: marci@280: #include <algorithm> marci@280: #include <list> marci@280: #include <iterator> marci@280: marci@280: #include <bfs_iterator.hh> marci@280: //#include <time_measure.h> marci@280: marci@280: namespace hugo { marci@280: marci@280: template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> marci@280: class ResGraph { marci@280: public: marci@280: typedef typename Graph::NodeIt NodeIt; marci@280: typedef typename Graph::EachNodeIt EachNodeIt; marci@280: private: marci@280: typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@280: const Graph& G; marci@280: FlowMap& flow; marci@280: const CapacityMap& capacity; marci@280: public: marci@280: ResGraph(const Graph& _G, FlowMap& _flow, marci@280: const CapacityMap& _capacity) : marci@280: G(_G), flow(_flow), capacity(_capacity) { } marci@280: marci@280: class EdgeIt; marci@280: class OutEdgeIt; marci@280: friend class EdgeIt; marci@280: friend class OutEdgeIt; marci@280: marci@280: class EdgeIt { marci@280: friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; marci@280: protected: marci@280: const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG; marci@280: OldSymEdgeIt sym; marci@280: public: marci@280: EdgeIt() { } marci@280: //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } marci@280: Number free() const { marci@280: if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@280: return (resG->capacity.get(sym)-resG->flow.get(sym)); marci@280: } else { marci@280: return (resG->flow.get(sym)); marci@280: } marci@280: } marci@280: bool valid() const { return sym.valid(); } marci@280: void augment(Number a) const { marci@280: if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@280: resG->flow.set(sym, resG->flow.get(sym)+a); marci@280: //resG->flow[sym]+=a; marci@280: } else { marci@280: resG->flow.set(sym, resG->flow.get(sym)-a); marci@280: //resG->flow[sym]-=a; marci@280: } marci@280: } marci@280: }; marci@280: marci@280: class OutEdgeIt : public EdgeIt { marci@280: friend class ResGraph<Graph, Number, FlowMap, CapacityMap>; marci@280: public: marci@280: OutEdgeIt() { } marci@280: //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } marci@280: private: marci@280: OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { marci@280: resG=&_resG; marci@280: sym=resG->G.template first<OldSymEdgeIt>(v); marci@280: while( sym.valid() && !(free()>0) ) { ++sym; } marci@280: } marci@280: public: marci@280: OutEdgeIt& operator++() { marci@280: ++sym; marci@280: while( sym.valid() && !(free()>0) ) { ++sym; } marci@280: return *this; marci@280: } marci@280: }; marci@280: marci@280: void getFirst(OutEdgeIt& e, NodeIt v) const { marci@280: e=OutEdgeIt(*this, v); marci@280: } marci@280: void getFirst(EachNodeIt& v) const { G.getFirst(v); } marci@280: marci@280: template< typename It > marci@280: It first() const { marci@280: It e; marci@280: getFirst(e); marci@280: return e; marci@280: } marci@280: marci@280: template< typename It > marci@280: It first(NodeIt v) const { marci@280: It e; marci@280: getFirst(e, v); marci@280: return e; marci@280: } marci@280: marci@280: NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } marci@280: NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } marci@280: marci@280: NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } marci@280: NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } marci@280: marci@280: int id(NodeIt v) const { return G.id(v); } marci@280: marci@280: template <typename S> marci@280: class NodeMap { marci@280: typename Graph::NodeMap<S> node_map; marci@280: public: marci@280: NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } marci@280: NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } marci@280: void set(NodeIt nit, S a) { node_map.set(nit, a); } marci@280: S get(NodeIt nit) const { return node_map.get(nit); } marci@280: S& operator[](NodeIt nit) { return node_map[nit]; } marci@280: const S& operator[](NodeIt nit) const { return node_map[nit]; } marci@280: }; marci@280: marci@280: }; marci@280: marci@280: marci@280: template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> marci@280: class ResGraph2 { marci@280: public: marci@280: typedef typename Graph::NodeIt NodeIt; marci@280: typedef typename Graph::EachNodeIt EachNodeIt; marci@280: private: marci@280: //typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@280: typedef typename Graph::OutEdgeIt OldOutEdgeIt; marci@280: typedef typename Graph::InEdgeIt OldInEdgeIt; marci@280: marci@280: const Graph& G; marci@280: FlowMap& flow; marci@280: const CapacityMap& capacity; marci@280: public: marci@280: ResGraph2(const Graph& _G, FlowMap& _flow, marci@280: const CapacityMap& _capacity) : marci@280: G(_G), flow(_flow), capacity(_capacity) { } marci@280: marci@280: class EdgeIt; marci@280: class OutEdgeIt; marci@280: friend class EdgeIt; marci@280: friend class OutEdgeIt; marci@280: marci@280: class EdgeIt { marci@280: friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; marci@280: protected: marci@280: const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG; marci@280: //OldSymEdgeIt sym; marci@280: OldOutEdgeIt out; marci@280: OldInEdgeIt in; marci@280: bool out_or_in; //true, iff out marci@280: public: marci@280: EdgeIt() : out_or_in(true) { } marci@280: Number free() const { marci@280: if (out_or_in) { marci@280: return (resG->capacity.get(out)-resG->flow.get(out)); marci@280: } else { marci@280: return (resG->flow.get(in)); marci@280: } marci@280: } marci@280: bool valid() const { marci@280: return out_or_in && out.valid() || in.valid(); } marci@280: void augment(Number a) const { marci@280: if (out_or_in) { marci@280: resG->flow.set(out, resG->flow.get(out)+a); marci@280: } else { marci@280: resG->flow.set(in, resG->flow.get(in)-a); marci@280: } marci@280: } marci@280: }; marci@280: marci@280: class OutEdgeIt : public EdgeIt { marci@280: friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>; marci@280: public: marci@280: OutEdgeIt() { } marci@280: private: marci@280: OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { marci@280: resG=&_resG; marci@280: out=resG->G.template first<OldOutEdgeIt>(v); marci@280: while( out.valid() && !(free()>0) ) { ++out; } marci@280: if (!out.valid()) { marci@280: out_or_in=0; marci@280: in=resG->G.template first<OldInEdgeIt>(v); marci@280: while( in.valid() && !(free()>0) ) { ++in; } marci@280: } marci@280: } marci@280: public: marci@280: OutEdgeIt& operator++() { marci@280: if (out_or_in) { marci@280: NodeIt v=resG->G.aNode(out); marci@280: ++out; marci@280: while( out.valid() && !(free()>0) ) { ++out; } marci@280: if (!out.valid()) { marci@280: out_or_in=0; marci@280: in=resG->G.template first<OldInEdgeIt>(v); marci@280: while( in.valid() && !(free()>0) ) { ++in; } marci@280: } marci@280: } else { marci@280: ++in; marci@280: while( in.valid() && !(free()>0) ) { ++in; } marci@280: } marci@280: return *this; marci@280: } marci@280: }; marci@280: marci@280: void getFirst(OutEdgeIt& e, NodeIt v) const { marci@280: e=OutEdgeIt(*this, v); marci@280: } marci@280: void getFirst(EachNodeIt& v) const { G.getFirst(v); } marci@280: marci@280: template< typename It > marci@280: It first() const { marci@280: It e; marci@280: getFirst(e); marci@280: return e; marci@280: } marci@280: marci@280: template< typename It > marci@280: It first(NodeIt v) const { marci@280: It e; marci@280: getFirst(e, v); marci@280: return e; marci@280: } marci@280: marci@280: NodeIt tail(EdgeIt e) const { marci@280: return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@280: NodeIt head(EdgeIt e) const { marci@280: return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@280: marci@280: NodeIt aNode(OutEdgeIt e) const { marci@280: return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@280: NodeIt bNode(OutEdgeIt e) const { marci@280: return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@280: marci@280: int id(NodeIt v) const { return G.id(v); } marci@280: marci@280: template <typename S> marci@280: class NodeMap { marci@280: typename Graph::NodeMap<S> node_map; marci@280: public: marci@280: NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { } marci@280: NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { } marci@280: void set(NodeIt nit, S a) { node_map.set(nit, a); } marci@280: S get(NodeIt nit) const { return node_map.get(nit); } marci@280: }; marci@280: }; marci@280: marci@280: marci@280: template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> marci@280: class MaxFlow { marci@280: public: marci@280: typedef typename Graph::NodeIt NodeIt; marci@280: typedef typename Graph::EdgeIt EdgeIt; marci@280: typedef typename Graph::EachEdgeIt EachEdgeIt; marci@280: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@280: typedef typename Graph::InEdgeIt InEdgeIt; marci@280: marci@280: private: marci@280: const Graph* G; marci@280: NodeIt s; marci@280: NodeIt t; marci@280: FlowMap* flow; marci@280: const CapacityMap* capacity; marci@280: typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; marci@280: typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@280: typedef typename AugGraph::EdgeIt AugEdgeIt; marci@280: marci@280: //AugGraph res_graph; marci@280: //typedef typename AugGraph::NodeMap<bool> ReachedMap; marci@280: //typename AugGraph::NodeMap<AugEdgeIt> pred; marci@280: //typename AugGraph::NodeMap<Number> free; marci@280: public: marci@280: MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : marci@280: G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, marci@280: //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) marci@280: { } marci@280: bool augmentOnShortestPath() { marci@280: AugGraph res_graph(*G, *flow, *capacity); marci@280: bool _augment=false; marci@280: marci@280: typedef typename AugGraph::NodeMap<bool> ReachedMap; marci@280: BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); marci@280: res_bfs.pushAndSetReached(s); marci@280: marci@280: typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); marci@280: //filled up with invalid iterators marci@280: //pred.set(s, AugEdgeIt()); marci@280: marci@280: typename AugGraph::NodeMap<Number> free(res_graph); marci@280: marci@280: //searching for augmenting path marci@280: while ( !res_bfs.finished() ) { marci@280: AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); marci@280: if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { marci@280: NodeIt v=res_graph.tail(e); marci@280: NodeIt w=res_graph.head(e); marci@280: pred.set(w, e); marci@280: if (res_graph.valid(pred.get(v))) { marci@280: free.set(w, std::min(free.get(v), res_graph.free(e))); marci@280: } else { marci@280: free.set(w, res_graph.free(e)); marci@280: } marci@280: if (res_graph.head(e)==t) { _augment=true; break; } marci@280: } marci@280: marci@280: ++res_bfs; marci@280: } //end of searching augmenting path marci@280: marci@280: if (_augment) { marci@280: NodeIt n=t; marci@280: Number augment_value=free.get(t); marci@280: while (res_graph.valid(pred.get(n))) { marci@280: AugEdgeIt e=pred.get(n); marci@280: res_graph.augment(e, augment_value); marci@280: //e.augment(augment_value); marci@280: n=res_graph.tail(e); marci@280: } marci@280: } marci@280: marci@280: return _augment; marci@280: } marci@280: marci@280: template<typename MutableGraph> bool augmentOnBlockingFlow() { marci@280: bool _augment=false; marci@280: marci@280: AugGraph res_graph(*G, *flow, *capacity); marci@280: marci@280: typedef typename AugGraph::NodeMap<bool> ReachedMap; marci@280: BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@280: marci@280: bfs.pushAndSetReached(s); marci@280: typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's marci@280: while ( !bfs.finished() ) { marci@280: AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); marci@280: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@280: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@280: } marci@280: marci@280: ++bfs; marci@280: } //computing distances from s in the residual graph marci@280: marci@280: MutableGraph F; marci@280: typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph); marci@280: for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { marci@280: res_graph_to_F.set(n, F.addNode()); marci@280: } marci@280: marci@280: typename MutableGraph::NodeIt sF=res_graph_to_F.get(s); marci@280: typename MutableGraph::NodeIt tF=res_graph_to_F.get(t); marci@280: marci@280: typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F); marci@280: typename MutableGraph::EdgeMap<Number> residual_capacity(F); marci@280: marci@280: //Making F to the graph containing the edges of the residual graph marci@280: //which are in some shortest paths marci@280: for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) { marci@280: if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { marci@280: typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); marci@280: original_edge.update(); marci@280: original_edge.set(f, e); marci@280: residual_capacity.update(); marci@280: residual_capacity.set(f, res_graph.free(e)); marci@280: } marci@280: } marci@280: marci@280: bool __augment=true; marci@280: marci@280: while (__augment) { marci@280: __augment=false; marci@280: //computing blocking flow with dfs marci@280: typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; marci@280: DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); marci@280: typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators marci@280: typename MutableGraph::NodeMap<Number> free(F); marci@280: marci@280: dfs.pushAndSetReached(sF); marci@280: while (!dfs.finished()) { marci@280: ++dfs; marci@280: if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { marci@280: if (dfs.isBNodeNewlyReached()) { marci@280: // std::cout << "OutEdgeIt: " << dfs; marci@280: // std::cout << " aNode: " << F.aNode(dfs); marci@280: // std::cout << " bNode: " << F.bNode(dfs) << " "; marci@280: marci@280: typename MutableGraph::NodeIt v=F.aNode(dfs); marci@280: typename MutableGraph::NodeIt w=F.bNode(dfs); marci@280: pred.set(w, dfs); marci@280: if (F.valid(pred.get(v))) { marci@280: free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); marci@280: } else { marci@280: free.set(w, residual_capacity.get(dfs)); marci@280: } marci@280: if (w==tF) { marci@280: //std::cout << "AUGMENTATION"<<std::endl; marci@280: __augment=true; marci@280: _augment=true; marci@280: break; marci@280: } marci@280: marci@280: } else { marci@280: F.erase(typename MutableGraph::OutEdgeIt(dfs)); marci@280: } marci@280: } marci@280: } marci@280: marci@280: if (__augment) { marci@280: typename MutableGraph::NodeIt n=tF; marci@280: Number augment_value=free.get(tF); marci@280: while (F.valid(pred.get(n))) { marci@280: typename MutableGraph::EdgeIt e=pred.get(n); marci@280: res_graph.augment(original_edge.get(e), augment_value); marci@280: //original_edge.get(e).augment(augment_value); marci@280: n=F.tail(e); marci@280: if (residual_capacity.get(e)==augment_value) marci@280: F.erase(e); marci@280: else marci@280: residual_capacity.set(e, residual_capacity.get(e)-augment_value); marci@280: } marci@280: } marci@280: marci@280: } marci@280: marci@280: return _augment; marci@280: } marci@280: bool augmentOnBlockingFlow2() { marci@280: bool _augment=false; marci@280: marci@280: //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; marci@280: typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; marci@280: typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; marci@280: typedef typename EAugGraph::EdgeIt EAugEdgeIt; marci@280: marci@280: EAugGraph res_graph(*G, *flow, *capacity); marci@280: marci@280: //std::cout << "meg jo1" << std::endl; marci@280: marci@280: //typedef typename EAugGraph::NodeMap<bool> ReachedMap; marci@280: BfsIterator4< marci@280: ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, marci@280: ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, marci@280: ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); marci@280: marci@280: //std::cout << "meg jo2" << std::endl; marci@280: marci@280: bfs.pushAndSetReached(s); marci@280: //std::cout << "meg jo2.5" << std::endl; marci@280: marci@280: //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's marci@280: typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: marci@280: NodeMap<int>& dist=res_graph.dist; marci@280: //std::cout << "meg jo2.6" << std::endl; marci@280: marci@280: while ( !bfs.finished() ) { marci@280: ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; marci@280: // EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); marci@280: //if (res_graph.valid(e)) { marci@280: // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl; marci@280: //} marci@280: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@280: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@280: } marci@280: marci@280: ++bfs; marci@280: } //computing distances from s in the residual graph marci@280: marci@280: marci@280: //std::cout << "meg jo3" << std::endl; marci@280: marci@280: // typedef typename EAugGraph::EachNodeIt EAugEachNodeIt; marci@280: // for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { marci@280: // std::cout << "dist: " << dist.get(n) << std::endl; marci@280: // } marci@280: marci@280: bool __augment=true; marci@280: marci@280: while (__augment) { marci@280: // std::cout << "new iteration"<< std::endl; marci@280: marci@280: __augment=false; marci@280: //computing blocking flow with dfs marci@280: typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; marci@280: DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > marci@280: dfs(res_graph); marci@280: typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators marci@280: typename EAugGraph::NodeMap<Number> free(res_graph); marci@280: marci@280: dfs.pushAndSetReached(s); marci@280: while (!dfs.finished()) { marci@280: ++dfs; marci@280: if (res_graph.valid(EAugOutEdgeIt(dfs))) { marci@280: if (dfs.isBNodeNewlyReached()) { marci@280: // std::cout << "OutEdgeIt: " << dfs; marci@280: // std::cout << " aNode: " << res_graph.aNode(dfs); marci@280: // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); marci@280: // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; marci@280: marci@280: typename EAugGraph::NodeIt v=res_graph.aNode(dfs); marci@280: typename EAugGraph::NodeIt w=res_graph.bNode(dfs); marci@280: marci@280: pred.set(w, EAugOutEdgeIt(dfs)); marci@280: marci@280: //std::cout << EAugOutEdgeIt(dfs).free() << std::endl; marci@280: if (res_graph.valid(pred.get(v))) { marci@280: free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs)))); marci@280: } else { marci@280: free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); marci@280: } marci@280: marci@280: if (w==t) { marci@280: // std::cout << "t is reached, AUGMENTATION"<<std::endl; marci@280: __augment=true; marci@280: _augment=true; marci@280: break; marci@280: } marci@280: } else { marci@280: // std::cout << "<<DELETE "; marci@280: // std::cout << " aNode: " << res_graph.aNode(dfs); marci@280: // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); marci@280: // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; marci@280: // std::cout << "DELETE>> "; marci@280: marci@280: res_graph.erase(dfs); marci@280: } marci@280: } marci@280: marci@280: } marci@280: marci@280: if (__augment) { marci@280: typename EAugGraph::NodeIt n=t; marci@280: Number augment_value=free.get(t); marci@280: // std::cout << "av:" << augment_value << std::endl; marci@280: while (res_graph.valid(pred.get(n))) { marci@280: EAugEdgeIt e=pred.get(n); marci@280: res_graph.augment(e, augment_value); marci@280: //e.augment(augment_value); marci@280: n=res_graph.tail(e); marci@280: if (res_graph.free(e)==0) marci@280: res_graph.erase(e); marci@280: } marci@280: } marci@280: marci@280: } marci@280: marci@280: return _augment; marci@280: } marci@280: void run() { marci@280: //int num_of_augmentations=0; marci@280: while (augmentOnShortestPath()) { marci@280: //while (augmentOnBlockingFlow<MutableGraph>()) { marci@280: //std::cout << ++num_of_augmentations << " "; marci@280: //std::cout<<std::endl; marci@280: } marci@280: } marci@280: template<typename MutableGraph> void run() { marci@280: //int num_of_augmentations=0; marci@280: //while (augmentOnShortestPath()) { marci@280: while (augmentOnBlockingFlow<MutableGraph>()) { marci@280: //std::cout << ++num_of_augmentations << " "; marci@280: //std::cout<<std::endl; marci@280: } marci@280: } marci@280: Number flowValue() { marci@280: Number a=0; marci@280: OutEdgeIt e; marci@280: for(G->getFirst(e, s); G->valid(e); G->next(e)) { marci@280: a+=flow->get(e); marci@280: } marci@280: return a; marci@280: } marci@280: }; marci@280: marci@280: marci@280: // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> marci@280: // class MaxFlow2 { marci@280: // public: marci@280: // typedef typename Graph::NodeIt NodeIt; marci@280: // typedef typename Graph::EdgeIt EdgeIt; marci@280: // typedef typename Graph::EachEdgeIt EachEdgeIt; marci@280: // typedef typename Graph::OutEdgeIt OutEdgeIt; marci@280: // typedef typename Graph::InEdgeIt InEdgeIt; marci@280: // private: marci@280: // const Graph& G; marci@280: // std::list<NodeIt>& S; marci@280: // std::list<NodeIt>& T; marci@280: // FlowMap& flow; marci@280: // const CapacityMap& capacity; marci@280: // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; marci@280: // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@280: // typedef typename AugGraph::EdgeIt AugEdgeIt; marci@280: // typename Graph::NodeMap<bool> SMap; marci@280: // typename Graph::NodeMap<bool> TMap; marci@280: // public: marci@280: // MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { marci@280: // for(typename std::list<NodeIt>::const_iterator i=S.begin(); marci@280: // i!=S.end(); ++i) { marci@280: // SMap.set(*i, true); marci@280: // } marci@280: // for (typename std::list<NodeIt>::const_iterator i=T.begin(); marci@280: // i!=T.end(); ++i) { marci@280: // TMap.set(*i, true); marci@280: // } marci@280: // } marci@280: // bool augment() { marci@280: // AugGraph res_graph(G, flow, capacity); marci@280: // bool _augment=false; marci@280: // NodeIt reached_t_node; marci@280: marci@280: // typedef typename AugGraph::NodeMap<bool> ReachedMap; marci@280: // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); marci@280: // for(typename std::list<NodeIt>::const_iterator i=S.begin(); marci@280: // i!=S.end(); ++i) { marci@280: // res_bfs.pushAndSetReached(*i); marci@280: // } marci@280: // //res_bfs.pushAndSetReached(s); marci@280: marci@280: // typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); marci@280: // //filled up with invalid iterators marci@280: marci@280: // typename AugGraph::NodeMap<Number> free(res_graph); marci@280: marci@280: // //searching for augmenting path marci@280: // while ( !res_bfs.finished() ) { marci@280: // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); marci@280: // if (e.valid() && res_bfs.isBNodeNewlyReached()) { marci@280: // NodeIt v=res_graph.tail(e); marci@280: // NodeIt w=res_graph.head(e); marci@280: // pred.set(w, e); marci@280: // if (pred.get(v).valid()) { marci@280: // free.set(w, std::min(free.get(v), e.free())); marci@280: // } else { marci@280: // free.set(w, e.free()); marci@280: // } marci@280: // if (TMap.get(res_graph.head(e))) { marci@280: // _augment=true; marci@280: // reached_t_node=res_graph.head(e); marci@280: // break; marci@280: // } marci@280: // } marci@280: marci@280: // ++res_bfs; marci@280: // } //end of searching augmenting path marci@280: marci@280: // if (_augment) { marci@280: // NodeIt n=reached_t_node; marci@280: // Number augment_value=free.get(reached_t_node); marci@280: // while (pred.get(n).valid()) { marci@280: // AugEdgeIt e=pred.get(n); marci@280: // e.augment(augment_value); marci@280: // n=res_graph.tail(e); marci@280: // } marci@280: // } marci@280: marci@280: // return _augment; marci@280: // } marci@280: // void run() { marci@280: // while (augment()) { } marci@280: // } marci@280: // Number flowValue() { marci@280: // Number a=0; marci@280: // for(typename std::list<NodeIt>::const_iterator i=S.begin(); marci@280: // i!=S.end(); ++i) { marci@280: // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) { marci@280: // a+=flow.get(e); marci@280: // } marci@280: // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) { marci@280: // a-=flow.get(e); marci@280: // } marci@280: // } marci@280: // return a; marci@280: // } marci@280: // }; marci@280: marci@280: marci@280: marci@280: } // namespace hugo marci@280: marci@280: #endif //EDMONDS_KARP_HH