marci@59: #ifndef EDMONDS_KARP_HH
marci@59: #define EDMONDS_KARP_HH
marci@43: 
marci@43: #include <algorithm>
marci@75: #include <list>
marci@75: #include <iterator>
marci@43: 
marci@43: #include <bfs_iterator.hh>
marci@133: //#include <time_measure.h>
marci@43: 
alpar@107: namespace hugo {
marci@43: 
marci@75:   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
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<Graph, Number, FlowMap, CapacityMap>;
marci@43:     protected:
marci@75:       const ResGraph<Graph, Number, FlowMap, CapacityMap>* 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<Graph, Number, FlowMap, CapacityMap>;
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<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
marci@43:       	resG=&_resG;
marci@43: 	sym=resG->G.template first<OldSymEdgeIt>(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 <typename S>
marci@75:     class NodeMap {
marci@75:       typename Graph::NodeMap<S> node_map; 
marci@75:     public:
marci@75:       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@75:       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _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<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
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<Graph, Number, FlowMap, CapacityMap>;
marci@75:     protected:
marci@75:       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
marci@75:       //OldSymEdgeIt sym;
marci@75:       OldOutEdgeIt out;
marci@75:       OldInEdgeIt in;
marci@75:       bool out_or_in; //1, iff out
marci@75:     public:
marci@75:       EdgeIt() : out_or_in(1) { } 
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<Graph, Number, FlowMap, CapacityMap>;
marci@75:     public:
marci@75:       OutEdgeIt() { }
marci@75:     private:
marci@75:       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) { 
marci@75:       	resG=&_resG;
marci@75: 	out=resG->G.template first<OldOutEdgeIt>(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<OldInEdgeIt>(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<OldInEdgeIt>(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 <typename S>
marci@43:     class NodeMap {
marci@69:       typename Graph::NodeMap<S> node_map; 
marci@43:     public:
marci@75:       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@75:       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _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<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
marci@75:   class ResGraph3 {
klao@127:   public:
marci@75:     typedef typename Graph::NodeIt NodeIt;
marci@75:     typedef typename Graph::EachNodeIt EachNodeIt;
klao@127: 
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:     const Graph& G;
marci@75:     FlowMap& flow;
marci@75:     const CapacityMap& capacity;
marci@75:   public:
marci@75:     ResGraph3(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 ResGraph3<Graph, Number, FlowMap, CapacityMap>;
marci@75:     protected:
marci@75:       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* 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@75:       bool out_or_in; //1, iff out
marci@75:     public:
marci@75:       EdgeIt() : out_or_in(1) { } 
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@75:     class OutEdgeIt : public EdgeIt {
marci@75:       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
marci@75:     public:
marci@75:       OutEdgeIt() { }
marci@75:     private:
marci@75:       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) { 
marci@75:       	G=&_G;
marci@75: 	flow=&_flow;
marci@75: 	capacity=&_capacity;
marci@133: 	//out=/*resG->*/G->template first<OldOutEdgeIt>(v);
marci@133: 	G->getFirst(out, v);
marci@75: 	while( out.valid() && !(free()>0) ) { ++out; }
marci@75: 	if (!out.valid()) {
marci@75: 	  out_or_in=0;
marci@133: 	  //in=/*resG->*/G->template first<OldInEdgeIt>(v);
marci@133: 	  G->getFirst(in, 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@133: 	    G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(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@133:     class EachEdgeIt : public EdgeIt {
marci@133:       typename Graph::EachNodeIt v;
marci@133:     public:
marci@133:       EachEdgeIt() { }
marci@133:       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
marci@133:       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) { 
marci@133: 	G=&_G;
marci@133: 	flow=&_flow;
marci@133: 	capacity=&_capacity;
marci@133: 	out_or_in=1;
marci@133: 	G->getFirst(v);
marci@133: 	if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
marci@133: 	while (out.valid() && !(free()>0) ) { ++out; }
marci@133: 	while (v.valid() && !out.valid()) { 
marci@133: 	  ++v; 
marci@133: 	  if (v.valid()) G->getFirst(out, v); 
marci@133: 	  while (out.valid() && !(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@133: 	  while (in.valid() && !(free()>0) ) { ++in; }
marci@133: 	  while (v.valid() && !in.valid()) { 
marci@133: 	    ++v; 
marci@133: 	    if (v.valid()) G->getFirst(in, v); 
marci@133: 	    while (in.valid() && !(free()>0) ) { ++in; }
marci@133: 	  }
marci@133: 	}
marci@133:       }
marci@133:       EachEdgeIt& operator++() { 
marci@133: 	if (out_or_in) {
marci@133: 	  ++out;
marci@133: 	  while (out.valid() && !(free()>0) ) { ++out; }
marci@133: 	  while (v.valid() && !out.valid()) { 
marci@133: 	    ++v; 
marci@133: 	    if (v.valid()) G->getFirst(out, v); 
marci@133: 	    while (out.valid() && !(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@133: 	    while (in.valid() && !(free()>0) ) { ++in; }
marci@133: 	    while (v.valid() && !in.valid()) { 
marci@133: 	      ++v; 
marci@133: 	      if (v.valid()) G->getFirst(in, v); 
marci@133: 	      while (in.valid() && !(free()>0) ) { ++in; }
marci@133: 	    }  
marci@133: 	  }
marci@133: 	} else {
marci@133: 	  ++in;
marci@133: 	  while (in.valid() && !(free()>0) ) { ++in; }
marci@133: 	  while (v.valid() && !in.valid()) { 
marci@133: 	    ++v; 
marci@133: 	    if (v.valid()) G->getFirst(in, v); 
marci@133: 	    while (in.valid() && !(free()>0) ) { ++in; }
marci@133: 	  }
marci@133: 	}
marci@133: 	return *this;
marci@133:       }
marci@133:     };
marci@133: 
marci@75:     void getFirst(OutEdgeIt& e, NodeIt v) const { 
marci@75:       e=OutEdgeIt(G, v, flow, capacity); 
marci@75:     }
marci@133:     void getFirst(EachEdgeIt& e) const { 
marci@133:       e=EachEdgeIt(G, flow, capacity); 
marci@133:     }
marci@75:     void getFirst(EachNodeIt& v) const { G.getFirst(v); }
marci@75:     
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@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@75: 
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@75: 
marci@75:     int id(NodeIt v) const { return G.id(v); }
marci@75: 
marci@137:     template <typename T>
marci@75:     class NodeMap {
marci@137:       typename Graph::NodeMap<T> node_map; 
marci@75:     public:
marci@75:       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@137:       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _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 <typename T>
marci@137:     class EdgeMap {
marci@137:       typename Graph::EdgeMap<T> forward_map, backward_map; 
marci@137:     public:
marci@137:       EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }
marci@137:       EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _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 <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
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@43:     const Graph& G;
marci@64:     NodeIt s;
marci@64:     NodeIt t;
marci@59:     FlowMap& flow;
marci@59:     const CapacityMap& capacity;
marci@75:     typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > 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<bool> ReachedMap;
marci@75:     //typename AugGraph::NodeMap<AugEdgeIt> pred; 
marci@133:     //typename AugGraph::NodeMap<Number> free;
marci@59:   public:
marci@75:     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : 
marci@75:       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@59:       AugGraph res_graph(G, flow, capacity);
marci@59:       bool _augment=false;
marci@59:       
marci@59:       typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@75:       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
marci@59:       res_bfs.pushAndSetReached(s);
marci@59: 	
marci@59:       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
marci@75:       //filled up with invalid iterators
marci@75:       //pred.set(s, AugEdgeIt());
marci@59:       
marci@133:       typename AugGraph::NodeMap<Number> 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@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@75: 	Number 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@141: 
marci@133:     template<typename MutableGraph> bool augmentOnBlockingFlow() {
marci@133:       bool _augment=false;
marci@133: 
marci@133:       AugGraph res_graph(G, flow, capacity);
marci@133: 
marci@133:       typedef typename AugGraph::NodeMap<bool> ReachedMap;
marci@133:       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
marci@133: 
marci@100:       bfs.pushAndSetReached(s);
marci@133:       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
marci@100:       while ( !bfs.finished() ) { 
marci@141: 	AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
marci@100: 	if (e.valid() && 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<NodeIt> res_graph_to_F(res_graph);
marci@133:       for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++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<AugEdgeIt> original_edge(F);
marci@133:       typename MutableGraph::EdgeMap<Number> free_on_edge(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@133:       for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++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@133: 	  free_on_edge.update();
marci@133: 	  free_on_edge.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<bool> BlockingReachedMap;
marci@133: 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
marci@133: 	typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
marci@133: 	typename MutableGraph::NodeMap<Number> free(F);
marci@133: 
marci@133: 	dfs.pushAndSetReached(sF);      
marci@133: 	while (!dfs.finished()) {
marci@133: 	  ++dfs;
marci@133: 	  if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
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@133: 	    if (pred.get(v).valid()) {
marci@133: 	      free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
marci@133: 	    } else {
marci@133: 	      free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/); 
marci@133: 	    }
marci@133: 	    if (w==tF) { 
marci@133: 	      //std::cout << "AUGMENTATION"<<std::endl;
marci@133: 	      __augment=true; 
marci@133: 	      _augment=true;
marci@133: 	      break; 
marci@133: 	    }
marci@133: 	  } else { 
marci@133: 	    //std::cout << "OutEdgeIt: " << "invalid"; 
marci@133: 	    //std::cout << " aNode: " << dfs.aNode(); 
marci@133: 	    //std::cout << " bNode: " << "invalid" << " ";
marci@133: 	  }
marci@133: 	  if (dfs.isBNodeNewlyReached()) { 
marci@133: 	    //std::cout << "bNodeIsNewlyReached ";
marci@133: 	  } else { 
marci@133: 	    //std::cout << "bNodeIsNotNewlyReached ";
marci@133: 	    if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
marci@133: 	      //std::cout << "DELETE ";
marci@133: 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
marci@133: 	    }
marci@133: 	  } 
marci@133: 	  //if (dfs.isANodeExamined()) { 
marci@133: 	    //std::cout << "aNodeIsExamined ";
marci@133: 	    //} else { 
marci@133: 	    //std::cout << "aNodeIsNotExamined ";
marci@133: 	    //} 
marci@133: 	  //std::cout<<std::endl;
marci@100: 	}
marci@133: 
marci@133: 	if (__augment) {
marci@133: 	  typename MutableGraph::NodeIt n=tF;
marci@133: 	  Number augment_value=free.get(tF);
marci@133: 	  while (pred.get(n).valid()) { 
marci@133: 	    typename MutableGraph::EdgeIt e=pred.get(n);
marci@133: 	    original_edge.get(e).augment(augment_value); 
marci@133: 	    n=F.tail(e);
marci@135: 	    if (free_on_edge.get(e)==augment_value) 
marci@135: 	      F.erase(e); 
marci@135: 	    else 
marci@135: 	      free_on_edge.set(e, free_on_edge.get(e)-augment_value);
marci@133: 	  }
marci@133: 	}
marci@135:       
marci@100:       }
marci@133:             
marci@133:       return _augment;
marci@100:     }
marci@43:     void run() {
marci@100:       //int num_of_augmentations=0;
marci@133:       while (augmentOnShortestPath()) { 
marci@133: 	//while (augmentOnBlockingFlow<MutableGraph>()) { 
marci@133: 	//std::cout << ++num_of_augmentations << " ";
marci@133: 	//std::cout<<std::endl;
marci@133:       } 
marci@133:     }
marci@133:     template<typename MutableGraph> void run() {
marci@133:       //int num_of_augmentations=0;
marci@133:       //while (augmentOnShortestPath()) { 
marci@133: 	while (augmentOnBlockingFlow<MutableGraph>()) { 
marci@100: 	//std::cout << ++num_of_augmentations << " ";
marci@100: 	//std::cout<<std::endl;
marci@100:       } 
marci@43:     }
marci@75:     Number flowValue() { 
marci@75:       Number a=0;
marci@69:       for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
marci@69: 	a+=flow.get(i);
marci@69:       }
marci@69:       return a;
marci@69:     }
marci@43:   };
marci@43: 
marci@75: 
marci@75: /*
marci@75:   template <typename Graph>
marci@75:   class IteratorBoolNodeMap {
marci@75:     typedef typename Graph::NodeIt NodeIt;
marci@75:     typedef typename Graph::EachNodeIt EachNodeIt;
marci@75:     class BoolItem {
marci@75:     public:
marci@75:       bool value;
marci@75:       NodeIt prev;
marci@75:       NodeIt next;
marci@75:       BoolItem() : value(false), prev(), next() {}
marci@75:     };
marci@75:     NodeIt first_true;
marci@75:     //NodeIt last_true;
marci@75:     NodeIt first_false;
marci@75:     //NodeIt last_false;
marci@75:     const Graph& G; 
marci@75:     typename Graph::NodeMap<BoolItem> container;
marci@75:   public:
marci@75:     typedef bool ValueType;
marci@75:     typedef NodeIt KeyType;
marci@75:     IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) { 
marci@75:       //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
marci@75:       //BoolItem b=container.get(e);
marci@75:       //b.me=e;
marci@75:       //container.set(b);
marci@75:       //} 
marci@75:       G.getFirst(first_false);
marci@75:       NodeIt e_prev;
marci@75:       for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
marci@75: 	container[e].prev=e_prev;
marci@75: 	if (e_prev.valid()) container[e_prev].next=e;
marci@75: 	e_prev=e;
marci@75:       }
marci@75:     }
marci@75:     //NodeMap(const Graph& _G, T a) : 
marci@75:     //  G(_G), container(G.node_id, a) { }
marci@75:     //FIXME
marci@75:     void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
marci@75:     T get(NodeIt nit) const { return container[G.id(nit)]; }
alpar@107:     //void update() { container.resize(G.node_id); }
alpar@107:     //void update(T a) { container.resize(G.node_id, a); }
marci@75:   };
marci@75: */
marci@75: 
marci@75:   
marci@75:   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
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<NodeIt>& S;
marci@75:     std::list<NodeIt>& T;
marci@75:     FlowMap& flow;
marci@75:     const CapacityMap& capacity;
marci@75:     typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
marci@75:     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
marci@75:     typedef typename AugGraph::EdgeIt AugEdgeIt;
marci@75:     typename Graph::NodeMap<bool> SMap;
marci@75:     typename Graph::NodeMap<bool> TMap;
marci@75:   public:
marci@75:     MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _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<NodeIt>::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<NodeIt>::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<bool> ReachedMap;
marci@75:       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
marci@75:       for(typename std::list<NodeIt>::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<AugEdgeIt> pred(res_graph); 
marci@75:       //filled up with invalid iterators
marci@75:       
marci@133:       typename AugGraph::NodeMap<Number> 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<NodeIt>::const_iterator i=S.begin(); 
marci@75: 	  i!=S.end(); ++i) { 
marci@75: 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
marci@75: 	  a+=flow.get(e);
marci@75: 	}
marci@75: 	for(InEdgeIt e=G.template first<InEdgeIt>(*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