marci@59: #ifndef EDMONDS_KARP_HH
marci@59: #define EDMONDS_KARP_HH
marci@43: 
marci@43: #include <algorithm>
marci@43: 
marci@43: #include <bfs_iterator.hh>
marci@43: 
marci@43: namespace marci {
marci@43: 
marci@59:   template<typename Graph, typename T, 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@59:       friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
marci@43:     protected:
marci@59:       const ResGraph<Graph, T, 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@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<Graph, T, FlowMap, CapacityMap>;
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<Graph, T, 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@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@43:     template <typename ValueType>
marci@43:     class NodeMap {
marci@43:       typename Graph::NodeMap<ValueType> node_map; 
marci@43:     public:
marci@59:       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
marci@64:       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { }
marci@64:       void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
marci@64:       ValueType get(NodeIt nit) const { return node_map.get(nit); }
marci@43:     };
marci@43: 
marci@43:   };
marci@43: 
marci@59:   template <typename Graph, typename T, 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@59:     typedef ResGraph<Graph, T, FlowMap, CapacityMap > 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<bool> ReachedMap;
marci@59:       BfsIterator2< 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@59:       //filled with invalid iterators
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: 	//std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
marci@59: 	//while (!bfs_copy.empty()) {
marci@59: 	//  AugOutEdgeIt e=bfs_copy.front();
marci@59: 	//  bfs_copy.pop();
marci@59: 	//  if (e.valid()) {
marci@59: 	//    std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
marci@59: 	//  } else {
marci@59: 	//    std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
marci@59: 	//  }
marci@59: 	//}
marci@59: 	//std::cout<<std::endl;
marci@59: 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
marci@59: 	//if (e.valid()) {
marci@59: 	//  std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
marci@59: 	//} else {
marci@59: 	//  std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
marci@59: 	//}
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: 	  //std::cout<<v<<"->"<<w<<std::endl;
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: 	//std::cout<<"augmentation: ";
marci@59: 	while (pred.get(n).valid()) { 
marci@59: 	  AugEdgeIt e=pred.get(n);
marci@59: 	  e.augment(augment_value); 
marci@59: 	  //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
marci@59: 	  n=res_graph.tail(e);
marci@59: 	}
marci@59: 	//std::cout<<std::endl;
marci@59:       }
marci@59:       //std::cout << "actual flow: "<< std::endl;
marci@59:       //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
marci@59:       //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@59:       //}
marci@59:       //std::cout<<std::endl;
marci@59: 
marci@59:       return _augment;
marci@59:     }
marci@43:     void run() {
marci@59:       while (augment()) { } 
marci@43:     }
marci@43:   };
marci@43: 
marci@43: } // namespace marci
marci@43: 
marci@59: #endif //EDMONDS_KARP_HH