marci@280: #ifndef MARCI_MAX_FLOW_HH marci@280: #define MARCI_MAX_FLOW_HH marci@280: marci@280: #include <algorithm> marci@280: marci@280: #include <marci_property_vector.hh> marci@280: #include <marci_bfs.hh> marci@280: marci@280: namespace hugo { marci@280: marci@280: template<typename graph_type, typename T> marci@280: class res_graph_type { marci@280: typedef typename graph_type::node_iterator node_iterator; marci@280: typedef typename graph_type::each_node_iterator each_node_iterator; marci@280: typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator; marci@280: graph_type& G; marci@280: edge_property_vector<graph_type, T>& flow; marci@280: edge_property_vector<graph_type, T>& capacity; marci@280: public: marci@280: 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@280: marci@280: class edge_iterator { marci@280: friend class res_graph_type<graph_type, T>; marci@280: protected: marci@280: res_graph_type<graph_type, T>* resG; marci@280: old_sym_edge_iterator sym; marci@280: public: marci@280: edge_iterator() { } marci@280: //bool is_free() { marci@280: //if (resG->G.a_node(sym)==resG->G.tail(sym)) { marci@280: // return (resG->flow.get(sym)<resG->capacity.get(sym)); marci@280: //} else { marci@280: // return (resG->flow.get(sym)>0); marci@280: //} marci@280: //} marci@280: T free() { marci@280: if (resG->G.a_node(sym)==resG->G.tail(sym)) { marci@280: return (resG->capacity.get(sym)-resG->flow.get(sym)); marci@280: } else { marci@280: return (resG->flow.get(sym)); marci@280: } marci@280: } marci@280: bool valid() { return sym.valid(); } marci@280: void make_invalid() { sym.make_invalid(); } marci@280: void augment(T a) { marci@280: if (resG->G.a_node(sym)==resG->G.tail(sym)) { marci@280: resG->flow.put(sym, resG->flow.get(sym)+a); marci@280: } else { marci@280: resG->flow.put(sym, resG->flow.get(sym)-a); marci@280: } marci@280: } marci@280: }; marci@280: marci@280: class out_edge_iterator : public edge_iterator { marci@280: public: marci@280: out_edge_iterator() { } marci@280: out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { marci@280: resG=&_resG; marci@280: sym=resG->G.first_sym_edge(v); marci@280: while( sym.valid() && !(free()>0) ) { ++sym; } marci@280: } marci@280: out_edge_iterator& operator++() { marci@280: ++sym; marci@280: while( sym.valid() && !(free()>0) ) { ++sym; } marci@280: return *this; marci@280: } marci@280: }; marci@280: marci@280: out_edge_iterator first_out_edge(const node_iterator& v) { marci@280: return out_edge_iterator(*this, v); marci@280: } marci@280: marci@280: each_node_iterator first_node() { marci@280: return G.first_node(); marci@280: } marci@280: marci@280: node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); } marci@280: node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); } marci@280: marci@280: int id(const node_iterator& v) { return G.id(v); } marci@280: marci@280: //node_iterator invalid_node() { return G.invalid_node(); } marci@280: //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } marci@280: }; marci@280: marci@280: template <typename graph_type, typename T> marci@280: struct max_flow_type { marci@280: typedef typename graph_type::node_iterator node_iterator; marci@280: typedef typename graph_type::edge_iterator edge_iterator; marci@280: typedef typename graph_type::each_node_iterator each_node_iterator; marci@280: typedef typename graph_type::out_edge_iterator out_edge_iterator; marci@280: typedef typename graph_type::in_edge_iterator in_edge_iterator; marci@280: graph_type& G; marci@280: node_iterator s; marci@280: node_iterator t; marci@280: edge_property_vector<graph_type, T> flow; marci@280: edge_property_vector<graph_type, T>& capacity; marci@280: marci@280: 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@280: for(each_node_iterator i=G.first_node(); i.valid(); ++i) marci@280: for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) marci@280: flow.put(j, 0); marci@280: } marci@280: void run() { marci@280: typedef res_graph_type<graph_type, T> aug_graph_type; marci@280: aug_graph_type res_graph(G, flow, capacity); marci@280: marci@280: bool augment; marci@280: do { marci@280: augment=false; marci@280: marci@280: typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type; marci@280: bfs_queue_type bfs_queue; marci@280: bfs_queue.push(res_graph.first_out_edge(s)); marci@280: marci@280: typedef node_property_vector<aug_graph_type, bool> reached_type; marci@280: reached_type reached(res_graph, false); marci@280: reached.put(s, true); marci@280: marci@280: bfs_iterator1< aug_graph_type, reached_type > marci@280: res_bfs(res_graph, bfs_queue, reached); marci@280: marci@280: typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type; marci@280: pred_type pred(res_graph); marci@280: aug_graph_type::edge_iterator a; marci@280: a.make_invalid(); marci@280: pred.put(s, a); marci@280: marci@280: typedef node_property_vector<aug_graph_type, int> free_type; marci@280: free_type free(res_graph); marci@280: marci@280: //searching for augmenting path marci@280: while ( res_bfs.valid() ) { marci@280: //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl; marci@280: if (res_bfs.newly_reached()) { marci@280: aug_graph_type::edge_iterator e; marci@280: e=res_bfs; marci@280: node_iterator v=res_graph.tail(e); marci@280: node_iterator w=res_graph.head(e); marci@280: //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; marci@280: pred.put(w, e); marci@280: if (pred.get(v).valid()) { marci@280: free.put(w, std::min(free.get(v), e.free())); marci@280: //std::cout <<" nem elso csucs: "; marci@280: //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; marci@280: } else { marci@280: free.put(w, e.free()); marci@280: //std::cout <<" elso csucs: "; marci@280: //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; marci@280: } marci@280: //std::cout<<std::endl; marci@280: } marci@280: marci@280: if (res_graph.head(res_bfs)==t) break; marci@280: ++res_bfs; marci@280: } marci@280: if (reached.get(t)) { marci@280: augment=true; marci@280: node_iterator n=t; marci@280: T augment_value=free.get(t); marci@280: std::cout<<"augmentation: "; marci@280: while (pred.get(n).valid()) { marci@280: aug_graph_type::edge_iterator e=pred.get(n); marci@280: e.augment(augment_value); marci@280: std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; marci@280: n=res_graph.tail(e); marci@280: } marci@280: std::cout<<std::endl; marci@280: } marci@280: marci@280: std::cout << "actual flow: "<< std::endl; marci@280: for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) { marci@280: std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; marci@280: } marci@280: std::cout<<std::endl; marci@280: marci@280: } while (augment); marci@280: } marci@280: }; marci@280: marci@280: } // namespace hugo marci@280: marci@280: #endif //MARCI_MAX_FLOW_HH