marci@9: #ifndef MARCI_MAX_FLOW_HH marci@9: #define MARCI_MAX_FLOW_HH marci@9: marci@9: #include marci@9: marci@9: #include marci@9: #include marci@9: #include marci@9: marci@9: namespace marci { marci@9: marci@9: template marci@9: class res_graph_type { marci@9: typedef typename graph_traits::node_iterator node_iterator; marci@9: typedef typename graph_traits::edge_iterator edge_iterator; marci@9: typedef typename graph_traits::each_node_iterator each_node_iterator; marci@9: typedef typename graph_traits::sym_edge_iterator sym_edge_iterator; marci@9: marci@9: graph_type& G; marci@9: edge_property_vector& flow; marci@9: edge_property_vector& capacity; marci@9: public: marci@9: res_graph_type(graph_type& _G, edge_property_vector& _flow, edge_property_vector& _capacity) : G(_G), flow(_flow), capacity(_capacity) { } marci@9: marci@9: class res_edge_it { marci@9: friend class res_graph_type; marci@9: protected: marci@9: res_graph_type* 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)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& _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 marci@9: struct graph_traits< res_graph_type > { marci@9: typedef typename graph_traits::node_iterator node_iterator; marci@9: typedef typename res_graph_type::res_edge_it edge_iterator; marci@9: typedef typename graph_traits::each_node_iterator each_node_iterator; marci@9: typedef typename res_graph_type::res_out_edge_it out_edge_iterator; marci@9: }; marci@9: marci@9: template marci@9: struct max_flow_type { marci@9: marci@9: typedef typename graph_traits::node_iterator node_iterator; marci@9: typedef typename graph_traits::edge_iterator edge_iterator; marci@9: typedef typename graph_traits::each_node_iterator each_node_iterator; marci@9: typedef typename graph_traits::out_edge_iterator out_edge_iterator; marci@9: typedef typename graph_traits::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 flow; marci@9: edge_property_vector& capacity; marci@9: marci@9: max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector& _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 aug_graph_type; marci@9: aug_graph_type res_graph(G, flow, capacity); marci@9: marci@9: bool augment; marci@9: do { marci@9: augment=false; marci@14: marci@14: typedef std::queue::out_edge_iterator> bfs_queue_type; marci@14: bfs_queue_type bfs_queue; marci@9: bfs_queue.push(res_graph.first_out_edge(s)); marci@14: marci@14: typedef node_property_vector reached_type; marci@14: //reached_type reached(res_graph); marci@14: //for(graph_traits::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); } marci@14: reached_type reached(res_graph, false); marci@9: reached.put(s, true); marci@9: marci@14: bfs_iterator1< aug_graph_type, reached_type > marci@14: res_bfs(res_graph, bfs_queue, reached); marci@14: marci@14: typedef node_property_vector::edge_iterator> pred_type; marci@14: pred_type pred(res_graph); marci@14: pred.put(s, res_graph.invalid_edge()); marci@14: marci@14: typedef node_property_vector free_type; marci@14: free_type free(res_graph); marci@14: marci@9: //searching for augmenting path marci@14: while ( res_bfs.is_valid() ) { marci@14: //std::cout<<"KULSO ciklus itt jar: "<"<::edge_iterator e; marci@14: e=res_bfs; marci@14: node_iterator v=res_graph.tail(e); marci@14: node_iterator w=res_graph.head(e); marci@14: //std::cout<"<::edge_iterator e=pred.get(n); marci@9: e.augment(augment_value); marci@9: std::cout<<"("<"<::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { marci@9: std::cout<<"("<"<