marci@59: #ifndef EDMONDS_KARP_HH marci@59: #define EDMONDS_KARP_HH marci@43: marci@43: #include marci@75: #include marci@75: #include marci@43: marci@43: #include marci@133: //#include marci@43: alpar@107: namespace hugo { marci@43: marci@75: template marci@43: class ResGraph { klao@127: public: marci@43: typedef typename Graph::NodeIt NodeIt; marci@43: typedef typename Graph::EachNodeIt EachNodeIt; klao@127: private: marci@43: typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@43: const Graph& G; marci@59: FlowMap& flow; marci@59: const CapacityMap& capacity; marci@43: public: marci@59: ResGraph(const Graph& _G, FlowMap& _flow, marci@59: const CapacityMap& _capacity) : marci@43: G(_G), flow(_flow), capacity(_capacity) { } marci@43: marci@43: class EdgeIt; marci@43: class OutEdgeIt; marci@43: friend class EdgeIt; marci@43: friend class OutEdgeIt; marci@43: marci@43: class EdgeIt { marci@75: friend class ResGraph; marci@43: protected: marci@75: const ResGraph* resG; marci@43: OldSymEdgeIt sym; marci@43: public: marci@43: EdgeIt() { } marci@43: //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { } marci@75: Number free() const { marci@43: if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@43: return (resG->capacity.get(sym)-resG->flow.get(sym)); marci@43: } else { marci@43: return (resG->flow.get(sym)); marci@43: } marci@43: } marci@43: bool valid() const { return sym.valid(); } marci@75: void augment(Number a) const { marci@43: if (resG->G.aNode(sym)==resG->G.tail(sym)) { marci@43: resG->flow.set(sym, resG->flow.get(sym)+a); marci@75: //resG->flow[sym]+=a; marci@43: } else { marci@43: resG->flow.set(sym, resG->flow.get(sym)-a); marci@75: //resG->flow[sym]-=a; marci@43: } marci@43: } marci@43: }; marci@43: marci@43: class OutEdgeIt : public EdgeIt { marci@75: friend class ResGraph; marci@43: public: marci@43: OutEdgeIt() { } marci@43: //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; } marci@43: private: marci@75: OutEdgeIt(const ResGraph& _resG, NodeIt v) { marci@43: resG=&_resG; marci@43: sym=resG->G.template first(v); marci@43: while( sym.valid() && !(free()>0) ) { ++sym; } marci@43: } marci@43: public: marci@43: OutEdgeIt& operator++() { marci@43: ++sym; marci@43: while( sym.valid() && !(free()>0) ) { ++sym; } marci@43: return *this; marci@43: } marci@43: }; marci@43: marci@64: void getFirst(OutEdgeIt& e, NodeIt v) const { marci@43: e=OutEdgeIt(*this, v); marci@43: } marci@43: void getFirst(EachNodeIt& v) const { G.getFirst(v); } marci@43: marci@43: template< typename It > marci@43: It first() const { marci@75: It e; marci@75: getFirst(e); marci@75: return e; marci@75: } marci@75: marci@75: template< typename It > marci@75: It first(NodeIt v) const { marci@75: It e; marci@75: getFirst(e, v); marci@75: return e; marci@75: } marci@75: marci@75: NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } marci@75: NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } marci@75: marci@75: NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } marci@75: NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } marci@75: marci@75: int id(NodeIt v) const { return G.id(v); } marci@75: marci@75: template marci@75: class NodeMap { marci@75: typename Graph::NodeMap node_map; marci@75: public: marci@75: NodeMap(const ResGraph& _G) : node_map(_G.G) { } marci@75: NodeMap(const ResGraph& _G, S a) : node_map(_G.G, a) { } marci@75: void set(NodeIt nit, S a) { node_map.set(nit, a); } marci@75: S get(NodeIt nit) const { return node_map.get(nit); } marci@75: S& operator[](NodeIt nit) { return node_map[nit]; } marci@75: const S& operator[](NodeIt nit) const { return node_map[nit]; } marci@75: }; marci@75: marci@75: }; marci@75: marci@75: marci@75: template marci@75: class ResGraph2 { klao@127: public: marci@75: typedef typename Graph::NodeIt NodeIt; marci@75: typedef typename Graph::EachNodeIt EachNodeIt; klao@127: private: marci@75: //typedef typename Graph::SymEdgeIt OldSymEdgeIt; marci@75: typedef typename Graph::OutEdgeIt OldOutEdgeIt; marci@75: typedef typename Graph::InEdgeIt OldInEdgeIt; marci@75: marci@75: const Graph& G; marci@75: FlowMap& flow; marci@75: const CapacityMap& capacity; marci@75: public: marci@75: ResGraph2(const Graph& _G, FlowMap& _flow, marci@75: const CapacityMap& _capacity) : marci@75: G(_G), flow(_flow), capacity(_capacity) { } marci@75: marci@75: class EdgeIt; marci@75: class OutEdgeIt; marci@75: friend class EdgeIt; marci@75: friend class OutEdgeIt; marci@75: marci@75: class EdgeIt { marci@75: friend class ResGraph2; marci@75: protected: marci@75: const ResGraph2* resG; marci@75: //OldSymEdgeIt sym; marci@75: OldOutEdgeIt out; marci@75: OldInEdgeIt in; marci@148: bool out_or_in; //true, iff out marci@75: public: marci@148: EdgeIt() : out_or_in(true) { } marci@75: Number free() const { marci@75: if (out_or_in) { marci@75: return (resG->capacity.get(out)-resG->flow.get(out)); marci@75: } else { marci@75: return (resG->flow.get(in)); marci@75: } marci@75: } marci@75: bool valid() const { marci@75: return out_or_in && out.valid() || in.valid(); } marci@75: void augment(Number a) const { marci@75: if (out_or_in) { marci@75: resG->flow.set(out, resG->flow.get(out)+a); marci@75: } else { marci@75: resG->flow.set(in, resG->flow.get(in)-a); marci@75: } marci@75: } marci@75: }; marci@75: marci@75: class OutEdgeIt : public EdgeIt { marci@75: friend class ResGraph2; marci@75: public: marci@75: OutEdgeIt() { } marci@75: private: marci@75: OutEdgeIt(const ResGraph2& _resG, NodeIt v) { marci@75: resG=&_resG; marci@75: out=resG->G.template first(v); marci@75: while( out.valid() && !(free()>0) ) { ++out; } marci@75: if (!out.valid()) { marci@75: out_or_in=0; marci@75: in=resG->G.template first(v); marci@75: while( in.valid() && !(free()>0) ) { ++in; } marci@75: } marci@75: } marci@75: public: marci@75: OutEdgeIt& operator++() { marci@75: if (out_or_in) { marci@75: NodeIt v=resG->G.aNode(out); marci@75: ++out; marci@75: while( out.valid() && !(free()>0) ) { ++out; } marci@75: if (!out.valid()) { marci@75: out_or_in=0; marci@75: in=resG->G.template first(v); marci@75: while( in.valid() && !(free()>0) ) { ++in; } marci@75: } marci@75: } else { marci@75: ++in; marci@75: while( in.valid() && !(free()>0) ) { ++in; } marci@75: } marci@75: return *this; marci@75: } marci@75: }; marci@75: marci@75: void getFirst(OutEdgeIt& e, NodeIt v) const { marci@75: e=OutEdgeIt(*this, v); marci@75: } marci@75: void getFirst(EachNodeIt& v) const { G.getFirst(v); } marci@75: marci@75: template< typename It > marci@75: It first() const { marci@43: It e; marci@43: getFirst(e); marci@43: return e; marci@43: } marci@43: marci@43: template< typename It > marci@64: It first(NodeIt v) const { marci@43: It e; marci@43: getFirst(e, v); marci@43: return e; marci@43: } marci@43: marci@75: NodeIt tail(EdgeIt e) const { marci@75: return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@75: NodeIt head(EdgeIt e) const { marci@75: return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@43: marci@75: NodeIt aNode(OutEdgeIt e) const { marci@75: return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } marci@75: NodeIt bNode(OutEdgeIt e) const { marci@75: return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } marci@43: marci@64: int id(NodeIt v) const { return G.id(v); } marci@43: marci@69: template marci@43: class NodeMap { marci@69: typename Graph::NodeMap node_map; marci@43: public: marci@75: NodeMap(const ResGraph2& _G) : node_map(_G.G) { } marci@75: NodeMap(const ResGraph2& _G, S a) : node_map(_G.G, a) { } marci@75: void set(NodeIt nit, S a) { node_map.set(nit, a); } marci@75: S get(NodeIt nit) const { return node_map.get(nit); } marci@75: }; marci@75: }; marci@75: marci@43: marci@75: template marci@59: class MaxFlow { klao@127: public: marci@43: typedef typename Graph::NodeIt NodeIt; marci@43: typedef typename Graph::EdgeIt EdgeIt; marci@43: typedef typename Graph::EachEdgeIt EachEdgeIt; marci@43: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@43: typedef typename Graph::InEdgeIt InEdgeIt; klao@127: klao@127: private: marci@148: const Graph* G; marci@64: NodeIt s; marci@64: NodeIt t; marci@148: FlowMap* flow; marci@148: const CapacityMap* capacity; marci@148: typedef ResGraphWrapper AugGraph; marci@59: typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@59: typedef typename AugGraph::EdgeIt AugEdgeIt; marci@75: marci@75: //AugGraph res_graph; marci@75: //typedef typename AugGraph::NodeMap ReachedMap; marci@75: //typename AugGraph::NodeMap pred; marci@133: //typename AugGraph::NodeMap free; marci@59: public: marci@75: MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : marci@148: G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, marci@75: //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) marci@75: { } marci@133: bool augmentOnShortestPath() { marci@148: AugGraph res_graph(*G, *flow, *capacity); marci@59: bool _augment=false; marci@59: marci@59: typedef typename AugGraph::NodeMap ReachedMap; marci@148: BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); marci@59: res_bfs.pushAndSetReached(s); marci@59: marci@59: typename AugGraph::NodeMap pred(res_graph); marci@75: //filled up with invalid iterators marci@75: //pred.set(s, AugEdgeIt()); marci@59: marci@133: typename AugGraph::NodeMap free(res_graph); marci@59: marci@59: //searching for augmenting path marci@59: while ( !res_bfs.finished() ) { marci@141: AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); marci@148: if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { marci@59: NodeIt v=res_graph.tail(e); marci@59: NodeIt w=res_graph.head(e); marci@59: pred.set(w, e); marci@148: if (res_graph.valid(pred.get(v))) { marci@59: free.set(w, std::min(free.get(v), e.free())); marci@59: } else { marci@59: free.set(w, e.free()); marci@59: } marci@59: if (res_graph.head(e)==t) { _augment=true; break; } marci@59: } marci@59: marci@59: ++res_bfs; marci@59: } //end of searching augmenting path marci@43: marci@59: if (_augment) { marci@59: NodeIt n=t; marci@75: Number augment_value=free.get(t); marci@148: while (res_graph.valid(pred.get(n))) { marci@59: AugEdgeIt e=pred.get(n); marci@59: e.augment(augment_value); marci@59: n=res_graph.tail(e); marci@59: } marci@59: } marci@59: marci@59: return _augment; marci@59: } marci@141: marci@133: template bool augmentOnBlockingFlow() { marci@133: bool _augment=false; marci@133: marci@148: AugGraph res_graph(*G, *flow, *capacity); marci@133: marci@133: typedef typename AugGraph::NodeMap ReachedMap; marci@133: BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); marci@133: marci@100: bfs.pushAndSetReached(s); marci@133: typename AugGraph::NodeMap dist(res_graph); //filled up with 0's marci@100: while ( !bfs.finished() ) { marci@141: AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); marci@148: if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { marci@133: dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); marci@100: } marci@100: marci@100: ++bfs; marci@133: } //computing distances from s in the residual graph marci@100: marci@100: MutableGraph F; marci@133: typename AugGraph::NodeMap res_graph_to_F(res_graph); marci@148: for(typename AugGraph::EachNodeIt n=res_graph.template first(); res_graph.valid(n); res_graph.next(n)) { marci@133: res_graph_to_F.set(n, F.addNode()); marci@100: } marci@133: marci@133: typename MutableGraph::NodeIt sF=res_graph_to_F.get(s); marci@133: typename MutableGraph::NodeIt tF=res_graph_to_F.get(t); marci@133: marci@133: typename MutableGraph::EdgeMap original_edge(F); marci@148: typename MutableGraph::EdgeMap residual_capacity(F); marci@133: marci@133: //Making F to the graph containing the edges of the residual graph marci@133: //which are in some shortest paths marci@148: for(typename AugGraph::EachEdgeIt e=res_graph.template first(); res_graph.valid(e); res_graph.next(e)) { marci@133: if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { marci@133: typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); marci@133: original_edge.update(); marci@133: original_edge.set(f, e); marci@148: residual_capacity.update(); marci@148: residual_capacity.set(f, e.free()); marci@133: } marci@133: } marci@133: marci@133: bool __augment=true; marci@133: marci@133: while (__augment) { marci@133: __augment=false; marci@133: //computing blocking flow with dfs marci@133: typedef typename MutableGraph::NodeMap BlockingReachedMap; marci@133: DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); marci@133: typename MutableGraph::NodeMap pred(F); //invalid iterators marci@133: typename MutableGraph::NodeMap free(F); marci@133: marci@133: dfs.pushAndSetReached(sF); marci@133: while (!dfs.finished()) { marci@133: ++dfs; marci@148: if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { marci@133: //std::cout << "OutEdgeIt: " << dfs; marci@133: //std::cout << " aNode: " << F.aNode(dfs); marci@133: //std::cout << " bNode: " << F.bNode(dfs) << " "; marci@133: marci@133: typename MutableGraph::NodeIt v=F.aNode(dfs); marci@133: typename MutableGraph::NodeIt w=F.bNode(dfs); marci@133: pred.set(w, dfs); marci@148: if (F.valid(pred.get(v))) { marci@148: free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); marci@133: } else { marci@148: free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/); marci@133: } marci@133: if (w==tF) { marci@133: //std::cout << "AUGMENTATION"<()) { marci@133: //std::cout << ++num_of_augmentations << " "; marci@133: //std::cout< void run() { marci@133: //int num_of_augmentations=0; marci@133: //while (augmentOnShortestPath()) { marci@133: while (augmentOnBlockingFlow()) { marci@100: //std::cout << ++num_of_augmentations << " "; marci@100: //std::cout<getFirst(e, s); G->valid(e); G->next(e)) { marci@148: a+=flow->get(e); marci@69: } marci@69: return a; marci@69: } marci@43: }; marci@43: marci@75: marci@155: // template marci@155: // class MaxFlow2 { marci@155: // public: marci@155: // typedef typename Graph::NodeIt NodeIt; marci@155: // typedef typename Graph::EdgeIt EdgeIt; marci@155: // typedef typename Graph::EachEdgeIt EachEdgeIt; marci@155: // typedef typename Graph::OutEdgeIt OutEdgeIt; marci@155: // typedef typename Graph::InEdgeIt InEdgeIt; marci@155: // private: marci@155: // const Graph& G; marci@155: // std::list& S; marci@155: // std::list& T; marci@155: // FlowMap& flow; marci@155: // const CapacityMap& capacity; marci@155: // typedef ResGraphWrapper AugGraph; marci@155: // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@155: // typedef typename AugGraph::EdgeIt AugEdgeIt; marci@155: // typename Graph::NodeMap SMap; marci@155: // typename Graph::NodeMap TMap; marci@155: // public: marci@155: // 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@155: // for(typename std::list::const_iterator i=S.begin(); marci@155: // i!=S.end(); ++i) { marci@155: // SMap.set(*i, true); marci@155: // } marci@155: // for (typename std::list::const_iterator i=T.begin(); marci@155: // i!=T.end(); ++i) { marci@155: // TMap.set(*i, true); marci@155: // } marci@155: // } marci@155: // bool augment() { marci@155: // AugGraph res_graph(G, flow, capacity); marci@155: // bool _augment=false; marci@155: // NodeIt reached_t_node; marci@75: marci@155: // typedef typename AugGraph::NodeMap ReachedMap; marci@155: // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); marci@155: // for(typename std::list::const_iterator i=S.begin(); marci@155: // i!=S.end(); ++i) { marci@155: // res_bfs.pushAndSetReached(*i); marci@155: // } marci@155: // //res_bfs.pushAndSetReached(s); marci@75: marci@155: // typename AugGraph::NodeMap pred(res_graph); marci@155: // //filled up with invalid iterators marci@75: marci@155: // typename AugGraph::NodeMap free(res_graph); marci@75: marci@155: // //searching for augmenting path marci@155: // while ( !res_bfs.finished() ) { marci@155: // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); marci@155: // if (e.valid() && res_bfs.isBNodeNewlyReached()) { marci@155: // NodeIt v=res_graph.tail(e); marci@155: // NodeIt w=res_graph.head(e); marci@155: // pred.set(w, e); marci@155: // if (pred.get(v).valid()) { marci@155: // free.set(w, std::min(free.get(v), e.free())); marci@155: // } else { marci@155: // free.set(w, e.free()); marci@155: // } marci@155: // if (TMap.get(res_graph.head(e))) { marci@155: // _augment=true; marci@155: // reached_t_node=res_graph.head(e); marci@155: // break; marci@155: // } marci@155: // } marci@75: marci@155: // ++res_bfs; marci@155: // } //end of searching augmenting path marci@75: marci@155: // if (_augment) { marci@155: // NodeIt n=reached_t_node; marci@155: // Number augment_value=free.get(reached_t_node); marci@155: // while (pred.get(n).valid()) { marci@155: // AugEdgeIt e=pred.get(n); marci@155: // e.augment(augment_value); marci@155: // n=res_graph.tail(e); marci@155: // } marci@155: // } marci@75: marci@155: // return _augment; marci@155: // } marci@155: // void run() { marci@155: // while (augment()) { } marci@155: // } marci@155: // Number flowValue() { marci@155: // Number a=0; marci@155: // for(typename std::list::const_iterator i=S.begin(); marci@155: // i!=S.end(); ++i) { marci@155: // for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@155: // a+=flow.get(e); marci@155: // } marci@155: // for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@155: // a-=flow.get(e); marci@155: // } marci@155: // } marci@155: // return a; marci@155: // } marci@155: // }; marci@75: marci@75: marci@75: alpar@107: } // namespace hugo marci@43: marci@59: #endif //EDMONDS_KARP_HH