marci@59: #ifndef EDMONDS_KARP_HH marci@59: #define EDMONDS_KARP_HH marci@43: marci@43: #include marci@43: marci@43: #include marci@43: marci@43: namespace marci { marci@43: marci@59: template marci@43: class ResGraph { marci@43: typedef typename Graph::NodeIt NodeIt; marci@43: typedef typename Graph::EachNodeIt EachNodeIt; 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@59: friend class ResGraph; marci@43: protected: marci@59: 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@43: T 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@64: void augment(T 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@43: } else { marci@43: resG->flow.set(sym, resG->flow.get(sym)-a); marci@43: } marci@43: } marci@43: }; marci@43: marci@43: class OutEdgeIt : public EdgeIt { marci@59: 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@64: 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@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@64: NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); } marci@64: NodeIt head(EdgeIt e) const { return G.bNode(e.sym); } marci@43: marci@64: NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); } marci@64: NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); } 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@59: NodeMap(const ResGraph& _G) : node_map(_G.G) { } marci@69: NodeMap(const ResGraph& _G, S a) : node_map(_G.G, a) { } marci@69: void set(NodeIt nit, S a) { node_map.set(nit, a); } marci@69: S get(NodeIt nit) const { return node_map.get(nit); } marci@43: }; marci@43: marci@43: }; marci@43: marci@59: template marci@59: class MaxFlow { 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; marci@43: const Graph& G; marci@64: NodeIt s; marci@64: NodeIt t; marci@59: FlowMap& flow; marci@59: const CapacityMap& capacity; marci@59: typedef ResGraph AugGraph; marci@59: typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@59: typedef typename AugGraph::EdgeIt AugEdgeIt; marci@59: public: marci@64: MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { } marci@59: bool augment() { marci@59: AugGraph res_graph(G, flow, capacity); marci@59: bool _augment=false; marci@59: marci@59: typedef typename AugGraph::NodeMap ReachedMap; marci@59: BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); marci@59: res_bfs.pushAndSetReached(s); marci@59: marci@59: typename AugGraph::NodeMap pred(res_graph); marci@59: //filled with invalid iterators marci@59: marci@59: typename AugGraph::NodeMap free(res_graph); marci@59: marci@59: //searching for augmenting path marci@59: while ( !res_bfs.finished() ) { marci@59: AugOutEdgeIt e=AugOutEdgeIt(res_bfs); marci@59: if (e.valid() && 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@59: if (pred.get(v).valid()) { 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@59: T augment_value=free.get(t); marci@59: while (pred.get(n).valid()) { 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@43: void run() { marci@59: while (augment()) { } marci@43: } marci@69: T flowValue() { marci@69: T a=0; marci@69: for(OutEdgeIt i=G.template first(s); i.valid(); ++i) { marci@69: a+=flow.get(i); marci@69: } marci@69: return a; marci@69: } marci@43: }; marci@43: marci@43: } // namespace marci marci@43: marci@59: #endif //EDMONDS_KARP_HH