[9] | 1 | #ifndef MARCI_MAX_FLOW_HH |
---|
| 2 | #define MARCI_MAX_FLOW_HH |
---|
| 3 | |
---|
| 4 | #include <algorithm> |
---|
| 5 | |
---|
| 6 | #include <marci_graph_traits.hh> |
---|
| 7 | #include <marci_property_vector.hh> |
---|
| 8 | #include <marci_bfs.hh> |
---|
| 9 | |
---|
| 10 | namespace marci { |
---|
| 11 | |
---|
| 12 | template<typename graph_type, typename T> |
---|
| 13 | class res_graph_type { |
---|
| 14 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
---|
| 15 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
---|
| 16 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
---|
| 17 | typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator; |
---|
| 18 | |
---|
| 19 | graph_type& G; |
---|
| 20 | edge_property_vector<graph_type, T>& flow; |
---|
| 21 | edge_property_vector<graph_type, T>& capacity; |
---|
| 22 | public: |
---|
| 23 | 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) { } |
---|
| 24 | |
---|
| 25 | class res_edge_it { |
---|
| 26 | friend class res_graph_type<graph_type, T>; |
---|
| 27 | protected: |
---|
| 28 | res_graph_type<graph_type, T>* resG; |
---|
| 29 | sym_edge_iterator sym; |
---|
| 30 | public: |
---|
| 31 | res_edge_it() { } |
---|
| 32 | //bool is_free() { |
---|
| 33 | //if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
---|
| 34 | // return (resG->flow.get(sym)<resG->capacity.get(sym)); |
---|
| 35 | //} else { |
---|
| 36 | // return (resG->flow.get(sym)>0); |
---|
| 37 | //} |
---|
| 38 | //} |
---|
| 39 | T free() { |
---|
| 40 | if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
---|
| 41 | return (resG->capacity.get(sym)-resG->flow.get(sym)); |
---|
| 42 | } else { |
---|
| 43 | return (resG->flow.get(sym)); |
---|
| 44 | } |
---|
| 45 | } |
---|
| 46 | bool is_valid() { return sym.is_valid(); } |
---|
| 47 | void augment(T a) { |
---|
| 48 | if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
---|
| 49 | resG->flow.put(sym, resG->flow.get(sym)+a); |
---|
| 50 | } else { |
---|
| 51 | resG->flow.put(sym, resG->flow.get(sym)-a); |
---|
| 52 | } |
---|
| 53 | } |
---|
| 54 | }; |
---|
| 55 | |
---|
| 56 | class res_out_edge_it : public res_edge_it { |
---|
| 57 | public: |
---|
| 58 | res_out_edge_it() { } |
---|
| 59 | res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { |
---|
| 60 | resG=&_resG; |
---|
| 61 | sym=resG->G.first_sym_edge(v); |
---|
| 62 | while( sym.is_valid() && !(free()>0) ) { ++sym; } |
---|
| 63 | } |
---|
| 64 | res_out_edge_it& operator++() { |
---|
| 65 | ++sym; |
---|
| 66 | while( sym.is_valid() && !(free()>0) ) { ++sym; } |
---|
| 67 | return *this; |
---|
| 68 | } |
---|
| 69 | }; |
---|
| 70 | |
---|
| 71 | res_out_edge_it first_out_edge(const node_iterator& v) { |
---|
| 72 | return res_out_edge_it(*this, v); |
---|
| 73 | } |
---|
| 74 | |
---|
| 75 | each_node_iterator first_node() { |
---|
| 76 | return G.first_node(); |
---|
| 77 | } |
---|
| 78 | |
---|
| 79 | node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); } |
---|
| 80 | node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); } |
---|
| 81 | |
---|
| 82 | int id(const node_iterator& v) { return G.id(v); } |
---|
| 83 | |
---|
| 84 | node_iterator invalid_node() { return G.invalid_node(); } |
---|
| 85 | res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } |
---|
| 86 | |
---|
| 87 | }; |
---|
| 88 | |
---|
| 89 | template <typename graph_type, typename T> |
---|
| 90 | struct graph_traits< res_graph_type<graph_type, T> > { |
---|
| 91 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
---|
| 92 | typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator; |
---|
| 93 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
---|
| 94 | typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator; |
---|
| 95 | }; |
---|
| 96 | |
---|
| 97 | template <typename graph_type, typename pred_type, typename free_type> |
---|
| 98 | struct flow_visitor { |
---|
| 99 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
---|
| 100 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
---|
| 101 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
---|
| 102 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
---|
| 103 | graph_type& G; |
---|
| 104 | pred_type& pred; |
---|
| 105 | free_type& free; |
---|
| 106 | flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { } |
---|
| 107 | void at_previously_reached(out_edge_iterator& e) { |
---|
| 108 | //node_iterator v=G.tail(e); |
---|
| 109 | //node_iterator w=G.head(e); |
---|
| 110 | //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached"; |
---|
| 111 | //std::cout<<std::endl; |
---|
| 112 | } |
---|
| 113 | void at_newly_reached(out_edge_iterator& e) { |
---|
| 114 | node_iterator v=G.tail(e); |
---|
| 115 | node_iterator w=G.head(e); |
---|
| 116 | //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; |
---|
| 117 | pred.put(w, e); |
---|
| 118 | if (pred.get(v).is_valid()) { |
---|
| 119 | free.put(w, std::min(free.get(v), e.free())); |
---|
| 120 | //std::cout <<" nem elso csucs: "; |
---|
| 121 | //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
---|
| 122 | } else { |
---|
| 123 | free.put(w, e.free()); |
---|
| 124 | //std::cout <<" elso csucs: "; |
---|
| 125 | //std::cout <<"szabad kap eddig: "<< free.get(w) << " "; |
---|
| 126 | } |
---|
| 127 | //std::cout<<std::endl; |
---|
| 128 | } |
---|
| 129 | }; |
---|
| 130 | |
---|
| 131 | template <typename graph_type, typename T> |
---|
| 132 | struct max_flow_type { |
---|
| 133 | |
---|
| 134 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
---|
| 135 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
---|
| 136 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
---|
| 137 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
---|
| 138 | typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
---|
| 139 | |
---|
| 140 | graph_type& G; |
---|
| 141 | node_iterator s; |
---|
| 142 | node_iterator t; |
---|
| 143 | edge_property_vector<graph_type, T> flow; |
---|
| 144 | edge_property_vector<graph_type, T>& capacity; |
---|
| 145 | |
---|
| 146 | 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) { |
---|
| 147 | for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) |
---|
| 148 | for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) |
---|
| 149 | flow.put(j, 0); |
---|
| 150 | } |
---|
| 151 | void run() { |
---|
| 152 | typedef res_graph_type<graph_type, T> aug_graph_type; |
---|
| 153 | aug_graph_type res_graph(G, flow, capacity); |
---|
| 154 | |
---|
| 155 | typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type; |
---|
| 156 | bfs_queue_type bfs_queue; |
---|
| 157 | //bfs_queue.push(res_graph.first_out_edge(s)); |
---|
| 158 | |
---|
| 159 | typedef node_property_vector<aug_graph_type, bool> reached_type; |
---|
| 160 | //reached_type reached(res_graph, false); |
---|
| 161 | reached_type reached(res_graph); |
---|
| 162 | //reached.put(s, true); |
---|
| 163 | |
---|
| 164 | typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type; |
---|
| 165 | pred_type pred(res_graph); |
---|
| 166 | pred.put(s, res_graph.invalid_edge()); |
---|
| 167 | |
---|
| 168 | typedef node_property_vector<aug_graph_type, int> free_type; |
---|
| 169 | free_type free(res_graph); |
---|
| 170 | |
---|
| 171 | typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type; |
---|
| 172 | visitor_type vis(res_graph, pred, free); |
---|
| 173 | |
---|
| 174 | bfs_iterator< aug_graph_type, reached_type, visitor_type > |
---|
| 175 | res_bfs(res_graph, bfs_queue, reached, vis); |
---|
| 176 | |
---|
| 177 | //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { |
---|
| 178 | //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) { |
---|
| 179 | // std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") "; |
---|
| 180 | //} |
---|
| 181 | //} |
---|
| 182 | //std::cout<<std::endl; |
---|
| 183 | |
---|
| 184 | //char c; |
---|
| 185 | bool augment; |
---|
| 186 | do { |
---|
| 187 | augment=false; |
---|
| 188 | |
---|
| 189 | while (!bfs_queue.empty()) { bfs_queue.pop(); } |
---|
| 190 | bfs_queue.push(res_graph.first_out_edge(s)); |
---|
| 191 | |
---|
| 192 | for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); } |
---|
| 193 | reached.put(s, true); |
---|
| 194 | |
---|
| 195 | //searching for augmenting path |
---|
| 196 | while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { |
---|
| 197 | res_bfs.process(); |
---|
| 198 | //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break; |
---|
| 199 | if (res_graph.head(res_bfs)==t) break; |
---|
| 200 | //res_bfs.next(); |
---|
| 201 | ++res_bfs; |
---|
| 202 | } |
---|
| 203 | //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); } |
---|
| 204 | if (reached.get(t)) { |
---|
| 205 | augment=true; |
---|
| 206 | node_iterator n=t; |
---|
| 207 | T augment_value=free.get(t); |
---|
| 208 | std::cout<<"augmentation: "; |
---|
| 209 | while (pred.get(n).is_valid()) { |
---|
| 210 | graph_traits<aug_graph_type>::edge_iterator e=pred.get(n); |
---|
| 211 | e.augment(augment_value); |
---|
| 212 | std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; |
---|
| 213 | n=res_graph.tail(e); |
---|
| 214 | } |
---|
| 215 | std::cout<<std::endl; |
---|
| 216 | } |
---|
| 217 | |
---|
| 218 | std::cout << "max flow:"<< std::endl; |
---|
| 219 | for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { |
---|
| 220 | std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; |
---|
| 221 | } |
---|
| 222 | std::cout<<std::endl; |
---|
| 223 | |
---|
| 224 | } while (augment); |
---|
| 225 | } |
---|
| 226 | }; |
---|
| 227 | |
---|
| 228 | } // namespace marci |
---|
| 229 | |
---|
| 230 | #endif //MARCI_MAX_FLOW_HH |
---|