marci@9: #ifndef MARCI_MAX_FLOW_HH
marci@9: #define MARCI_MAX_FLOW_HH
marci@9: 
marci@9: #include <algorithm>
marci@9: 
marci@9: #include <marci_graph_traits.hh>
marci@9: #include <marci_property_vector.hh>
marci@9: #include <marci_bfs.hh>
marci@9: 
marci@9: namespace marci {
marci@9: 
marci@9:   template<typename graph_type, typename T>
marci@9:   class res_graph_type { 
marci@9:     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
marci@9:     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
marci@9:     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
marci@9:     typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
marci@9: 
marci@9:     graph_type& G;
marci@9:     edge_property_vector<graph_type, T>& flow;
marci@9:     edge_property_vector<graph_type, T>& capacity;
marci@9:   public:
marci@9:     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) { }
marci@9: 
marci@9:     class res_edge_it {
marci@9:       friend class res_graph_type<graph_type, T>;
marci@9:     protected:
marci@9:       res_graph_type<graph_type, T>* resG;
marci@9:       sym_edge_iterator sym;
marci@9:     public:
marci@9:       res_edge_it() { }
marci@9:       //bool is_free() {  
marci@9:       //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
marci@9:       //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 
marci@9:       //} else { 
marci@9:       //  return (resG->flow.get(sym)>0); 
marci@9:       //}
marci@9:       //}
marci@9:       T free() { 
marci@9: 	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
marci@9: 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
marci@9: 	} else { 
marci@9: 	  return (resG->flow.get(sym)); 
marci@9: 	}
marci@9:       }
marci@9:       bool is_valid() { return sym.is_valid(); }
marci@9:       void augment(T a) {
marci@9: 	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
marci@9: 	  resG->flow.put(sym, resG->flow.get(sym)+a);
marci@9: 	} else { 
marci@9: 	  resG->flow.put(sym, resG->flow.get(sym)-a);
marci@9: 	}
marci@9:       }
marci@9:     };
marci@9: 
marci@9:     class res_out_edge_it : public res_edge_it {
marci@9:     public:
marci@9:       res_out_edge_it() { }
marci@9:       res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 
marci@9:       	resG=&_resG;
marci@9: 	sym=resG->G.first_sym_edge(v);
marci@9: 	while( sym.is_valid() && !(free()>0) ) { ++sym; }
marci@9:       }
marci@9:       res_out_edge_it& operator++() { 
marci@9: 	++sym; 
marci@9: 	while( sym.is_valid() && !(free()>0) ) { ++sym; }
marci@9: 	return *this; 
marci@9:       }
marci@9:     };
marci@9: 
marci@9:     res_out_edge_it first_out_edge(const node_iterator& v) {
marci@9:       return res_out_edge_it(*this, v);
marci@9:     }
marci@9: 
marci@9:     each_node_iterator first_node() {
marci@9:       return G.first_node();
marci@9:     }
marci@9: 
marci@9:     node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
marci@9:     node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
marci@9: 
marci@9:     int id(const node_iterator& v) { return G.id(v); }
marci@9: 
marci@9:     node_iterator invalid_node() { return G.invalid_node(); }
marci@9:     res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
marci@9:     
marci@9:   };
marci@9: 
marci@9:   template <typename graph_type, typename T>
marci@9:   struct graph_traits< res_graph_type<graph_type, T> > {
marci@9:     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
marci@9:     typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
marci@9:     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
marci@9:     typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
marci@9:   };
marci@9: 
marci@9:   template <typename graph_type, typename pred_type, typename free_type>
marci@9:   struct flow_visitor {
marci@9:     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
marci@9:     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
marci@9:     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
marci@9:     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
marci@9:     graph_type& G;
marci@9:     pred_type& pred;
marci@9:     free_type& free;
marci@9:     flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
marci@9:     void at_previously_reached(out_edge_iterator& e) { 
marci@9:       //node_iterator v=G.tail(e);
marci@9:       //node_iterator w=G.head(e);
marci@9:       //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
marci@9:       //std::cout<<std::endl;
marci@9:    }
marci@9:     void at_newly_reached(out_edge_iterator& e) { 
marci@9:       node_iterator v=G.tail(e);
marci@9:       node_iterator w=G.head(e);
marci@9:       //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
marci@9:       pred.put(w, e);
marci@9:       if (pred.get(v).is_valid()) {
marci@9: 	free.put(w, std::min(free.get(v), e.free()));
marci@9: 	//std::cout <<" nem elso csucs: ";
marci@9: 	//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
marci@9:       } else {
marci@9: 	free.put(w, e.free()); 
marci@9: 	//std::cout <<" elso csucs: ";
marci@9: 	//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
marci@9:       }
marci@9:       //std::cout<<std::endl;
marci@9:     }
marci@9:   };
marci@9: 
marci@9:   template <typename graph_type, typename T>
marci@9:   struct max_flow_type {
marci@9:     
marci@9:     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
marci@9:     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
marci@9:     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
marci@9:     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
marci@9:     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
marci@9: 
marci@9:     graph_type& G;
marci@9:     node_iterator s;
marci@9:     node_iterator t;
marci@9:     edge_property_vector<graph_type, T> flow;
marci@9:     edge_property_vector<graph_type, T>& capacity;
marci@9: 
marci@9:     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) { 
marci@9:       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) 
marci@9: 	for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) 
marci@9: 	  flow.put(j, 0);
marci@9:     }
marci@9:     void run() {
marci@9:       typedef res_graph_type<graph_type, T> aug_graph_type;
marci@9:       aug_graph_type res_graph(G, flow, capacity);
marci@9: 
marci@9:       typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
marci@9:       bfs_queue_type bfs_queue;
marci@9:       //bfs_queue.push(res_graph.first_out_edge(s));
marci@9: 
marci@9:       typedef node_property_vector<aug_graph_type, bool> reached_type;
marci@9:       //reached_type reached(res_graph, false);
marci@9:       reached_type reached(res_graph);
marci@9:       //reached.put(s, true);
marci@9: 
marci@9:       typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
marci@9:       pred_type pred(res_graph);
marci@9:       pred.put(s, res_graph.invalid_edge());
marci@9:       
marci@9:       typedef node_property_vector<aug_graph_type, int> free_type;
marci@9:       free_type free(res_graph);
marci@9: 
marci@9:       typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
marci@9:       visitor_type vis(res_graph, pred, free);
marci@9:       
marci@9:       bfs_iterator< aug_graph_type, reached_type, visitor_type > 
marci@9: 	res_bfs(res_graph, bfs_queue, reached, vis);
marci@9: 
marci@9:       //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { 
marci@9:       //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
marci@9:       //  std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
marci@9:       //}
marci@9:       //}
marci@9:       //std::cout<<std::endl;
marci@9: 
marci@9:       //char c; 
marci@9:       bool augment;
marci@9:       do {
marci@9: 	augment=false;
marci@9: 	
marci@9: 	while (!bfs_queue.empty()) { bfs_queue.pop(); }
marci@9: 	bfs_queue.push(res_graph.first_out_edge(s));
marci@9: 	
marci@9: 	for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
marci@9: 	reached.put(s, true); 
marci@9: 	
marci@9: 	//searching for augmenting path
marci@9: 	while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { 
marci@9: 	  res_bfs.process(); 
marci@9: 	  //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
marci@9: 	  if (res_graph.head(res_bfs)==t) break;
marci@9: 	  //res_bfs.next();
marci@9: 	  ++res_bfs;
marci@9: 	}
marci@9: 	//for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); } 
marci@9: 	if (reached.get(t)) {
marci@9: 	  augment=true;
marci@9: 	  node_iterator n=t;
marci@9: 	  T augment_value=free.get(t);
marci@9: 	  std::cout<<"augmentation: ";
marci@9: 	  while (pred.get(n).is_valid()) { 
marci@9: 	    graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
marci@9: 	    e.augment(augment_value); 
marci@9: 	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
marci@9: 	    n=res_graph.tail(e);
marci@9: 	  }
marci@9: 	  std::cout<<std::endl;
marci@9: 	}
marci@9: 
marci@9: 	std::cout << "max flow:"<< std::endl;
marci@9: 	for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { 
marci@9: 	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@9: 	}
marci@9: 	std::cout<<std::endl;
marci@9: 
marci@9:       } while (augment);
marci@9:     }
marci@9:   };
marci@9: 
marci@9: } // namespace marci
marci@9: 
marci@9: #endif //MARCI_MAX_FLOW_HH