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@100: #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 {
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@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 {
marci@75:     typedef typename Graph::NodeIt NodeIt;
marci@75:     typedef typename Graph::EachNodeIt EachNodeIt;
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 {
alpar@94: public:
marci@75:     typedef typename Graph::NodeIt NodeIt;
marci@75:     typedef typename Graph::EachNodeIt EachNodeIt;
marci@75:     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
marci@75:     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
marci@75:     typedef typename Graph::InEdgeIt OldInEdgeIt;
marci@75:     
alpar@94: private:
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@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 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@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(G, v, flow, capacity); 
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@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@75:     template <typename S>
marci@75:     class NodeMap {
marci@75:       typename Graph::NodeMap<S> node_map; 
marci@75:     public:
marci@75:       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@75:       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _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@75: 
marci@75:   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
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@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@75:     //typename AugGraph::NodeMap<int> 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@59:     bool augment() {
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@59:       typename AugGraph::NodeMap<int> 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@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@100:     bool augmentWithBlockingFlow() {
marci@100:       BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
marci@100:       bfs.pushAndSetReached(s);
marci@100:       typename Graph::NodeMap<int> dist(G); //filled up with 0's
marci@100:       while ( !bfs.finished() ) { 
marci@100: 	OutEdgeIt e=OutEdgeIt(bfs);
marci@100: 	if (e.valid() && bfs.isBNodeNewlyReached()) {
marci@100: 	  dist.set(G.head(e), dist.get(G.tail(e))+1);
marci@100: 	  //NodeIt v=res_graph.tail(e);
marci@100: 	  //NodeIt w=res_graph.head(e);
marci@100: 	  //pred.set(w, e);
marci@100: 	  //if (pred.get(v).valid()) {
marci@100: 	  //  free.set(w, std::min(free.get(v), e.free()));
marci@100: 	  //} else {
marci@100: 	  //  free.set(w, e.free()); 
marci@100: 	  //}
marci@100: 	  //if (res_graph.head(e)==t) { _augment=true; break; }
marci@100: 	}
marci@100: 	
marci@100: 	++bfs;
marci@100:       } //end of searching augmenting path
marci@100: 
marci@100:       double pre_time_copy=currTime();
marci@100:       typedef Graph MutableGraph;
marci@100:       MutableGraph F;
marci@100:       typename Graph::NodeMap<NodeIt> G_to_F(G);
marci@100:       for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
marci@100: 	G_to_F.set(n, F.addNode());
marci@100:       }
marci@100:       for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
marci@100: 	if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
marci@100: 	  F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
marci@100: 	}
marci@100:       }
marci@100:       double post_time_copy=currTime();
marci@100:       std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl; 
marci@100: 
marci@100:       return 0;
marci@100:     }
marci@43:     void run() {
marci@100:       //int num_of_augmentations=0;
marci@100:       while (augment()) { 
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 {
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;
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@75:       typename AugGraph::NodeMap<int> free(res_graph);
marci@75: 	
marci@75:       //searching for augmenting path
marci@75:       while ( !res_bfs.finished() ) { 
marci@75: 	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