|
1 /* |
|
2 preflow_push_hl.hh |
|
3 by jacint. |
|
4 Runs the highest label variant of the preflow push algorithm with |
|
5 running time O(n^2\sqrt(m)). |
|
6 |
|
7 Member functions: |
|
8 |
|
9 void run() : runs the algorithm |
|
10 |
|
11 The following functions should be used after run() was already run. |
|
12 |
|
13 T maxflow() : returns the value of a maximum flow |
|
14 |
|
15 T flowonedge(edge_iterator e) : for a fixed maximum flow x it returns x(e) |
|
16 |
|
17 edge_property_vector<graph_type, T> allflow() : returns the fixed maximum flow x |
|
18 |
|
19 node_property_vector<graph_type, bool> mincut() : returns a |
|
20 characteristic vector of a minimum cut. (An empty level |
|
21 in the algorithm gives a minimum cut.) |
|
22 */ |
|
23 |
|
24 #ifndef PREFLOW_PUSH_HL_HH |
|
25 #define PREFLOW_PUSH_HL_HH |
|
26 |
|
27 #include <algorithm> |
|
28 #include <vector> |
|
29 #include <stack> |
|
30 |
|
31 #include <marci_graph_traits.hh> |
|
32 #include <marci_property_vector.hh> |
|
33 #include <reverse_bfs.hh> |
|
34 |
|
35 namespace marci { |
|
36 |
|
37 template <typename graph_type, typename T> |
|
38 class preflow_push_hl { |
|
39 |
|
40 typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
|
41 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
|
42 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
|
43 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; |
|
44 typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
|
45 typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator; |
|
46 |
|
47 |
|
48 graph_type& G; |
|
49 node_iterator s; |
|
50 node_iterator t; |
|
51 edge_property_vector<graph_type, T> flow; |
|
52 edge_property_vector<graph_type, T>& capacity; |
|
53 T value; |
|
54 node_property_vector<graph_type, bool> mincutvector; |
|
55 |
|
56 |
|
57 public: |
|
58 |
|
59 preflow_push_hl(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { } |
|
60 |
|
61 |
|
62 |
|
63 |
|
64 /* |
|
65 The run() function runs the highest label preflow-push, |
|
66 running time: O(n^2\sqrt(m)) |
|
67 */ |
|
68 void run() { |
|
69 |
|
70 node_property_vector<graph_type, int> level(G); //level of node |
|
71 node_property_vector<graph_type, T> excess(G); //excess of node |
|
72 |
|
73 int n=number_of(G.first_node()); //number of nodes |
|
74 int b=n; |
|
75 /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/ |
|
76 |
|
77 std::vector<std::stack<node_iterator> > stack(2*n-1); //Stack of the active nodes in level i. |
|
78 |
|
79 |
|
80 |
|
81 |
|
82 /*Reverse_bfs from t, to find the starting level.*/ |
|
83 |
|
84 reverse_bfs<list_graph> bfs(G, t); |
|
85 bfs.run(); |
|
86 for(each_node_iterator v=G.first_node(); v.valid(); ++v) { |
|
87 level.put(v, bfs.dist(v)); |
|
88 //std::cout << "the level of " << v << " is " << bfs.dist(v); |
|
89 } |
|
90 |
|
91 /*The level of s is fixed to n*/ |
|
92 level.put(s,n); |
|
93 |
|
94 |
|
95 |
|
96 |
|
97 |
|
98 /* Starting flow. It is everywhere 0 at the moment. */ |
|
99 |
|
100 for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) |
|
101 { |
|
102 node_iterator w=G.head(i); |
|
103 flow.put(i, capacity.get(i)); |
|
104 stack[bfs.dist(w)].push(w); |
|
105 excess.put(w, capacity.get(i)); |
|
106 } |
|
107 |
|
108 |
|
109 /* |
|
110 End of preprocessing |
|
111 */ |
|
112 |
|
113 |
|
114 |
|
115 /* |
|
116 Push/relabel on the highest level active nodes. |
|
117 */ |
|
118 |
|
119 /*While there exists active node.*/ |
|
120 while (b) { |
|
121 |
|
122 /*We decrease the bound if there is no active node of level b.*/ |
|
123 if (stack[b].empty()) { |
|
124 --b; |
|
125 } else { |
|
126 |
|
127 node_iterator w=stack[b].top(); //w is the highest label active node. |
|
128 stack[b].pop(); //We delete w from the stack. |
|
129 |
|
130 int newlevel=2*n-2; //In newlevel we maintain the next level of w. |
|
131 |
|
132 for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) { |
|
133 node_iterator v=G.head(e); |
|
134 /*e is the edge wv.*/ |
|
135 |
|
136 if (flow.get(e)<capacity.get(e)) { |
|
137 /*e is an edge of the residual graph */ |
|
138 |
|
139 if(level.get(w)==level.get(v)+1) { |
|
140 /*Push is allowed now*/ |
|
141 |
|
142 if (capacity.get(e)-flow.get(e) > excess.get(w)) { |
|
143 /*A nonsaturating push.*/ |
|
144 |
|
145 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); |
|
146 /*v becomes active.*/ |
|
147 |
|
148 flow.put(e, flow.get(e)+excess.get(w)); |
|
149 excess.put(v, excess.get(v)+excess.get(w)); |
|
150 excess.put(w,0); |
|
151 //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl; |
|
152 break; |
|
153 } else { |
|
154 /*A saturating push.*/ |
|
155 |
|
156 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); |
|
157 /*v becomes active.*/ |
|
158 |
|
159 excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e)); |
|
160 excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e)); |
|
161 flow.put(e, capacity.get(e)); |
|
162 //std::cout << w<<" " <<v<<" elore elen sat pump " << std::endl; |
|
163 if (excess.get(w)==0) break; |
|
164 /*If w is not active any more, then we go on to the next node.*/ |
|
165 |
|
166 } // if (capacity.get(e)-flow.get(e) > excess.get(w)) |
|
167 } // if(level.get(w)==level.get(v)+1) |
|
168 |
|
169 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} |
|
170 |
|
171 } //if (flow.get(e)<capacity.get(e)) |
|
172 |
|
173 } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) |
|
174 |
|
175 |
|
176 |
|
177 for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) { |
|
178 node_iterator v=G.tail(e); |
|
179 /*e is the edge vw.*/ |
|
180 |
|
181 if (excess.get(w)==0) break; |
|
182 /*It may happen, that w became inactive in the first for cycle.*/ |
|
183 if(flow.get(e)>0) { |
|
184 /*e is an edge of the residual graph */ |
|
185 |
|
186 if(level.get(w)==level.get(v)+1) { |
|
187 /*Push is allowed now*/ |
|
188 |
|
189 if (flow.get(e) > excess.get(w)) { |
|
190 /*A nonsaturating push.*/ |
|
191 |
|
192 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); |
|
193 /*v becomes active.*/ |
|
194 |
|
195 flow.put(e, flow.get(e)-excess.get(w)); |
|
196 excess.put(v, excess.get(v)+excess.get(w)); |
|
197 excess.put(w,0); |
|
198 //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl; |
|
199 break; |
|
200 } else { |
|
201 /*A saturating push.*/ |
|
202 |
|
203 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); |
|
204 /*v becomes active.*/ |
|
205 |
|
206 excess.put(v, excess.get(v)+flow.get(e)); |
|
207 excess.put(w, excess.get(w)-flow.get(e)); |
|
208 flow.put(e,0); |
|
209 //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl; |
|
210 if (excess.get(w)==0) { break;} |
|
211 } //if (flow.get(e) > excess.get(v)) |
|
212 } //if(level.get(w)==level.get(v)+1) |
|
213 |
|
214 else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);} |
|
215 |
|
216 |
|
217 } //if (flow.get(e)>0) |
|
218 |
|
219 } //for |
|
220 |
|
221 |
|
222 if (excess.get(w)>0) { |
|
223 level.put(w,++newlevel); |
|
224 stack[newlevel].push(w); |
|
225 b=newlevel; |
|
226 //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl; |
|
227 } |
|
228 |
|
229 |
|
230 } //else |
|
231 |
|
232 } //while(b) |
|
233 |
|
234 value = excess.get(t); |
|
235 /*Max flow value.*/ |
|
236 |
|
237 |
|
238 |
|
239 |
|
240 } //void run() |
|
241 |
|
242 |
|
243 |
|
244 |
|
245 |
|
246 /* |
|
247 Returns the maximum value of a flow. |
|
248 */ |
|
249 |
|
250 T maxflow() { |
|
251 return value; |
|
252 } |
|
253 |
|
254 |
|
255 |
|
256 /* |
|
257 For the maximum flow x found by the algorithm, it returns the flow value on edge e, i.e. x(e). |
|
258 */ |
|
259 |
|
260 T flowonedge(edge_iterator e) { |
|
261 return flow.get(e); |
|
262 } |
|
263 |
|
264 |
|
265 |
|
266 /* |
|
267 Returns the maximum flow x found by the algorithm. |
|
268 */ |
|
269 |
|
270 edge_property_vector<graph_type, T> allflow() { |
|
271 return flow; |
|
272 } |
|
273 |
|
274 |
|
275 |
|
276 /* |
|
277 Returns a minimum cut by using a reverse bfs from t in the residual graph. |
|
278 */ |
|
279 |
|
280 node_property_vector<graph_type, bool> mincut() { |
|
281 |
|
282 std::queue<node_iterator> queue; |
|
283 |
|
284 mincutvector.put(t,false); |
|
285 queue.push(t); |
|
286 |
|
287 while (!queue.empty()) { |
|
288 node_iterator w=queue.front(); |
|
289 queue.pop(); |
|
290 |
|
291 for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) { |
|
292 node_iterator v=G.tail(e); |
|
293 if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) { |
|
294 queue.push(v); |
|
295 mincutvector.put(v, false); |
|
296 } |
|
297 } // for |
|
298 |
|
299 for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) { |
|
300 node_iterator v=G.head(e); |
|
301 if (mincutvector.get(v) && flow.get(e) > 0 ) { |
|
302 queue.push(v); |
|
303 mincutvector.put(v, false); |
|
304 } |
|
305 } // for |
|
306 |
|
307 } |
|
308 |
|
309 return mincutvector; |
|
310 |
|
311 } |
|
312 |
|
313 |
|
314 }; |
|
315 }//namespace marci |
|
316 #endif |
|
317 |
|
318 |
|
319 |
|
320 |