[9] | 1 | #ifndef MARCI_MAX_FLOW_HH |
---|
| 2 | #define MARCI_MAX_FLOW_HH |
---|
| 3 | |
---|
| 4 | #include <algorithm> |
---|
| 5 | |
---|
| 6 | #include <marci_property_vector.hh> |
---|
| 7 | #include <marci_bfs.hh> |
---|
| 8 | |
---|
| 9 | namespace marci { |
---|
| 10 | |
---|
| 11 | template<typename graph_type, typename T> |
---|
| 12 | class res_graph_type { |
---|
[19] | 13 | typedef typename graph_type::node_iterator node_iterator; |
---|
| 14 | typedef typename graph_type::each_node_iterator each_node_iterator; |
---|
| 15 | typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator; |
---|
[9] | 16 | graph_type& G; |
---|
| 17 | edge_property_vector<graph_type, T>& flow; |
---|
| 18 | edge_property_vector<graph_type, T>& capacity; |
---|
| 19 | public: |
---|
| 20 | 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) { } |
---|
| 21 | |
---|
[19] | 22 | class edge_iterator { |
---|
[9] | 23 | friend class res_graph_type<graph_type, T>; |
---|
| 24 | protected: |
---|
| 25 | res_graph_type<graph_type, T>* resG; |
---|
[19] | 26 | old_sym_edge_iterator sym; |
---|
[9] | 27 | public: |
---|
[19] | 28 | edge_iterator() { } |
---|
[9] | 29 | //bool is_free() { |
---|
| 30 | //if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
---|
| 31 | // return (resG->flow.get(sym)<resG->capacity.get(sym)); |
---|
| 32 | //} else { |
---|
| 33 | // return (resG->flow.get(sym)>0); |
---|
| 34 | //} |
---|
| 35 | //} |
---|
| 36 | T free() { |
---|
| 37 | if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
---|
| 38 | return (resG->capacity.get(sym)-resG->flow.get(sym)); |
---|
| 39 | } else { |
---|
| 40 | return (resG->flow.get(sym)); |
---|
| 41 | } |
---|
| 42 | } |
---|
[19] | 43 | bool valid() { return sym.valid(); } |
---|
[17] | 44 | void make_invalid() { sym.make_invalid(); } |
---|
[9] | 45 | void augment(T a) { |
---|
| 46 | if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
---|
| 47 | resG->flow.put(sym, resG->flow.get(sym)+a); |
---|
| 48 | } else { |
---|
| 49 | resG->flow.put(sym, resG->flow.get(sym)-a); |
---|
| 50 | } |
---|
| 51 | } |
---|
| 52 | }; |
---|
| 53 | |
---|
[19] | 54 | class out_edge_iterator : public edge_iterator { |
---|
[9] | 55 | public: |
---|
[19] | 56 | out_edge_iterator() { } |
---|
| 57 | out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { |
---|
[9] | 58 | resG=&_resG; |
---|
| 59 | sym=resG->G.first_sym_edge(v); |
---|
[19] | 60 | while( sym.valid() && !(free()>0) ) { ++sym; } |
---|
[9] | 61 | } |
---|
[19] | 62 | out_edge_iterator& operator++() { |
---|
[9] | 63 | ++sym; |
---|
[19] | 64 | while( sym.valid() && !(free()>0) ) { ++sym; } |
---|
[9] | 65 | return *this; |
---|
| 66 | } |
---|
| 67 | }; |
---|
| 68 | |
---|
[19] | 69 | out_edge_iterator first_out_edge(const node_iterator& v) { |
---|
| 70 | return out_edge_iterator(*this, v); |
---|
[9] | 71 | } |
---|
| 72 | |
---|
| 73 | each_node_iterator first_node() { |
---|
| 74 | return G.first_node(); |
---|
| 75 | } |
---|
| 76 | |
---|
[19] | 77 | node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); } |
---|
| 78 | node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); } |
---|
[9] | 79 | |
---|
| 80 | int id(const node_iterator& v) { return G.id(v); } |
---|
| 81 | |
---|
[17] | 82 | //node_iterator invalid_node() { return G.invalid_node(); } |
---|
[19] | 83 | //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } |
---|
[9] | 84 | }; |
---|
| 85 | |
---|
| 86 | template <typename graph_type, typename T> |
---|
| 87 | struct max_flow_type { |
---|
[19] | 88 | typedef typename graph_type::node_iterator node_iterator; |
---|
| 89 | typedef typename graph_type::edge_iterator edge_iterator; |
---|
| 90 | typedef typename graph_type::each_node_iterator each_node_iterator; |
---|
| 91 | typedef typename graph_type::out_edge_iterator out_edge_iterator; |
---|
| 92 | typedef typename graph_type::in_edge_iterator in_edge_iterator; |
---|
[9] | 93 | graph_type& G; |
---|
| 94 | node_iterator s; |
---|
| 95 | node_iterator t; |
---|
| 96 | edge_property_vector<graph_type, T> flow; |
---|
| 97 | edge_property_vector<graph_type, T>& capacity; |
---|
| 98 | |
---|
| 99 | 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) { |
---|
[19] | 100 | for(each_node_iterator i=G.first_node(); i.valid(); ++i) |
---|
| 101 | for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) |
---|
[9] | 102 | flow.put(j, 0); |
---|
| 103 | } |
---|
| 104 | void run() { |
---|
| 105 | typedef res_graph_type<graph_type, T> aug_graph_type; |
---|
| 106 | aug_graph_type res_graph(G, flow, capacity); |
---|
| 107 | |
---|
| 108 | bool augment; |
---|
| 109 | do { |
---|
| 110 | augment=false; |
---|
[14] | 111 | |
---|
[19] | 112 | typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type; |
---|
[14] | 113 | bfs_queue_type bfs_queue; |
---|
[9] | 114 | bfs_queue.push(res_graph.first_out_edge(s)); |
---|
[14] | 115 | |
---|
| 116 | typedef node_property_vector<aug_graph_type, bool> reached_type; |
---|
| 117 | reached_type reached(res_graph, false); |
---|
[9] | 118 | reached.put(s, true); |
---|
| 119 | |
---|
[14] | 120 | bfs_iterator1< aug_graph_type, reached_type > |
---|
| 121 | res_bfs(res_graph, bfs_queue, reached); |
---|
| 122 | |
---|
[19] | 123 | typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type; |
---|
[14] | 124 | pred_type pred(res_graph); |
---|
[19] | 125 | aug_graph_type::edge_iterator a; |
---|
[17] | 126 | a.make_invalid(); |
---|
| 127 | pred.put(s, a); |
---|
[14] | 128 | |
---|
| 129 | typedef node_property_vector<aug_graph_type, int> free_type; |
---|
| 130 | free_type free(res_graph); |
---|
| 131 | |
---|
[9] | 132 | //searching for augmenting path |
---|
[19] | 133 | while ( res_bfs.valid() ) { |
---|
[14] | 134 | //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl; |
---|
[19] | 135 | if (res_bfs.newly_reached()) { |
---|
| 136 | aug_graph_type::edge_iterator e; |
---|
[14] | 137 | e=res_bfs; |
---|
| 138 | node_iterator v=res_graph.tail(e); |
---|
| 139 | node_iterator w=res_graph.head(e); |
---|
| 140 | //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; |
---|
| 141 | pred.put(w, e); |
---|
[19] | 142 | if (pred.get(v).valid()) { |
---|
[14] | 143 | free.put(w, std::min(free.get(v), e.free())); |
---|
| 144 | //std::cout <<" nem elso csucs: "; |
---|
| 145 | //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
---|
| 146 | } else { |
---|
| 147 | free.put(w, e.free()); |
---|
| 148 | //std::cout <<" elso csucs: "; |
---|
| 149 | //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
---|
| 150 | } |
---|
| 151 | //std::cout<<std::endl; |
---|
| 152 | } |
---|
| 153 | |
---|
[9] | 154 | if (res_graph.head(res_bfs)==t) break; |
---|
| 155 | ++res_bfs; |
---|
| 156 | } |
---|
| 157 | if (reached.get(t)) { |
---|
| 158 | augment=true; |
---|
| 159 | node_iterator n=t; |
---|
| 160 | T augment_value=free.get(t); |
---|
| 161 | std::cout<<"augmentation: "; |
---|
[19] | 162 | while (pred.get(n).valid()) { |
---|
| 163 | aug_graph_type::edge_iterator e=pred.get(n); |
---|
[9] | 164 | e.augment(augment_value); |
---|
| 165 | std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; |
---|
| 166 | n=res_graph.tail(e); |
---|
| 167 | } |
---|
| 168 | std::cout<<std::endl; |
---|
| 169 | } |
---|
| 170 | |
---|
[14] | 171 | std::cout << "actual flow: "<< std::endl; |
---|
[19] | 172 | for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) { |
---|
[9] | 173 | std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
---|
| 174 | } |
---|
| 175 | std::cout<<std::endl; |
---|
| 176 | |
---|
| 177 | } while (augment); |
---|
| 178 | } |
---|
| 179 | }; |
---|
| 180 | |
---|
| 181 | } // namespace marci |
---|
| 182 | |
---|
| 183 | #endif //MARCI_MAX_FLOW_HH |
---|