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@311: #include marci@301: marci@301: namespace hugo { marci@301: marci@330: // template marci@330: // class ResGraph { marci@330: // public: marci@330: // typedef typename Graph::Node Node; marci@330: // typedef typename Graph::NodeIt NodeIt; marci@330: // private: marci@330: // typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@330: // const Graph& G; marci@330: // const CapacityMap& capacity; marci@330: // FlowMap& flow; marci@330: // public: marci@330: // ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) : marci@330: // G(_G), capacity(_capacity), flow(_flow) { } marci@301: marci@330: // class Edge; marci@330: // class OutEdgeIt; marci@330: // friend class Edge; marci@330: // friend class OutEdgeIt; marci@301: marci@330: // class Edge { marci@330: // friend class ResGraph; marci@330: // protected: marci@330: // const ResGraph* resG; marci@330: // OldSymEdgeIt sym; marci@330: // public: marci@330: // Edge() { } marci@330: // //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } marci@330: // Number free() const { marci@330: // if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@330: // return (resG->capacity.get(sym)-resG->flow.get(sym)); marci@330: // } else { marci@330: // return (resG->flow.get(sym)); marci@330: // } marci@330: // } marci@330: // bool valid() const { return sym.valid(); } marci@330: // void augment(Number a) const { marci@330: // if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@330: // resG->flow.set(sym, resG->flow.get(sym)+a); marci@330: // //resG->flow[sym]+=a; marci@330: // } else { marci@330: // resG->flow.set(sym, resG->flow.get(sym)-a); marci@330: // //resG->flow[sym]-=a; marci@330: // } marci@330: // } marci@330: // }; marci@301: marci@330: // class OutEdgeIt : public Edge { marci@330: // friend class ResGraph; marci@330: // public: marci@330: // OutEdgeIt() { } marci@330: // //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } marci@330: // private: marci@330: // OutEdgeIt(const ResGraph& _resG, Node v) { marci@330: // resG=&_resG; marci@330: // sym=resG->G.template first(v); marci@330: // while( sym.valid() && !(free()>0) ) { ++sym; } marci@330: // } marci@330: // public: marci@330: // OutEdgeIt& operator++() { marci@330: // ++sym; marci@330: // while( sym.valid() && !(free()>0) ) { ++sym; } marci@330: // return *this; marci@330: // } marci@330: // }; marci@301: marci@330: // void /*getF*/first(OutEdgeIt& e, Node v) const { marci@330: // e=OutEdgeIt(*this, v); marci@330: // } marci@330: // void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } marci@301: marci@330: // template< typename It > marci@330: // It first() const { marci@330: // It e; marci@330: // /*getF*/first(e); marci@330: // return e; marci@330: // } marci@301: marci@330: // template< typename It > marci@330: // It first(Node v) const { marci@330: // It e; marci@330: // /*getF*/first(e, v); marci@330: // return e; marci@330: // } marci@301: marci@330: // Node tail(Edge e) const { return G.aNode(e.sym); } marci@330: // Node head(Edge e) const { return G.bNode(e.sym); } marci@301: marci@330: // Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } marci@330: // Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); } marci@301: marci@330: // int id(Node v) const { return G.id(v); } marci@301: marci@330: // template marci@330: // class NodeMap { marci@330: // typename Graph::NodeMap node_map; marci@330: // public: marci@330: // NodeMap(const ResGraph& _G) : node_map(_G.G) { } marci@330: // NodeMap(const ResGraph& _G, S a) : node_map(_G.G, a) { } marci@330: // void set(Node nit, S a) { node_map.set(nit, a); } marci@330: // S get(Node nit) const { return node_map.get(nit); } marci@330: // S& operator[](Node nit) { return node_map[nit]; } marci@330: // const S& operator[](Node nit) const { return node_map[nit]; } marci@330: // }; marci@301: marci@330: // }; marci@301: marci@301: marci@330: // template marci@330: // class ResGraph2 { marci@330: // public: marci@330: // typedef typename Graph::Node Node; marci@330: // typedef typename Graph::NodeIt NodeIt; marci@330: // private: marci@330: // //typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@330: // typedef typename Graph::OutEdgeIt OldOutEdgeIt; marci@330: // typedef typename Graph::InEdgeIt OldInEdgeIt; marci@301: marci@330: // const Graph& G; marci@330: // FlowMap& flow; marci@330: // const CapacityMap& capacity; marci@330: // public: marci@330: // ResGraph2(const Graph& _G, FlowMap& _flow, marci@330: // const CapacityMap& _capacity) : marci@330: // G(_G), flow(_flow), capacity(_capacity) { } marci@301: marci@330: // class Edge; marci@330: // class OutEdgeIt; marci@330: // friend class Edge; marci@330: // friend class OutEdgeIt; marci@301: marci@330: // class Edge { marci@330: // friend class ResGraph2; marci@330: // protected: marci@330: // const ResGraph2* resG; marci@330: // //OldSymEdgeIt sym; marci@330: // OldOutEdgeIt out; marci@330: // OldInEdgeIt in; marci@330: // bool out_or_in; //true, iff out marci@330: // public: marci@330: // Edge() : out_or_in(true) { } marci@330: // Number free() const { marci@330: // if (out_or_in) { marci@330: // return (resG->capacity.get(out)-resG->flow.get(out)); marci@330: // } else { marci@330: // return (resG->flow.get(in)); marci@330: // } marci@330: // } marci@330: // bool valid() const { marci@330: // return out_or_in && out.valid() || in.valid(); } marci@330: // void augment(Number a) const { marci@330: // if (out_or_in) { marci@330: // resG->flow.set(out, resG->flow.get(out)+a); marci@330: // } else { marci@330: // resG->flow.set(in, resG->flow.get(in)-a); marci@330: // } marci@330: // } marci@330: // }; marci@301: marci@330: // class OutEdgeIt : public Edge { marci@330: // friend class ResGraph2; marci@330: // public: marci@330: // OutEdgeIt() { } marci@330: // private: marci@330: // OutEdgeIt(const ResGraph2& _resG, Node v) { marci@330: // resG=&_resG; marci@330: // out=resG->G.template first(v); marci@330: // while( out.valid() && !(free()>0) ) { ++out; } marci@330: // if (!out.valid()) { marci@330: // out_or_in=0; marci@330: // in=resG->G.template first(v); marci@330: // while( in.valid() && !(free()>0) ) { ++in; } marci@330: // } marci@330: // } marci@330: // public: marci@330: // OutEdgeIt& operator++() { marci@330: // if (out_or_in) { marci@330: // Node v=resG->G.aNode(out); marci@330: // ++out; marci@330: // while( out.valid() && !(free()>0) ) { ++out; } marci@330: // if (!out.valid()) { marci@330: // out_or_in=0; marci@330: // in=resG->G.template first(v); marci@330: // while( in.valid() && !(free()>0) ) { ++in; } marci@330: // } marci@330: // } else { marci@330: // ++in; marci@330: // while( in.valid() && !(free()>0) ) { ++in; } marci@330: // } marci@330: // return *this; marci@330: // } marci@330: // }; marci@301: marci@330: // void /*getF*/first(OutEdgeIt& e, Node v) const { marci@330: // e=OutEdgeIt(*this, v); marci@330: // } marci@330: // void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); } marci@301: marci@330: // template< typename It > marci@330: // It first() const { marci@330: // It e; marci@330: // /*getF*/first(e); marci@330: // return e; marci@330: // } marci@301: marci@330: // template< typename It > marci@330: // It first(Node v) const { marci@330: // It e; marci@330: // /*getF*/first(e, v); marci@330: // return e; marci@330: // } marci@301: marci@330: // Node tail(Edge e) const { marci@330: // return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@330: // Node head(Edge e) const { marci@330: // return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@301: marci@330: // Node aNode(OutEdgeIt e) const { marci@330: // return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@330: // Node bNode(OutEdgeIt e) const { marci@330: // return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@301: marci@330: // int id(Node v) const { return G.id(v); } marci@301: marci@330: // template marci@330: // class NodeMap { marci@330: // typename Graph::NodeMap node_map; marci@330: // public: marci@330: // NodeMap(const ResGraph2& _G) : node_map(_G.G) { } marci@330: // NodeMap(const ResGraph2& _G, S a) : node_map(_G.G, a) { } marci@330: // void set(Node nit, S a) { node_map.set(nit, a); } marci@330: // S get(Node nit) const { return node_map.get(nit); } marci@330: // }; marci@330: // }; marci@301: marci@301: marci@330: 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@330: const CapacityMap* capacity; marci@301: FlowMap* flow; marci@330: typedef ResGraphWrapper ResGW; marci@301: typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; marci@301: typedef typename ResGW::Edge ResGWEdge; marci@301: public: marci@301: marci@330: MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity, marci@330: FlowMap& _flow) : marci@330: g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { } marci@301: marci@301: bool augmentOnShortestPath() { marci@330: ResGW res_graph(*g, *capacity, *flow); marci@301: bool _augment=false; marci@301: marci@360: BfsIterator< ResGW, typename ResGW::NodeMap > 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@330: ResGW res_graph(*g, *capacity, *flow); marci@301: marci@360: BfsIterator< ResGW, typename ResGW::NodeMap > 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@311: ConstMap true_map(true); marci@311: typedef SubGraphWrapper, marci@311: DistanceMap > FilterResGW; marci@311: FilterResGW filter_res_graph(res_graph, true_map, 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@312: marci@360: DfsIterator< MG, typename MG::NodeMap > 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@330: ResGW res_graph(*g, *capacity, *flow); marci@301: marci@301: //bfs for distances on the residual graph marci@360: BfsIterator< ResGW, typename ResGW::NodeMap > 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@360: DfsIterator< MG, typename MG::NodeMap > 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@330: ResGW res_graph(*g, *capacity, *flow); marci@301: marci@360: BfsIterator< ResGW, typename ResGW::NodeMap > 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@311: ConstMap true_map(true); marci@311: typedef SubGraphWrapper, marci@311: DistanceMap > FilterResGW; marci@311: FilterResGW filter_res_graph(res_graph, true_map, 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@311: //computing blocking flow with dfs marci@360: DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap > marci@311: dfs(erasing_res_graph); marci@301: typename ErasingResGW::NodeMap marci@301: pred(erasing_res_graph); marci@301: pred.set(s, INVALID); marci@311: //invalid iterators for sources marci@301: marci@317: typename ErasingResGW::NodeMap free1(erasing_res_graph); marci@301: marci@317: dfs.pushAndSetReached( marci@317: typename ErasingResGW::Node( marci@317: typename FilterResGW::Node( marci@317: typename ResGW::Node(s) marci@317: ) marci@317: ) marci@317: ); marci@301: while (!dfs.finished()) { marci@301: ++dfs; marci@301: if (erasing_res_graph.valid( marci@317: typename ErasingResGW::OutEdgeIt(dfs))) marci@301: { marci@311: 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@317: free1.set(w, std::min(free1[v], res_graph.resCap( marci@317: typename ErasingResGW::OutEdgeIt(dfs)))); marci@301: } else { marci@317: free1.set(w, res_graph.resCap( marci@317: typename ErasingResGW::OutEdgeIt(dfs))); marci@301: } marci@301: marci@301: if (w==t) { marci@301: __augment=true; marci@301: _augment=true; marci@301: break; marci@301: } marci@311: } else { marci@311: erasing_res_graph.erase(dfs); marci@301: } marci@301: } marci@301: } marci@301: marci@311: if (__augment) { marci@317: typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t)); marci@317: // typename ResGW::NodeMap a(res_graph); marci@317: // typename ResGW::Node b; marci@317: // Number j=a[b]; marci@317: // typename FilterResGW::NodeMap a1(filter_res_graph); marci@317: // typename FilterResGW::Node b1; marci@317: // Number j1=a1[b1]; marci@317: // typename ErasingResGW::NodeMap a2(erasing_res_graph); marci@317: // typename ErasingResGW::Node b2; marci@317: // Number j2=a2[b2]; marci@317: Number augment_value=free1[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@311: } marci@311: } 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@360: // BfsIterator< 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@360: // BfsIterator< 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@360: // DfsIterator< 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