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: alpar@107: namespace hugo { marci@9: marci@9: template marci@9: class res_graph_type { marci@19: typedef typename graph_type::node_iterator node_iterator; marci@19: typedef typename graph_type::each_node_iterator each_node_iterator; marci@19: typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator; 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@19: class edge_iterator { marci@9: friend class res_graph_type; marci@9: protected: marci@9: res_graph_type* resG; marci@19: old_sym_edge_iterator sym; marci@9: public: marci@19: edge_iterator() { } 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@19: bool valid() { return sym.valid(); } marci@17: void make_invalid() { sym.make_invalid(); } 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@19: class out_edge_iterator : public edge_iterator { marci@9: public: marci@19: out_edge_iterator() { } marci@19: out_edge_iterator(res_graph_type& _resG, const node_iterator& v) { marci@9: resG=&_resG; marci@9: sym=resG->G.first_sym_edge(v); marci@19: while( sym.valid() && !(free()>0) ) { ++sym; } marci@9: } marci@19: out_edge_iterator& operator++() { marci@9: ++sym; marci@19: while( sym.valid() && !(free()>0) ) { ++sym; } marci@9: return *this; marci@9: } marci@9: }; marci@9: marci@19: out_edge_iterator first_out_edge(const node_iterator& v) { marci@19: return out_edge_iterator(*this, v); marci@9: } marci@9: marci@9: each_node_iterator first_node() { marci@9: return G.first_node(); marci@9: } marci@9: marci@19: node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); } marci@19: node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); } marci@9: marci@9: int id(const node_iterator& v) { return G.id(v); } marci@9: marci@17: //node_iterator invalid_node() { return G.invalid_node(); } marci@19: //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } marci@9: }; marci@9: marci@9: template marci@9: struct max_flow_type { marci@19: typedef typename graph_type::node_iterator node_iterator; marci@19: typedef typename graph_type::edge_iterator edge_iterator; marci@19: typedef typename graph_type::each_node_iterator each_node_iterator; marci@19: typedef typename graph_type::out_edge_iterator out_edge_iterator; marci@19: typedef typename graph_type::in_edge_iterator in_edge_iterator; 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@19: for(each_node_iterator i=G.first_node(); i.valid(); ++i) marci@19: for(out_edge_iterator j=G.first_out_edge(i); j.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@19: typedef std::queue 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, 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@19: typedef node_property_vector pred_type; marci@14: pred_type pred(res_graph); marci@19: aug_graph_type::edge_iterator a; marci@17: a.make_invalid(); marci@17: pred.put(s, a); 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@19: while ( res_bfs.valid() ) { marci@14: //std::cout<<"KULSO ciklus itt jar: "<"<"<"<"<