#ifndef MARCI_MAX_FLOW_HH

 #define MARCI_MAX_FLOW_HH

 #include <algorithm>

 #include <bfs_iterator.hh>

 namespace marci {

   template<typename Graph, typename T>

   class ResGraph {

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::EachNodeIt EachNodeIt;

     typedef typename Graph::SymEdgeIt OldSymEdgeIt;

     const Graph& G;

     typename Graph::EdgeMap<T>& flow;

     const typename Graph::EdgeMap<T>& capacity;

   public:

     ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow, 

 	     const typename Graph::EdgeMap<T>& _capacity) : 

       G(_G), flow(_flow), capacity(_capacity) { }

     class EdgeIt; 

     class OutEdgeIt; 

     friend class EdgeIt; 

     friend class OutEdgeIt; 

     class EdgeIt {

       friend class ResGraph<Graph, T>;

     protected:

       const ResGraph<Graph, T>* 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(const 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>;

     public:

       OutEdgeIt() { }

       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }

     private:

       OutEdgeIt(const ResGraph<Graph, T>& _resG, const 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, const 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(const NodeIt v) const { 

       It e;

       getFirst(e, v);

       return e; 

     }

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

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

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

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

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

     template <typename ValueType>

     class NodeMap {

       //const ResGraph<Graph, T>& G; 

       typename Graph::NodeMap<ValueType> node_map; 

     public:

       NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }

       NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }

       void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }

       ValueType get(const NodeIt nit) const { return node_map.get(nit); }

     };

   };

   template <typename Graph, typename T>

   struct max_flow_type {

     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;

     typename Graph::EdgeMap<T> flow;

     const typename Graph::EdgeMap<T>& capacity;

     max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }

     void run() {

       typedef ResGraph<Graph, T> AugGraph;

       AugGraph res_graph(G, flow, capacity);

       bool augment;

       do {

 	augment=false;

 	typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;

 	typedef typename AugGraph::EdgeIt AugEdgeIt;

 	typedef std::queue<AugOutEdgeIt> BfsQueue;

 	BfsQueue bfs_queue;

 	bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));

 	typedef typename AugGraph::NodeMap<bool> ReachedMap;

 	ReachedMap reached(res_graph, false);

 	reached.set(s, true); 

 	bfs_iterator1< AugGraph, ReachedMap > 

 	res_bfs(res_graph, bfs_queue, reached);

 	typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;

 	PredMap pred(res_graph);

 	//typename AugGraph::EdgeIt a; //invalid

 	//a.makeInvalid();

 	//pred.set(s, a);

 	typedef typename AugGraph::NodeMap<int> FreeMap;

 	FreeMap free(res_graph);

 	//searching for augmenting path

 	while ( res_bfs.valid() ) { 

 	  //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;

 	  if (res_bfs.newly_reached()) {

 	    AugOutEdgeIt e=AugOutEdgeIt(res_bfs);

 	    NodeIt v=res_graph.tail(e);

 	    NodeIt w=res_graph.head(e);

 	    //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";

 	    pred.set(w, e);

 	    if (pred.get(v).valid()) {

 	      free.set(w, std::min(free.get(v), e.free()));

 	      //std::cout <<" nem elso csucs: ";

 	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";

 	    } else {

 	      free.set(w, e.free()); 

 	      //std::cout <<" elso csucs: ";

 	      //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";

 	    }

 	    //std::cout<<std::endl;

 	  }

 	  if (res_graph.head(res_bfs)==t) break;

 	  ++res_bfs;

 	} //end searching augmenting path

 	if (reached.get(t)) {

 	  augment=true;

 	  NodeIt n=t;

 	  T augment_value=free.get(t);

 	  std::cout<<"augmentation: ";

 	  while (pred.get(n).valid()) { 

 	    AugEdgeIt e=pred.get(n);

 	    e.augment(augment_value); 

 	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";

 	    n=res_graph.tail(e);

 	  }

 	  std::cout<<std::endl;

 	}

 	std::cout << "actual flow: "<< std::endl;

 	for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 

 	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";

 	}

 	std::cout<<std::endl;

       } while (augment);

     }

   };

 } // namespace marci

 #endif //MARCI_MAX_FLOW_HH