|
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 |