marci@174: // -*- c++ -*- marci@174: #ifndef EDMONDS_KARP_H marci@174: #define EDMONDS_KARP_H marci@174: marci@174: #include marci@174: #include marci@174: #include marci@174: marci@174: #include marci@174: #include marci@174: marci@174: namespace hugo { marci@174: marci@174: template marci@174: class ResGraph { marci@174: public: marci@174: typedef typename Graph::Node Node; marci@174: typedef typename Graph::NodeIt NodeIt; marci@174: private: marci@174: typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@174: const Graph& G; marci@174: FlowMap& flow; marci@174: const CapacityMap& capacity; marci@174: public: marci@174: ResGraph(const Graph& _G, FlowMap& _flow, marci@174: const CapacityMap& _capacity) : marci@174: G(_G), flow(_flow), capacity(_capacity) { } marci@174: marci@174: class Edge; marci@174: class OutEdgeIt; marci@174: friend class Edge; marci@174: friend class OutEdgeIt; marci@174: marci@174: class Edge { marci@174: friend class ResGraph; marci@174: protected: marci@174: const ResGraph* resG; marci@174: OldSymEdgeIt sym; marci@174: public: marci@174: Edge() { } marci@174: //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } marci@174: Number free() const { marci@174: if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@174: return (resG->capacity.get(sym)-resG->flow.get(sym)); marci@174: } else { marci@174: return (resG->flow.get(sym)); marci@174: } marci@174: } marci@174: bool valid() const { return sym.valid(); } marci@174: void augment(Number a) const { marci@174: if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@174: resG->flow.set(sym, resG->flow.get(sym)+a); marci@174: //resG->flow[sym]+=a; marci@174: } else { marci@174: resG->flow.set(sym, resG->flow.get(sym)-a); marci@174: //resG->flow[sym]-=a; marci@174: } marci@174: } marci@174: }; marci@174: marci@174: class OutEdgeIt : public Edge { marci@174: friend class ResGraph; marci@174: public: marci@174: OutEdgeIt() { } marci@174: //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } marci@174: private: marci@174: OutEdgeIt(const ResGraph& _resG, Node v) { marci@174: resG=&_resG; marci@174: sym=resG->G.template first(v); marci@174: while( sym.valid() && !(free()>0) ) { ++sym; } marci@174: } marci@174: public: marci@174: OutEdgeIt& operator++() { marci@174: ++sym; marci@174: while( sym.valid() && !(free()>0) ) { ++sym; } marci@174: return *this; marci@174: } marci@174: }; marci@174: marci@174: void /*getF*/first(OutEdgeIt& e, Node v) const { marci@174: e=OutEdgeIt(*this, v); marci@174: } marci@174: void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } marci@174: marci@174: template< typename It > marci@174: It first() const { marci@174: It e; marci@174: /*getF*/first(e); marci@174: return e; marci@174: } marci@174: marci@174: template< typename It > marci@174: It first(Node v) const { marci@174: It e; marci@174: /*getF*/first(e, v); marci@174: return e; marci@174: } marci@174: marci@174: Node tail(Edge e) const { return G.aNode(e.sym); } marci@174: Node head(Edge e) const { return G.bNode(e.sym); } marci@174: marci@174: Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } marci@174: Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } marci@174: marci@174: int id(Node v) const { return G.id(v); } marci@174: marci@174: template marci@174: class NodeMap { marci@174: typename Graph::NodeMap node_map; marci@174: public: marci@174: NodeMap(const ResGraph& _G) : node_map(_G.G) { } marci@174: NodeMap(const ResGraph& _G, S a) : node_map(_G.G, a) { } marci@174: void set(Node nit, S a) { node_map.set(nit, a); } marci@174: S get(Node nit) const { return node_map.get(nit); } marci@174: S& operator[](Node nit) { return node_map[nit]; } marci@174: const S& operator[](Node nit) const { return node_map[nit]; } marci@174: }; marci@174: marci@174: }; marci@174: marci@174: marci@174: template marci@174: class ResGraph2 { marci@174: public: marci@174: typedef typename Graph::Node Node; marci@174: typedef typename Graph::NodeIt NodeIt; marci@174: private: marci@174: //typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@174: typedef typename Graph::OutEdgeIt OldOutEdgeIt; marci@174: typedef typename Graph::InEdgeIt OldInEdgeIt; marci@174: marci@174: const Graph& G; marci@174: FlowMap& flow; marci@174: const CapacityMap& capacity; marci@174: public: marci@174: ResGraph2(const Graph& _G, FlowMap& _flow, marci@174: const CapacityMap& _capacity) : marci@174: G(_G), flow(_flow), capacity(_capacity) { } marci@174: marci@174: class Edge; marci@174: class OutEdgeIt; marci@174: friend class Edge; marci@174: friend class OutEdgeIt; marci@174: marci@174: class Edge { marci@174: friend class ResGraph2; marci@174: protected: marci@174: const ResGraph2* resG; marci@174: //OldSymEdgeIt sym; marci@174: OldOutEdgeIt out; marci@174: OldInEdgeIt in; marci@174: bool out_or_in; //true, iff out marci@174: public: marci@174: Edge() : out_or_in(true) { } marci@174: Number free() const { marci@174: if (out_or_in) { marci@174: return (resG->capacity.get(out)-resG->flow.get(out)); marci@174: } else { marci@174: return (resG->flow.get(in)); marci@174: } marci@174: } marci@174: bool valid() const { marci@174: return out_or_in && out.valid() || in.valid(); } marci@174: void augment(Number a) const { marci@174: if (out_or_in) { marci@174: resG->flow.set(out, resG->flow.get(out)+a); marci@174: } else { marci@174: resG->flow.set(in, resG->flow.get(in)-a); marci@174: } marci@174: } marci@174: }; marci@174: marci@174: class OutEdgeIt : public Edge { marci@174: friend class ResGraph2; marci@174: public: marci@174: OutEdgeIt() { } marci@174: private: marci@174: OutEdgeIt(const ResGraph2& _resG, Node v) { marci@174: resG=&_resG; marci@174: out=resG->G.template first(v); marci@174: while( out.valid() && !(free()>0) ) { ++out; } marci@174: if (!out.valid()) { marci@174: out_or_in=0; marci@174: in=resG->G.template first(v); marci@174: while( in.valid() && !(free()>0) ) { ++in; } marci@174: } marci@174: } marci@174: public: marci@174: OutEdgeIt& operator++() { marci@174: if (out_or_in) { marci@174: Node v=resG->G.aNode(out); marci@174: ++out; marci@174: while( out.valid() && !(free()>0) ) { ++out; } marci@174: if (!out.valid()) { marci@174: out_or_in=0; marci@174: in=resG->G.template first(v); marci@174: while( in.valid() && !(free()>0) ) { ++in; } marci@174: } marci@174: } else { marci@174: ++in; marci@174: while( in.valid() && !(free()>0) ) { ++in; } marci@174: } marci@174: return *this; marci@174: } marci@174: }; marci@174: marci@174: void /*getF*/first(OutEdgeIt& e, Node v) const { marci@174: e=OutEdgeIt(*this, v); marci@174: } marci@174: void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } marci@174: marci@174: template< typename It > marci@174: It first() const { marci@174: It e; marci@174: /*getF*/first(e); marci@174: return e; marci@174: } marci@174: marci@174: template< typename It > marci@174: It first(Node v) const { marci@174: It e; marci@174: /*getF*/first(e, v); marci@174: return e; marci@174: } marci@174: marci@174: Node tail(Edge e) const { marci@174: return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@174: Node head(Edge e) const { marci@174: return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@174: marci@174: Node aNode(OutEdgeIt e) const { marci@174: return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@174: Node bNode(OutEdgeIt e) const { marci@174: return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@174: marci@174: int id(Node v) const { return G.id(v); } marci@174: marci@174: template marci@174: class NodeMap { marci@174: typename Graph::NodeMap node_map; marci@174: public: marci@174: NodeMap(const ResGraph2& _G) : node_map(_G.G) { } marci@174: NodeMap(const ResGraph2& _G, S a) : node_map(_G.G, a) { } marci@174: void set(Node nit, S a) { node_map.set(nit, a); } marci@174: S get(Node nit) const { return node_map.get(nit); } marci@174: }; marci@174: }; marci@174: marci@174: marci@174: template marci@174: class MaxFlow { marci@174: public: marci@174: typedef typename Graph::Node Node; marci@174: typedef typename Graph::Edge Edge; marci@174: typedef typename Graph::EdgeIt EdgeIt; marci@174: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@174: typedef typename Graph::InEdgeIt InEdgeIt; marci@174: marci@174: private: marci@174: const Graph* G; marci@174: Node s; marci@174: Node t; marci@174: FlowMap* flow; marci@174: const CapacityMap* capacity; marci@174: typedef ResGraphWrapper AugGraph; marci@174: typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@174: typedef typename AugGraph::Edge AugEdge; marci@174: marci@174: public: marci@174: MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : marci@191: G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } marci@174: bool augmentOnShortestPath() { marci@174: AugGraph res_graph(*G, *flow, *capacity); marci@174: bool _augment=false; marci@174: marci@174: typedef typename AugGraph::NodeMap ReachedMap; marci@174: BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); marci@174: res_bfs.pushAndSetReached(s); marci@174: marci@174: typename AugGraph::NodeMap pred(res_graph); marci@174: pred.set(s, AugEdge(INVALID)); marci@174: marci@174: typename AugGraph::NodeMap free(res_graph); marci@174: marci@174: //searching for augmenting path marci@174: while ( !res_bfs.finished() ) { marci@191: AugOutEdgeIt e=res_bfs; marci@174: if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { marci@174: Node v=res_graph.tail(e); marci@174: Node w=res_graph.head(e); marci@174: pred.set(w, e); marci@174: if (res_graph.valid(pred.get(v))) { marci@174: free.set(w, std::min(free.get(v), res_graph.free(e))); marci@174: } else { marci@174: free.set(w, res_graph.free(e)); marci@174: } marci@174: if (res_graph.head(e)==t) { _augment=true; break; } marci@174: } marci@174: marci@174: ++res_bfs; marci@174: } //end of searching augmenting path marci@174: marci@174: if (_augment) { marci@174: Node n=t; marci@174: Number augment_value=free.get(t); marci@174: while (res_graph.valid(pred.get(n))) { marci@174: AugEdge e=pred.get(n); marci@174: res_graph.augment(e, augment_value); marci@174: n=res_graph.tail(e); marci@174: } marci@174: } marci@174: marci@174: return _augment; marci@174: } marci@174: marci@191: template bool augmentOnBlockingFlow() { marci@174: bool _augment=false; marci@174: marci@174: AugGraph res_graph(*G, *flow, *capacity); marci@174: marci@174: typedef typename AugGraph::NodeMap ReachedMap; marci@174: BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@174: marci@174: bfs.pushAndSetReached(s); marci@174: typename AugGraph::NodeMap dist(res_graph); //filled up with 0's marci@174: while ( !bfs.finished() ) { marci@191: AugOutEdgeIt e=bfs; marci@174: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@174: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@174: } marci@174: marci@174: ++bfs; marci@174: } //computing distances from s in the residual graph marci@174: marci@174: MutableGraph F; marci@174: typename AugGraph::NodeMap marci@174: res_graph_to_F(res_graph); marci@174: for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { marci@174: res_graph_to_F.set(n, F.addNode()); marci@174: } marci@174: marci@174: typename MutableGraph::Node sF=res_graph_to_F.get(s); marci@174: typename MutableGraph::Node tF=res_graph_to_F.get(t); marci@174: marci@174: typename MutableGraph::EdgeMap original_edge(F); marci@174: typename MutableGraph::EdgeMap residual_capacity(F); marci@174: marci@174: //Making F to the graph containing the edges of the residual graph marci@174: //which are in some shortest paths marci@174: for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { marci@174: if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { marci@174: typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); marci@174: original_edge.update(); marci@174: original_edge.set(f, e); marci@174: residual_capacity.update(); marci@174: residual_capacity.set(f, res_graph.free(e)); marci@174: } marci@174: } marci@174: marci@174: bool __augment=true; marci@174: marci@174: while (__augment) { marci@174: __augment=false; marci@174: //computing blocking flow with dfs marci@174: typedef typename MutableGraph::NodeMap BlockingReachedMap; marci@174: DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); marci@174: typename MutableGraph::NodeMap pred(F); marci@174: pred.set(sF, typename MutableGraph::Edge(INVALID)); marci@174: //invalid iterators for sources marci@174: marci@174: typename MutableGraph::NodeMap free(F); marci@174: marci@174: dfs.pushAndSetReached(sF); marci@174: while (!dfs.finished()) { marci@174: ++dfs; marci@174: if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { marci@174: if (dfs.isBNodeNewlyReached()) { marci@174: typename MutableGraph::Node v=F.aNode(dfs); marci@174: typename MutableGraph::Node w=F.bNode(dfs); marci@174: pred.set(w, dfs); marci@174: if (F.valid(pred.get(v))) { marci@174: free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); marci@174: } else { marci@174: free.set(w, residual_capacity.get(dfs)); marci@174: } marci@174: if (w==tF) { marci@174: __augment=true; marci@174: _augment=true; marci@174: break; marci@174: } marci@174: marci@174: } else { marci@174: F.erase(typename MutableGraph::OutEdgeIt(dfs)); marci@174: } marci@174: } marci@174: } marci@174: marci@174: if (__augment) { marci@174: typename MutableGraph::Node n=tF; marci@174: Number augment_value=free.get(tF); marci@174: while (F.valid(pred.get(n))) { marci@174: typename MutableGraph::Edge e=pred.get(n); marci@174: res_graph.augment(original_edge.get(e), augment_value); marci@174: n=F.tail(e); marci@174: if (residual_capacity.get(e)==augment_value) marci@174: F.erase(e); marci@174: else marci@174: residual_capacity.set(e, residual_capacity.get(e)-augment_value); marci@174: } marci@174: } marci@174: marci@174: } marci@174: marci@174: return _augment; marci@174: } marci@206: template bool augmentOnBlockingFlow1() { marci@206: bool _augment=false; marci@206: marci@206: AugGraph res_graph(*G, *flow, *capacity); marci@206: marci@206: //bfs for distances on the residual graph marci@206: typedef typename AugGraph::NodeMap ReachedMap; marci@206: BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@206: bfs.pushAndSetReached(s); marci@206: typename AugGraph::NodeMap dist(res_graph); //filled up with 0's marci@206: marci@206: //F will contain the physical copy of the residual graph marci@206: //with the set of edges which areon shortest paths marci@206: MutableGraph F; marci@206: typename AugGraph::NodeMap marci@206: res_graph_to_F(res_graph); marci@206: for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { marci@206: res_graph_to_F.set(n, F.addNode()); marci@206: } marci@206: typename MutableGraph::Node sF=res_graph_to_F.get(s); marci@206: typename MutableGraph::Node tF=res_graph_to_F.get(t); marci@206: typename MutableGraph::EdgeMap original_edge(F); marci@206: typename MutableGraph::EdgeMap residual_capacity(F); marci@206: marci@206: while ( !bfs.finished() ) { marci@206: AugOutEdgeIt e=bfs; marci@206: if (res_graph.valid(e)) { marci@206: if (bfs.isBNodeNewlyReached()) { marci@206: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@206: typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); marci@206: original_edge.update(); marci@206: original_edge.set(f, e); marci@206: residual_capacity.update(); marci@206: residual_capacity.set(f, res_graph.free(e)); marci@206: } else { marci@206: if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { marci@206: typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); marci@206: original_edge.update(); marci@206: original_edge.set(f, e); marci@206: residual_capacity.update(); marci@206: residual_capacity.set(f, res_graph.free(e)); marci@206: } marci@206: } marci@206: } marci@206: ++bfs; marci@206: } //computing distances from s in the residual graph marci@206: marci@206: bool __augment=true; marci@206: marci@206: while (__augment) { marci@206: __augment=false; marci@206: //computing blocking flow with dfs marci@206: typedef typename MutableGraph::NodeMap BlockingReachedMap; marci@206: DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); marci@206: typename MutableGraph::NodeMap pred(F); marci@206: pred.set(sF, typename MutableGraph::Edge(INVALID)); marci@206: //invalid iterators for sources marci@206: marci@206: typename MutableGraph::NodeMap free(F); marci@206: marci@206: dfs.pushAndSetReached(sF); marci@206: while (!dfs.finished()) { marci@206: ++dfs; marci@206: if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { marci@206: if (dfs.isBNodeNewlyReached()) { marci@206: typename MutableGraph::Node v=F.aNode(dfs); marci@206: typename MutableGraph::Node w=F.bNode(dfs); marci@206: pred.set(w, dfs); marci@206: if (F.valid(pred.get(v))) { marci@206: free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); marci@206: } else { marci@206: free.set(w, residual_capacity.get(dfs)); marci@206: } marci@206: if (w==tF) { marci@206: __augment=true; marci@206: _augment=true; marci@206: break; marci@206: } marci@206: marci@206: } else { marci@206: F.erase(typename MutableGraph::OutEdgeIt(dfs)); marci@206: } marci@206: } marci@206: } marci@206: marci@206: if (__augment) { marci@206: typename MutableGraph::Node n=tF; marci@206: Number augment_value=free.get(tF); marci@206: while (F.valid(pred.get(n))) { marci@206: typename MutableGraph::Edge e=pred.get(n); marci@206: res_graph.augment(original_edge.get(e), augment_value); marci@206: n=F.tail(e); marci@206: if (residual_capacity.get(e)==augment_value) marci@206: F.erase(e); marci@206: else marci@206: residual_capacity.set(e, residual_capacity.get(e)-augment_value); marci@206: } marci@206: } marci@206: marci@206: } marci@206: marci@206: return _augment; marci@206: } marci@174: bool augmentOnBlockingFlow2() { marci@174: bool _augment=false; marci@174: marci@174: //typedef ErasingResGraphWrapper EAugGraph; marci@174: typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; marci@174: typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; marci@174: typedef typename EAugGraph::Edge EAugEdge; marci@174: marci@174: EAugGraph res_graph(*G, *flow, *capacity); marci@174: marci@174: //typedef typename EAugGraph::NodeMap ReachedMap; marci@174: BfsIterator4< marci@174: ErasingResGraphWrapper, marci@175: typename ErasingResGraphWrapper::OutEdgeIt, marci@174: ErasingResGraphWrapper::NodeMap > bfs(res_graph); marci@174: marci@191: bfs.pushAndSetReached(s); marci@174: marci@174: typename ErasingResGraphWrapper:: marci@174: NodeMap& dist=res_graph.dist; marci@174: marci@174: while ( !bfs.finished() ) { marci@175: typename ErasingResGraphWrapper::OutEdgeIt e=bfs; marci@174: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@174: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@174: } marci@174: ++bfs; marci@174: } //computing distances from s in the residual graph marci@174: marci@174: bool __augment=true; marci@174: marci@174: while (__augment) { marci@174: marci@174: __augment=false; marci@174: //computing blocking flow with dfs marci@174: typedef typename EAugGraph::NodeMap BlockingReachedMap; marci@174: DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > marci@174: dfs(res_graph); marci@174: typename EAugGraph::NodeMap pred(res_graph); marci@174: pred.set(s, EAugEdge(INVALID)); marci@174: //invalid iterators for sources marci@174: marci@174: typename EAugGraph::NodeMap free(res_graph); marci@174: marci@174: dfs.pushAndSetReached(s); marci@174: while (!dfs.finished()) { marci@174: ++dfs; marci@174: if (res_graph.valid(EAugOutEdgeIt(dfs))) { marci@174: if (dfs.isBNodeNewlyReached()) { marci@174: marci@174: typename EAugGraph::Node v=res_graph.aNode(dfs); marci@174: typename EAugGraph::Node w=res_graph.bNode(dfs); marci@174: marci@174: pred.set(w, EAugOutEdgeIt(dfs)); marci@174: if (res_graph.valid(pred.get(v))) { marci@191: free.set(w, std::min(free.get(v), res_graph.free(dfs))); marci@174: } else { marci@191: free.set(w, res_graph.free(dfs)); marci@174: } marci@174: marci@174: if (w==t) { marci@174: __augment=true; marci@174: _augment=true; marci@174: break; marci@174: } marci@174: } else { marci@174: res_graph.erase(dfs); marci@174: } marci@174: } marci@174: marci@174: } marci@174: marci@174: if (__augment) { marci@174: typename EAugGraph::Node n=t; marci@174: Number augment_value=free.get(t); marci@174: while (res_graph.valid(pred.get(n))) { marci@174: EAugEdge e=pred.get(n); marci@174: res_graph.augment(e, augment_value); marci@174: n=res_graph.tail(e); marci@174: if (res_graph.free(e)==0) marci@174: res_graph.erase(e); marci@174: } marci@174: } marci@174: marci@174: } marci@174: marci@174: return _augment; marci@174: } marci@174: void run() { marci@174: //int num_of_augmentations=0; marci@174: while (augmentOnShortestPath()) { marci@174: //while (augmentOnBlockingFlow()) { marci@174: //std::cout << ++num_of_augmentations << " "; marci@174: //std::cout< void run() { marci@174: //int num_of_augmentations=0; marci@174: //while (augmentOnShortestPath()) { marci@174: while (augmentOnBlockingFlow()) { marci@174: //std::cout << ++num_of_augmentations << " "; marci@174: //std::cout</*getF*/first(e, s); G->valid(e); G->next(e)) { marci@174: a+=flow->get(e); marci@174: } marci@174: return a; marci@174: } marci@174: }; marci@174: marci@193: marci@193: template marci@193: class MaxMatching { marci@193: public: marci@193: typedef typename Graph::Node Node; marci@194: typedef typename Graph::NodeIt NodeIt; marci@193: typedef typename Graph::Edge Edge; marci@193: typedef typename Graph::EdgeIt EdgeIt; marci@193: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@193: typedef typename Graph::InEdgeIt InEdgeIt; marci@193: marci@193: typedef typename Graph::NodeMap SMap; marci@193: typedef typename Graph::NodeMap TMap; marci@193: private: marci@193: const Graph* G; marci@193: SMap* S; marci@193: TMap* T; marci@193: //Node s; marci@193: //Node t; marci@193: FlowMap* flow; marci@193: const CapacityMap* capacity; marci@193: typedef ResGraphWrapper AugGraph; marci@193: typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@193: typedef typename AugGraph::Edge AugEdge; marci@198: typename Graph::NodeMap used; //0 marci@193: marci@193: public: marci@193: MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : marci@198: G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } marci@193: bool augmentOnShortestPath() { marci@193: AugGraph res_graph(*G, *flow, *capacity); marci@193: bool _augment=false; marci@193: marci@193: typedef typename AugGraph::NodeMap ReachedMap; marci@193: BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); marci@193: typename AugGraph::NodeMap pred(res_graph); marci@193: for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@198: if ((S->get(s)) && (used.get(s)<1) ) { marci@198: //Number u=0; marci@198: //for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@198: //u+=flow->get(e); marci@198: //if (u<1) { marci@196: res_bfs.pushAndSetReached(s); marci@196: pred.set(s, AugEdge(INVALID)); marci@198: //} marci@193: } marci@193: } marci@193: marci@193: typename AugGraph::NodeMap free(res_graph); marci@193: marci@193: Node n; marci@193: //searching for augmenting path marci@193: while ( !res_bfs.finished() ) { marci@193: AugOutEdgeIt e=res_bfs; marci@193: if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { marci@193: Node v=res_graph.tail(e); marci@193: Node w=res_graph.head(e); marci@193: pred.set(w, e); marci@193: if (res_graph.valid(pred.get(v))) { marci@193: free.set(w, std::min(free.get(v), res_graph.free(e))); marci@193: } else { marci@193: free.set(w, res_graph.free(e)); marci@193: } marci@197: n=res_graph.head(e); marci@198: if (T->get(n) && (used.get(n)<1) ) { marci@198: //Number u=0; marci@198: //for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) marci@198: //u+=flow->get(f); marci@198: //if (u<1) { marci@197: _augment=true; marci@197: break; marci@198: //} marci@193: } marci@193: } marci@193: marci@193: ++res_bfs; marci@193: } //end of searching augmenting path marci@193: marci@193: if (_augment) { marci@193: //Node n=t; marci@198: used.set(n, 1); //mind2 vegen jav marci@194: Number augment_value=free.get(n); marci@193: while (res_graph.valid(pred.get(n))) { marci@193: AugEdge e=pred.get(n); marci@193: res_graph.augment(e, augment_value); marci@193: n=res_graph.tail(e); marci@193: } marci@198: used.set(n, 1); //mind2 vegen jav marci@193: } marci@193: marci@193: return _augment; marci@193: } marci@193: marci@193: // template bool augmentOnBlockingFlow() { marci@193: // bool _augment=false; marci@193: marci@193: // AugGraph res_graph(*G, *flow, *capacity); marci@193: marci@193: // typedef typename AugGraph::NodeMap ReachedMap; marci@193: // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@193: marci@197: marci@197: marci@197: marci@197: marci@197: // //typename AugGraph::NodeMap pred(res_graph); marci@197: // for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@197: // if (S->get(s)) { marci@197: // Number u=0; marci@197: // for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@197: // u+=flow->get(e); marci@197: // if (u<1) { marci@197: // res_bfs.pushAndSetReached(s); marci@197: // //pred.set(s, AugEdge(INVALID)); marci@197: // } marci@197: // } marci@197: // } marci@197: marci@197: marci@197: marci@197: marci@197: // //bfs.pushAndSetReached(s); marci@193: // typename AugGraph::NodeMap dist(res_graph); //filled up with 0's marci@193: // while ( !bfs.finished() ) { marci@193: // AugOutEdgeIt e=bfs; marci@193: // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@193: // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@193: // } marci@193: marci@193: // ++bfs; marci@193: // } //computing distances from s in the residual graph marci@193: marci@193: // MutableGraph F; marci@193: // typename AugGraph::NodeMap marci@193: // res_graph_to_F(res_graph); marci@193: // for(typename AugGraph::NodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { marci@193: // res_graph_to_F.set(n, F.addNode()); marci@193: // } marci@193: marci@193: // typename MutableGraph::Node sF=res_graph_to_F.get(s); marci@193: // typename MutableGraph::Node tF=res_graph_to_F.get(t); marci@193: marci@193: // typename MutableGraph::EdgeMap original_edge(F); marci@193: // typename MutableGraph::EdgeMap residual_capacity(F); marci@193: marci@193: // //Making F to the graph containing the edges of the residual graph marci@193: // //which are in some shortest paths marci@193: // for(typename AugGraph::EdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { marci@193: // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { marci@193: // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); marci@193: // original_edge.update(); marci@193: // original_edge.set(f, e); marci@193: // residual_capacity.update(); marci@193: // residual_capacity.set(f, res_graph.free(e)); marci@193: // } marci@193: // } marci@193: marci@193: // bool __augment=true; marci@193: marci@193: // while (__augment) { marci@193: // __augment=false; marci@193: // //computing blocking flow with dfs marci@193: // typedef typename MutableGraph::NodeMap BlockingReachedMap; marci@193: // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); marci@193: // typename MutableGraph::NodeMap pred(F); marci@193: // pred.set(sF, typename MutableGraph::Edge(INVALID)); marci@193: // //invalid iterators for sources marci@193: marci@193: // typename MutableGraph::NodeMap free(F); marci@193: marci@193: // dfs.pushAndSetReached(sF); marci@193: // while (!dfs.finished()) { marci@193: // ++dfs; marci@193: // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { marci@193: // if (dfs.isBNodeNewlyReached()) { marci@193: // typename MutableGraph::Node v=F.aNode(dfs); marci@193: // typename MutableGraph::Node w=F.bNode(dfs); marci@193: // pred.set(w, dfs); marci@193: // if (F.valid(pred.get(v))) { marci@193: // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); marci@193: // } else { marci@193: // free.set(w, residual_capacity.get(dfs)); marci@193: // } marci@193: // if (w==tF) { marci@193: // __augment=true; marci@193: // _augment=true; marci@193: // break; marci@193: // } marci@193: marci@193: // } else { marci@193: // F.erase(typename MutableGraph::OutEdgeIt(dfs)); marci@193: // } marci@193: // } marci@193: // } marci@193: marci@193: // if (__augment) { marci@193: // typename MutableGraph::Node n=tF; marci@193: // Number augment_value=free.get(tF); marci@193: // while (F.valid(pred.get(n))) { marci@193: // typename MutableGraph::Edge e=pred.get(n); marci@193: // res_graph.augment(original_edge.get(e), augment_value); marci@193: // n=F.tail(e); marci@193: // if (residual_capacity.get(e)==augment_value) marci@193: // F.erase(e); marci@193: // else marci@193: // residual_capacity.set(e, residual_capacity.get(e)-augment_value); marci@193: // } marci@193: // } marci@193: marci@193: // } marci@193: marci@193: // return _augment; marci@193: // } marci@197: bool augmentOnBlockingFlow2() { marci@197: bool _augment=false; marci@193: marci@197: //typedef ErasingResGraphWrapper EAugGraph; marci@197: typedef FilterGraphWrapper< ErasingResGraphWrapper > EAugGraph; marci@197: typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; marci@197: typedef typename EAugGraph::Edge EAugEdge; marci@193: marci@197: EAugGraph res_graph(*G, *flow, *capacity); marci@193: marci@197: //typedef typename EAugGraph::NodeMap ReachedMap; marci@197: BfsIterator4< marci@197: ErasingResGraphWrapper, marci@197: typename ErasingResGraphWrapper::OutEdgeIt, marci@197: ErasingResGraphWrapper::NodeMap > bfs(res_graph); marci@197: marci@197: marci@197: //typename AugGraph::NodeMap pred(res_graph); marci@197: for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@197: if (S->get(s)) { marci@197: Number u=0; marci@197: for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@197: u+=flow->get(e); marci@197: if (u<1) { marci@197: bfs.pushAndSetReached(s); marci@197: //pred.set(s, AugEdge(INVALID)); marci@197: } marci@197: } marci@197: } marci@197: marci@193: marci@197: //bfs.pushAndSetReached(s); marci@193: marci@197: typename ErasingResGraphWrapper:: marci@197: NodeMap& dist=res_graph.dist; marci@193: marci@197: while ( !bfs.finished() ) { marci@197: typename ErasingResGraphWrapper::OutEdgeIt e=bfs; marci@197: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@197: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@197: } marci@197: ++bfs; marci@197: } //computing distances from s in the residual graph marci@193: marci@197: bool __augment=true; marci@193: marci@197: while (__augment) { marci@193: marci@197: __augment=false; marci@197: //computing blocking flow with dfs marci@197: typedef typename EAugGraph::NodeMap BlockingReachedMap; marci@197: DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > marci@197: dfs(res_graph); marci@197: typename EAugGraph::NodeMap pred(res_graph, INVALID); marci@197: //pred.set(s, EAugEdge(INVALID)); marci@197: //invalid iterators for sources marci@193: marci@197: typename EAugGraph::NodeMap free(res_graph); marci@193: marci@197: marci@197: //typename AugGraph::NodeMap pred(res_graph); marci@197: for(NodeIt s=G->template first(); G->valid(s); G->next(s)) { marci@197: if (S->get(s)) { marci@197: Number u=0; marci@197: for(OutEdgeIt e=G->template first(s); G->valid(e); G->next(e)) marci@197: u+=flow->get(e); marci@197: if (u<1) { marci@197: dfs.pushAndSetReached(s); marci@197: //pred.set(s, AugEdge(INVALID)); marci@197: } marci@197: } marci@197: } marci@197: marci@197: marci@197: marci@197: //dfs.pushAndSetReached(s); marci@197: typename EAugGraph::Node n; marci@197: while (!dfs.finished()) { marci@197: ++dfs; marci@197: if (res_graph.valid(EAugOutEdgeIt(dfs))) { marci@197: if (dfs.isBNodeNewlyReached()) { marci@193: marci@197: typename EAugGraph::Node v=res_graph.aNode(dfs); marci@197: typename EAugGraph::Node w=res_graph.bNode(dfs); marci@193: marci@197: pred.set(w, EAugOutEdgeIt(dfs)); marci@197: if (res_graph.valid(pred.get(v))) { marci@197: free.set(w, std::min(free.get(v), res_graph.free(dfs))); marci@197: } else { marci@197: free.set(w, res_graph.free(dfs)); marci@197: } marci@197: marci@197: n=w; marci@197: if (T->get(w)) { marci@197: Number u=0; marci@197: for(InEdgeIt f=G->template first(n); G->valid(f); G->next(f)) marci@197: u+=flow->get(f); marci@197: if (u<1) { marci@197: __augment=true; marci@197: _augment=true; marci@197: break; marci@197: } marci@197: } marci@197: } else { marci@197: res_graph.erase(dfs); marci@197: } marci@197: } marci@193: marci@197: } marci@193: marci@197: if (__augment) { marci@197: // typename EAugGraph::Node n=t; marci@197: Number augment_value=free.get(n); marci@197: while (res_graph.valid(pred.get(n))) { marci@197: EAugEdge e=pred.get(n); marci@197: res_graph.augment(e, augment_value); marci@197: n=res_graph.tail(e); marci@197: if (res_graph.free(e)==0) marci@197: res_graph.erase(e); marci@197: } marci@197: } marci@193: marci@197: } marci@193: marci@197: return _augment; marci@197: } marci@193: void run() { marci@193: //int num_of_augmentations=0; marci@193: while (augmentOnShortestPath()) { marci@193: //while (augmentOnBlockingFlow()) { marci@193: //std::cout << ++num_of_augmentations << " "; marci@193: //std::cout< void run() { marci@194: // //int num_of_augmentations=0; marci@194: // //while (augmentOnShortestPath()) { marci@194: // while (augmentOnBlockingFlow()) { marci@194: // //std::cout << ++num_of_augmentations << " "; marci@194: // //std::cout</*getF*/first(e); G->valid(e); G->next(e)) { marci@193: a+=flow->get(e); marci@193: } marci@193: return a; marci@193: } marci@193: }; marci@193: marci@193: marci@193: marci@193: marci@193: marci@174: marci@174: // template marci@174: // class MaxFlow2 { marci@174: // public: marci@174: // typedef typename Graph::Node Node; marci@174: // typedef typename Graph::Edge Edge; marci@174: // typedef typename Graph::EdgeIt EdgeIt; marci@174: // typedef typename Graph::OutEdgeIt OutEdgeIt; marci@174: // typedef typename Graph::InEdgeIt InEdgeIt; marci@174: // private: marci@174: // const Graph& G; marci@174: // std::list& S; marci@174: // std::list& T; marci@174: // FlowMap& flow; marci@174: // const CapacityMap& capacity; marci@174: // typedef ResGraphWrapper AugGraph; marci@174: // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@174: // typedef typename AugGraph::Edge AugEdge; marci@174: // typename Graph::NodeMap SMap; marci@174: // typename Graph::NodeMap TMap; marci@174: // public: marci@174: // MaxFlow2(const Graph& _G, std::list& _S, std::list& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { marci@174: // for(typename std::list::const_iterator i=S.begin(); marci@174: // i!=S.end(); ++i) { marci@174: // SMap.set(*i, true); marci@174: // } marci@174: // for (typename std::list::const_iterator i=T.begin(); marci@174: // i!=T.end(); ++i) { marci@174: // TMap.set(*i, true); marci@174: // } marci@174: // } marci@174: // bool augment() { marci@174: // AugGraph res_graph(G, flow, capacity); marci@174: // bool _augment=false; marci@174: // Node reached_t_node; marci@174: marci@174: // typedef typename AugGraph::NodeMap ReachedMap; marci@174: // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); marci@174: // for(typename std::list::const_iterator i=S.begin(); marci@174: // i!=S.end(); ++i) { marci@174: // res_bfs.pushAndSetReached(*i); marci@174: // } marci@174: // //res_bfs.pushAndSetReached(s); marci@174: marci@174: // typename AugGraph::NodeMap pred(res_graph); marci@174: // //filled up with invalid iterators marci@174: marci@174: // typename AugGraph::NodeMap free(res_graph); marci@174: marci@174: // //searching for augmenting path marci@174: // while ( !res_bfs.finished() ) { marci@174: // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); marci@174: // if (e.valid() && res_bfs.isBNodeNewlyReached()) { marci@174: // Node v=res_graph.tail(e); marci@174: // Node w=res_graph.head(e); marci@174: // pred.set(w, e); marci@174: // if (pred.get(v).valid()) { marci@174: // free.set(w, std::min(free.get(v), e.free())); marci@174: // } else { marci@174: // free.set(w, e.free()); marci@174: // } marci@174: // if (TMap.get(res_graph.head(e))) { marci@174: // _augment=true; marci@174: // reached_t_node=res_graph.head(e); marci@174: // break; marci@174: // } marci@174: // } marci@174: marci@174: // ++res_bfs; marci@174: // } //end of searching augmenting path marci@174: marci@174: // if (_augment) { marci@174: // Node n=reached_t_node; marci@174: // Number augment_value=free.get(reached_t_node); marci@174: // while (pred.get(n).valid()) { marci@174: // AugEdge e=pred.get(n); marci@174: // e.augment(augment_value); marci@174: // n=res_graph.tail(e); marci@174: // } marci@174: // } marci@174: marci@174: // return _augment; marci@174: // } marci@174: // void run() { marci@174: // while (augment()) { } marci@174: // } marci@174: // Number flowValue() { marci@174: // Number a=0; marci@174: // for(typename std::list::const_iterator i=S.begin(); marci@174: // i!=S.end(); ++i) { marci@174: // for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@174: // a+=flow.get(e); marci@174: // } marci@174: // for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@174: // a-=flow.get(e); marci@174: // } marci@174: // } marci@174: // return a; marci@174: // } marci@174: // }; marci@174: marci@174: marci@174: marci@174: } // namespace hugo marci@174: marci@174: #endif //EDMONDS_KARP_H