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@75: template marci@148: class ResGraphWrapper { 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::OutEdgeIt OldOutEdgeIt; marci@75: typedef typename Graph::InEdgeIt OldInEdgeIt; marci@148: const Graph* G; marci@148: FlowMap* flow; marci@148: const CapacityMap* capacity; marci@75: public: marci@148: ResGraphWrapper(const Graph& _G, FlowMap& _flow, marci@75: const CapacityMap& _capacity) : marci@148: G(&_G), flow(&_flow), capacity(&_capacity) { } marci@148: // ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) : marci@148: // G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { } 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@148: friend class ResGraphWrapper; marci@75: protected: marci@75: //const ResGraph3* resG; marci@75: const Graph* G; marci@75: FlowMap* flow; marci@75: const CapacityMap* capacity; 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@148: EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : marci@148: G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { } marci@133: //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { } 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@133: void print() { marci@133: if (out_or_in) { marci@133: std::cout << "out "; marci@133: if (out.valid()) marci@133: std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out)); marci@133: else marci@133: std::cout << "invalid"; marci@133: } marci@133: else { marci@133: std::cout << "in "; marci@133: if (in.valid()) marci@133: std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in)); marci@133: else marci@133: std::cout << "invalid"; marci@133: } marci@133: std::cout << std::endl; marci@133: } marci@75: }; marci@75: marci@148: Number free(OldOutEdgeIt out) const { marci@148: return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out)); marci@148: } marci@148: Number free(OldInEdgeIt in) const { marci@148: return (/*resG->*/flow->get(in)); marci@148: } marci@148: marci@75: class OutEdgeIt : public EdgeIt { marci@148: friend class ResGraphWrapper; marci@75: public: marci@75: OutEdgeIt() { } marci@75: private: marci@148: OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { marci@133: //out=/*resG->*/G->template first(v); marci@133: G->getFirst(out, v); marci@148: while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } marci@75: if (!out.valid()) { marci@75: out_or_in=0; marci@133: //in=/*resG->*/G->template first(v); marci@133: G->getFirst(in, v); marci@148: while( in.valid() && !(EdgeIt::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@148: while( out.valid() && !(EdgeIt::free()>0) ) { ++out; } marci@75: if (!out.valid()) { marci@75: out_or_in=0; marci@133: G->getFirst(in, v); //=/*resG->*/G->template first(v); marci@148: while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@75: } marci@75: } else { marci@75: ++in; marci@148: while( in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@75: } marci@75: return *this; marci@75: } marci@75: }; marci@75: marci@133: class EachEdgeIt : public EdgeIt { marci@148: friend class ResGraphWrapper; marci@133: typename Graph::EachNodeIt v; marci@133: public: marci@133: EachEdgeIt() { } marci@133: //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { } marci@148: EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) { marci@148: out_or_in=true; marci@133: G->getFirst(v); marci@133: if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt(); marci@148: while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } marci@133: while (v.valid() && !out.valid()) { marci@133: ++v; marci@133: if (v.valid()) G->getFirst(out, v); marci@148: while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } marci@133: } marci@133: if (!out.valid()) { marci@133: out_or_in=0; marci@133: G->getFirst(v); marci@133: if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); marci@148: while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@133: while (v.valid() && !in.valid()) { marci@133: ++v; marci@133: if (v.valid()) G->getFirst(in, v); marci@148: while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@133: } marci@133: } marci@133: } marci@133: EachEdgeIt& operator++() { marci@133: if (out_or_in) { marci@133: ++out; marci@148: while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } marci@133: while (v.valid() && !out.valid()) { marci@133: ++v; marci@133: if (v.valid()) G->getFirst(out, v); marci@148: while (out.valid() && !(EdgeIt::free()>0) ) { ++out; } marci@133: } marci@133: if (!out.valid()) { marci@133: out_or_in=0; marci@133: G->getFirst(v); marci@133: if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt(); marci@148: while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@133: while (v.valid() && !in.valid()) { marci@133: ++v; marci@133: if (v.valid()) G->getFirst(in, v); marci@148: while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@133: } marci@133: } marci@133: } else { marci@133: ++in; marci@148: while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@133: while (v.valid() && !in.valid()) { marci@133: ++v; marci@133: if (v.valid()) G->getFirst(in, v); marci@148: while (in.valid() && !(EdgeIt::free()>0) ) { ++in; } marci@133: } marci@133: } marci@133: return *this; marci@133: } marci@133: }; marci@133: marci@148: void getFirst(EachNodeIt& v) const { G->getFirst(v); } marci@75: void getFirst(OutEdgeIt& e, NodeIt v) const { marci@148: e=OutEdgeIt(*G, v, *flow, *capacity); marci@75: } marci@133: void getFirst(EachEdgeIt& e) const { marci@148: e=EachEdgeIt(*G, *flow, *capacity); marci@133: } marci@148: marci@148: EachNodeIt& next(EachNodeIt& n) const { return G->next(n); } marci@148: marci@148: OutEdgeIt& next(OutEdgeIt& e) const { marci@148: if (e.out_or_in) { marci@148: NodeIt v=G->aNode(e.out); marci@148: ++(e.out); marci@148: while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); } marci@148: if (!G->valid(e.out)) { marci@148: e.out_or_in=0; marci@148: G->getFirst(e.in, v); //=/*resG->*/G->template first(v); marci@148: while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } marci@148: } marci@148: } else { marci@148: ++(e.in); marci@148: while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } marci@148: } marci@148: return e; marci@148: } marci@148: marci@148: EachEdgeIt& next(EachEdgeIt& e) const { marci@148: if (e.out_or_in) { marci@148: ++(e.out); marci@148: while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); } marci@148: while (G->valid(e.v) && !G->valid(e.out)) { marci@148: ++(e.v); marci@148: if (G->valid(e.v)) G->getFirst(e.out, e.v); marci@148: while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); } marci@148: } marci@148: if (!G->valid(e.out)) { marci@148: e.out_or_in=0; marci@148: G->getFirst(e.v); marci@148: if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt(); marci@148: while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } marci@148: while (G->valid(e.v) && !G->valid(e.in)) { marci@148: ++(e.v); marci@148: if (G->valid(e.v)) G->getFirst(e.in, e.v); marci@148: while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } marci@148: } marci@148: } marci@148: } else { marci@148: ++(e.in); marci@148: while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } marci@148: while (G->valid(e.v) && !G->valid(e.in)) { marci@148: ++(e.v); marci@148: if (G->valid(e.v)) G->getFirst(e.in, e.v); marci@148: while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); } marci@148: } marci@148: } marci@148: return e; marci@148: } marci@75: marci@148: marci@75: template< typename It > marci@75: 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 { marci@148: return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); } marci@75: NodeIt head(EdgeIt e) const { marci@148: return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); } marci@75: marci@75: NodeIt aNode(OutEdgeIt e) const { marci@148: return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); } marci@75: NodeIt bNode(OutEdgeIt e) const { marci@148: return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); } marci@75: marci@148: int id(NodeIt v) const { return G->id(v); } marci@148: marci@148: bool valid(NodeIt n) const { return G->valid(n); } marci@148: bool valid(EdgeIt e) const { marci@148: return e.out_or_in ? G->valid(e.out) : G->valid(e.in); } marci@75: marci@137: template marci@75: class NodeMap { marci@137: typename Graph::NodeMap node_map; marci@75: public: marci@148: NodeMap(const ResGraphWrapper& _G) : node_map(*(_G.G)) { } marci@148: NodeMap(const ResGraphWrapper& _G, T a) : node_map(*(_G.G), a) { } marci@137: void set(NodeIt nit, T a) { node_map.set(nit, a); } marci@137: T get(NodeIt nit) const { return node_map.get(nit); } marci@137: }; marci@137: marci@137: template marci@137: class EdgeMap { marci@137: typename Graph::EdgeMap forward_map, backward_map; marci@137: public: marci@148: EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { } marci@148: EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { } marci@137: void set(EdgeIt e, T a) { marci@137: if (e.out_or_in) marci@137: forward_map.set(e.out, a); marci@137: else marci@137: backward_map.set(e.in, a); marci@137: } marci@137: T get(EdgeIt e) { marci@137: if (e.out_or_in) marci@137: return forward_map.get(e.out); marci@137: else marci@137: return backward_map.get(e.in); marci@137: } marci@43: }; marci@43: marci@43: }; 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@75: template marci@75: class MaxFlow2 { klao@127: public: marci@75: typedef typename Graph::NodeIt NodeIt; marci@75: typedef typename Graph::EdgeIt EdgeIt; marci@75: typedef typename Graph::EachEdgeIt EachEdgeIt; marci@75: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@75: typedef typename Graph::InEdgeIt InEdgeIt; klao@127: private: marci@75: const Graph& G; marci@75: std::list& S; marci@75: std::list& T; marci@75: FlowMap& flow; marci@75: const CapacityMap& capacity; marci@75: typedef ResGraph AugGraph; marci@75: typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; marci@75: typedef typename AugGraph::EdgeIt AugEdgeIt; marci@75: typename Graph::NodeMap SMap; marci@75: typename Graph::NodeMap TMap; marci@75: public: marci@75: 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@75: for(typename std::list::const_iterator i=S.begin(); marci@75: i!=S.end(); ++i) { marci@75: SMap.set(*i, true); marci@75: } marci@75: for (typename std::list::const_iterator i=T.begin(); marci@75: i!=T.end(); ++i) { marci@75: TMap.set(*i, true); marci@75: } marci@75: } marci@75: bool augment() { marci@75: AugGraph res_graph(G, flow, capacity); marci@75: bool _augment=false; marci@75: NodeIt reached_t_node; marci@75: marci@75: typedef typename AugGraph::NodeMap ReachedMap; marci@75: BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); marci@75: for(typename std::list::const_iterator i=S.begin(); marci@75: i!=S.end(); ++i) { marci@75: res_bfs.pushAndSetReached(*i); marci@75: } marci@75: //res_bfs.pushAndSetReached(s); marci@75: marci@75: typename AugGraph::NodeMap pred(res_graph); marci@75: //filled up with invalid iterators marci@75: marci@133: typename AugGraph::NodeMap free(res_graph); marci@75: marci@75: //searching for augmenting path marci@75: while ( !res_bfs.finished() ) { marci@141: AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); marci@75: if (e.valid() && res_bfs.isBNodeNewlyReached()) { marci@75: NodeIt v=res_graph.tail(e); marci@75: NodeIt w=res_graph.head(e); marci@75: pred.set(w, e); marci@75: if (pred.get(v).valid()) { marci@75: free.set(w, std::min(free.get(v), e.free())); marci@75: } else { marci@75: free.set(w, e.free()); marci@75: } marci@75: if (TMap.get(res_graph.head(e))) { marci@75: _augment=true; marci@75: reached_t_node=res_graph.head(e); marci@75: break; marci@75: } marci@75: } marci@75: marci@75: ++res_bfs; marci@75: } //end of searching augmenting path marci@75: marci@75: if (_augment) { marci@75: NodeIt n=reached_t_node; marci@75: Number augment_value=free.get(reached_t_node); marci@75: while (pred.get(n).valid()) { marci@75: AugEdgeIt e=pred.get(n); marci@75: e.augment(augment_value); marci@75: n=res_graph.tail(e); marci@75: } marci@75: } marci@75: marci@75: return _augment; marci@75: } marci@75: void run() { marci@75: while (augment()) { } marci@75: } marci@75: Number flowValue() { marci@75: Number a=0; marci@75: for(typename std::list::const_iterator i=S.begin(); marci@75: i!=S.end(); ++i) { marci@75: for(OutEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@75: a+=flow.get(e); marci@75: } marci@75: for(InEdgeIt e=G.template first(*i); e.valid(); ++e) { marci@75: a-=flow.get(e); marci@75: } marci@75: } marci@75: return a; marci@75: } marci@75: }; marci@75: marci@75: marci@75: alpar@107: } // namespace hugo marci@43: marci@59: #endif //EDMONDS_KARP_HH