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