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