#ifndef MARCI_MAX_FLOW_HH

 #define MARCI_MAX_FLOW_HH

 #include <algorithm>

 #include <marci_property_vector.hh>

 #include <marci_bfs.hh>

 namespace marci {

   template<typename graph_type, typename T>

   class res_graph_type { 

     typedef typename graph_type::node_iterator node_iterator;

     typedef typename graph_type::each_node_iterator each_node_iterator;

     typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;

     graph_type& G;

     edge_property_vector<graph_type, T>& flow;

     edge_property_vector<graph_type, T>& capacity;

   public:

     res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { }

     class edge_iterator {

       friend class res_graph_type<graph_type, T>;

     protected:

       res_graph_type<graph_type, T>* resG;

       old_sym_edge_iterator sym;

     public:

       edge_iterator() { }

       //bool is_free() {  

       //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 

       //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 

       //} else { 

       //  return (resG->flow.get(sym)>0); 

       //}

       //}

       T free() { 

 	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 

 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 

 	} else { 

 	  return (resG->flow.get(sym)); 

 	}

       }

       bool valid() { return sym.valid(); }

       void make_invalid() { sym.make_invalid(); }

       void augment(T a) {

 	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 

 	  resG->flow.put(sym, resG->flow.get(sym)+a);

 	} else { 

 	  resG->flow.put(sym, resG->flow.get(sym)-a);

 	}

       }

     };

     class out_edge_iterator : public edge_iterator {

     public:

       out_edge_iterator() { }

       out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 

       	resG=&_resG;

 	sym=resG->G.first_sym_edge(v);

 	while( sym.valid() && !(free()>0) ) { ++sym; }

       }

       out_edge_iterator& operator++() { 

 	++sym; 

 	while( sym.valid() && !(free()>0) ) { ++sym; }

 	return *this; 

       }

     };

     out_edge_iterator first_out_edge(const node_iterator& v) {

       return out_edge_iterator(*this, v);

     }

     each_node_iterator first_node() {

       return G.first_node();

     }

     node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }

     node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }

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

     //node_iterator invalid_node() { return G.invalid_node(); }

     //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } 

   };

   template <typename graph_type, typename T>

   struct max_flow_type {

     typedef typename graph_type::node_iterator node_iterator;

     typedef typename graph_type::edge_iterator edge_iterator;

     typedef typename graph_type::each_node_iterator each_node_iterator;

     typedef typename graph_type::out_edge_iterator out_edge_iterator;

     typedef typename graph_type::in_edge_iterator in_edge_iterator;

     graph_type& G;

     node_iterator s;

     node_iterator t;

     edge_property_vector<graph_type, T> flow;

     edge_property_vector<graph_type, T>& capacity;

     max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 

       for(each_node_iterator i=G.first_node(); i.valid(); ++i) 

 	for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) 

 	  flow.put(j, 0);

     }

     void run() {

       typedef res_graph_type<graph_type, T> aug_graph_type;

       aug_graph_type res_graph(G, flow, capacity);

       bool augment;

       do {

 	augment=false;

 	typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;

 	bfs_queue_type bfs_queue;

 	bfs_queue.push(res_graph.first_out_edge(s));

 	typedef node_property_vector<aug_graph_type, bool> reached_type;

 	reached_type reached(res_graph, false);

 	reached.put(s, true); 

 	bfs_iterator1< aug_graph_type, reached_type > 

 	res_bfs(res_graph, bfs_queue, reached);

 	typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;

 	pred_type pred(res_graph);

 	aug_graph_type::edge_iterator a; 

 	a.make_invalid();

 	pred.put(s, a);

 	typedef node_property_vector<aug_graph_type, int> free_type;

 	free_type 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()) {

 	    aug_graph_type::edge_iterator e;

 	    e=res_bfs;

 	    node_iterator v=res_graph.tail(e);

 	    node_iterator w=res_graph.head(e);

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

 	    pred.put(w, e);

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

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

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

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

 	    } else {

 	      free.put(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;

 	}

 	if (reached.get(t)) {

 	  augment=true;

 	  node_iterator n=t;

 	  T augment_value=free.get(t);

 	  std::cout<<"augmentation: ";

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

 	    aug_graph_type::edge_iterator 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(typename graph_type::each_edge_iterator e=G.first_edge(); 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