#ifndef EDMONDS_KARP_HH
#define EDMONDS_KARP_HH

#include <algorithm>

#include <bfs_iterator.hh>

namespace marci {

  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
  class ResGraph {
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EachNodeIt EachNodeIt;
    typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    const Graph& G;
    FlowMap& flow;
    const CapacityMap& capacity;
  public:
    ResGraph(const Graph& _G, FlowMap& _flow, 
	     const CapacityMap& _capacity) : 
      G(_G), flow(_flow), capacity(_capacity) { }

    class EdgeIt; 
    class OutEdgeIt; 
    friend class EdgeIt; 
    friend class OutEdgeIt; 

    class EdgeIt {
      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
    protected:
      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
      OldSymEdgeIt sym;
    public:
      EdgeIt() { } 
      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
      T free() const { 
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
	} else { 
	  return (resG->flow.get(sym)); 
	}
      }
      bool valid() const { return sym.valid(); }
      void augment(T a) const {
	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
	  resG->flow.set(sym, resG->flow.get(sym)+a);
	} else { 
	  resG->flow.set(sym, resG->flow.get(sym)-a);
	}
      }
    };

    class OutEdgeIt : public EdgeIt {
      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
    public:
      OutEdgeIt() { }
      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    private:
      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) { 
      	resG=&_resG;
	sym=resG->G.template first<OldSymEdgeIt>(v);
	while( sym.valid() && !(free()>0) ) { ++sym; }
      }
    public:
      OutEdgeIt& operator++() { 
	++sym; 
	while( sym.valid() && !(free()>0) ) { ++sym; }
	return *this; 
      }
    };

    void getFirst(OutEdgeIt& e, NodeIt v) const { 
      e=OutEdgeIt(*this, v); 
    }
    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
    
    template< typename It >
    It first() const { 
      It e;
      getFirst(e);
      return e; 
    }

    template< typename It >
    It first(NodeIt v) const { 
      It e;
      getFirst(e, v);
      return e; 
    }

    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }

    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }

    int id(NodeIt v) const { return G.id(v); }

    template <typename S>
    class NodeMap {
      typename Graph::NodeMap<S> node_map; 
    public:
      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
      void set(NodeIt nit, S a) { node_map.set(nit, a); }
      S get(NodeIt nit) const { return node_map.get(nit); }
    };

  };

  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
  class MaxFlow {
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::EachEdgeIt EachEdgeIt;
    typedef typename Graph::OutEdgeIt OutEdgeIt;
    typedef typename Graph::InEdgeIt InEdgeIt;
    const Graph& G;
    NodeIt s;
    NodeIt t;
    FlowMap& flow;
    const CapacityMap& capacity;
    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    typedef typename AugGraph::EdgeIt AugEdgeIt;
  public:
    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
    bool augment() {
      AugGraph res_graph(G, flow, capacity);
      bool _augment=false;
      
      typedef typename AugGraph::NodeMap<bool> ReachedMap;
      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
      res_bfs.pushAndSetReached(s);
	
      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
      //filled with invalid iterators
      
      typename AugGraph::NodeMap<int> free(res_graph);
	
      //searching for augmenting path
      while ( !res_bfs.finished() ) { 
	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
	if (e.valid() && res_bfs.isBNodeNewlyReached()) {
	  NodeIt v=res_graph.tail(e);
	  NodeIt w=res_graph.head(e);
	  pred.set(w, e);
	  if (pred.get(v).valid()) {
	    free.set(w, std::min(free.get(v), e.free()));
	  } else {
	    free.set(w, e.free()); 
	  }
	  if (res_graph.head(e)==t) { _augment=true; break; }
	}
	
	++res_bfs;
      } //end of searching augmenting path

      if (_augment) {
	NodeIt n=t;
	T augment_value=free.get(t);
	while (pred.get(n).valid()) { 
	  AugEdgeIt e=pred.get(n);
	  e.augment(augment_value); 
	  n=res_graph.tail(e);
	}
      }

      return _augment;
    }
    void run() {
      while (augment()) { } 
    }
    T flowValue() { 
      T a=0;
      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
	a+=flow.get(i);
      }
      return a;
    }
  };

} // namespace marci

#endif //EDMONDS_KARP_HH