1 #ifndef PREFLOW_PUSH_HH |
1 #ifndef HUGO_PREFLOW_PUSH_HH |
2 #define PREFLOW_PUSH_HH |
2 #define HUGO_PREFLOW_PUSH_HH |
3 |
3 |
4 #include <algorithm> |
4 //#include <algorithm> |
5 #include <list> |
5 #include <list> |
6 #include <vector> |
6 #include <vector> |
|
7 #include <queue> |
7 //#include "pf_hiba.hh" |
8 //#include "pf_hiba.hh" |
8 //#include <marci_list_graph.hh> |
9 //#include <marci_list_graph.hh> |
9 //#include <marci_graph_traits.hh> |
10 //#include <marci_graph_traits.hh> |
10 |
11 #include <invalid.h> |
11 #include <reverse_bfs.hh> |
12 #include <graph_wrapper.h> |
|
13 //#include <reverse_bfs.hh> |
12 |
14 |
13 using namespace std; |
15 using namespace std; |
14 |
16 |
15 namespace hugo { |
17 namespace hugo { |
16 |
18 |
17 template <typename graph_type, typename T> |
19 template <typename Graph, typename T> |
18 class preflow_push { |
20 class preflow_push { |
19 |
21 |
20 //Hasznos typedef-ek |
22 //Useful typedefs |
21 typedef typename graph_type::NodeIt NodeIt; |
23 typedef typename Graph::Node Node; |
22 typedef typename graph_type::EdgeIt EdgeIt; |
24 typedef typename Graph::NodeIt NodeIt; |
23 typedef typename graph_type::EachNodeIt EachNodeIt; |
25 typedef typename Graph::Edge Edge; |
24 typedef typename graph_type::EachEdgeIt EachEdgeIt; |
26 typedef typename Graph::OutEdgeIt OutEdgeIt; |
25 typedef typename graph_type::OutEdgeIt OutEdgeIt; |
27 typedef typename Graph::InEdgeIt InEdgeIt; |
26 typedef typename graph_type::InEdgeIt InEdgeIt; |
28 |
27 typedef typename graph_type::SymEdgeIt SymEdgeIt; |
|
28 |
|
29 |
|
30 |
|
31 /* |
|
32 typedef graph_traits<graph_type>::node_iterator node_iterator; |
|
33 typedef graph_traits<graph_type>::EdgeIt EdgeIt; |
|
34 typedef graph_traits<graph_type>::each_node_iterator each_node_iterator; |
|
35 typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt; |
|
36 typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt; |
|
37 typedef graph_traits<graph_type>::InEdgeIt InEdgeIt; |
|
38 typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt; |
|
39 */ |
|
40 |
29 |
41 //--------------------------------------------- |
30 //--------------------------------------------- |
42 //Parameters of the algorithm |
31 //Parameters of the algorithm |
43 //--------------------------------------------- |
32 //--------------------------------------------- |
44 //Fully examine an active node until excess becomes 0 |
33 //Fully examine an active node until excess becomes 0 |
53 //Parameters of the algorithm |
42 //Parameters of the algorithm |
54 //--------------------------------------------- |
43 //--------------------------------------------- |
55 |
44 |
56 private: |
45 private: |
57 //input |
46 //input |
58 graph_type& G; |
47 Graph& G; |
59 NodeIt s; |
48 Node s; |
60 NodeIt t; |
49 Node t; |
61 typename graph_type::EdgeMap<T> &capacity; |
50 typename Graph::EdgeMap<T> &capacity; |
62 //typename graph_type::EdgeMap<T> &capacity; |
51 |
63 //output |
52 //output |
64 //typename graph_type::EdgeMap<T> |
53 typename Graph::EdgeMap<T> preflow; |
65 typename graph_type::EdgeMap<T> preflow; |
|
66 T maxflow_value; |
54 T maxflow_value; |
67 |
55 |
68 //auxiliary variables for computation |
56 //auxiliary variables for computation |
|
57 //The number of the nodes |
69 int number_of_nodes; |
58 int number_of_nodes; |
70 |
59 //A nodemap for the level |
71 |
60 typename Graph::NodeMap<int> level; |
72 typename graph_type::NodeMap<int> level; |
61 //A nodemap for the excess |
73 typename graph_type::NodeMap<T> excess; |
62 typename Graph::NodeMap<T> excess; |
74 //node_property_vector<graph_type, int> level; |
|
75 //node_property_vector<graph_type, T> excess; |
|
76 |
63 |
77 //Number of nodes on each level |
64 //Number of nodes on each level |
78 vector<int> num_of_nodes_on_level; |
65 vector<int> num_of_nodes_on_level; |
79 |
66 |
80 //For the FIFO implementation |
67 //For the FIFO implementation |
81 list<NodeIt> fifo_nodes; |
68 list<Node> fifo_nodes; |
82 //For 'highest label' implementation |
69 //For 'highest label' implementation |
83 int highest_active; |
70 int highest_active; |
84 //int second_highest_active; |
71 //int second_highest_active; |
85 vector< list<NodeIt> > active_nodes; |
72 vector< list<Node> > active_nodes; |
86 |
73 |
87 public: |
74 public: |
88 |
75 |
89 //Constructing the object using the graph, source, sink and capacity vector |
76 //Constructing the object using the graph, source, sink and capacity vector |
90 preflow_push( |
77 preflow_push( |
91 graph_type& _G, |
78 Graph& _G, |
92 NodeIt _s, |
79 Node _s, |
93 NodeIt _t, |
80 Node _t, |
94 typename graph_type::EdgeMap<T> & _capacity) |
81 typename Graph::EdgeMap<T> & _capacity) |
95 : G(_G), s(_s), t(_t), |
82 : G(_G), s(_s), t(_t), |
96 capacity(_capacity), |
83 capacity(_capacity), |
97 preflow(_G), |
84 preflow(_G), |
98 //Counting the number of nodes |
85 //Counting the number of nodes |
99 //number_of_nodes(count(G.first<EachNodeIt>())), |
86 //number_of_nodes(count(G.first<EachNodeIt>())), |
125 } |
113 } |
126 |
114 |
127 //Returns the value of a maximal flow |
115 //Returns the value of a maximal flow |
128 T run(); |
116 T run(); |
129 |
117 |
130 typename graph_type::EdgeMap<T> getmaxflow(){ |
118 typename Graph::EdgeMap<T> getmaxflow(){ |
131 return preflow; |
119 return preflow; |
132 } |
120 } |
133 |
121 |
134 |
122 |
135 private: |
123 private: |
136 //For testing purposes only |
124 //For testing purposes only |
137 //Lists the node_properties |
125 //Lists the node_properties |
138 void write_property_vector(typename graph_type::NodeMap<T> a, |
126 void write_property_vector(typename Graph::NodeMap<T> a, |
139 //node_property_vector<graph_type, T> a, |
127 //node_property_vector<Graph, T> a, |
140 char* prop_name="property"){ |
128 char* prop_name="property"){ |
141 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) { |
129 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { |
142 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl; |
130 cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a[i]<<endl; |
143 } |
131 } |
144 cout<<endl; |
132 cout<<endl; |
145 } |
133 } |
146 |
134 |
147 //Modifies the excess of the node and makes sufficient changes |
135 //Modifies the excess of the node and makes sufficient changes |
148 void modify_excess(const NodeIt& a ,T v){ |
136 void modify_excess(const Node& a ,T v){ |
149 T old_value=excess.get(a); |
137 //T old_value=excess[a]; |
150 excess.set(a,old_value+v); |
138 excess[a] += v; |
151 } |
139 } |
152 |
140 |
153 //This private procedure is supposed to modify the preflow on edge j |
141 //This private procedure is supposed to modify the preflow on edge j |
154 //by value v (which can be positive or negative as well) |
142 //by value v (which can be positive or negative as well) |
155 //and maintain the excess on the head and tail |
143 //and maintain the excess on the head and tail |
156 //Here we do not check whether this is possible or not |
144 //Here we do not check whether this is possible or not |
157 void modify_preflow(EdgeIt j, const T& v){ |
145 void modify_preflow(Edge j, const T& v){ |
158 |
146 |
159 //Auxiliary variable |
|
160 T old_value; |
|
161 |
|
162 //Modifiyng the edge |
147 //Modifiyng the edge |
163 old_value=preflow.get(j); |
148 preflow[j] += v; |
164 preflow.set(j,old_value+v); |
|
165 |
149 |
166 |
150 |
167 //Modifiyng the head |
151 //Modifiyng the head |
168 modify_excess(G.head(j),v); |
152 modify_excess(G.head(j),v); |
169 |
153 |
172 |
156 |
173 } |
157 } |
174 |
158 |
175 //Gives the active node to work with |
159 //Gives the active node to work with |
176 //(depending on the implementation to be used) |
160 //(depending on the implementation to be used) |
177 NodeIt get_active_node(){ |
161 Node get_active_node(){ |
178 |
162 |
179 |
163 |
180 switch(implementation) { |
164 switch(implementation) { |
181 case impl_highest_label : { |
165 case impl_highest_label : { |
182 |
166 |
183 //First need to find the highest label for which there"s an active node |
167 //First need to find the highest label for which there's an active node |
184 while( highest_active>=0 && active_nodes[highest_active].empty() ){ |
168 while( highest_active>=0 && active_nodes[highest_active].empty() ){ |
185 --highest_active; |
169 --highest_active; |
186 } |
170 } |
187 |
171 |
188 if( highest_active>=0) { |
172 if( highest_active>=0) { |
189 |
173 |
190 |
174 |
191 NodeIt a=active_nodes[highest_active].front(); |
175 Node a=active_nodes[highest_active].front(); |
192 active_nodes[highest_active].pop_front(); |
176 active_nodes[highest_active].pop_front(); |
193 |
177 |
194 return a; |
178 return a; |
195 } |
179 } |
196 else { |
180 else { |
197 return NodeIt(); |
181 return INVALID; |
198 } |
182 } |
199 |
183 |
200 break; |
184 break; |
201 |
185 |
202 } |
186 } |
203 case impl_fifo : { |
187 case impl_fifo : { |
204 |
188 |
205 if( ! fifo_nodes.empty() ) { |
189 if( ! fifo_nodes.empty() ) { |
206 NodeIt a=fifo_nodes.front(); |
190 Node a=fifo_nodes.front(); |
207 fifo_nodes.pop_front(); |
191 fifo_nodes.pop_front(); |
208 return a; |
192 return a; |
209 } |
193 } |
210 else { |
194 else { |
211 return NodeIt(); |
195 return INVALID; |
212 } |
196 } |
213 break; |
197 break; |
214 } |
198 } |
215 } |
199 } |
216 // |
200 // |
217 return NodeIt(); |
201 return INVALID; |
218 } |
202 } |
219 |
203 |
220 //Puts node 'a' among the active nodes |
204 //Puts node 'a' among the active nodes |
221 void make_active(const NodeIt& a){ |
205 void make_active(const Node& a){ |
222 //s and t never become active |
206 //s and t never become active |
223 if (a!=s && a!= t){ |
207 if (a!=s && a!= t){ |
224 switch(implementation){ |
208 switch(implementation){ |
225 case impl_highest_label : |
209 case impl_highest_label : |
226 active_nodes[level.get(a)].push_back(a); |
210 active_nodes[level[a]].push_back(a); |
227 break; |
211 break; |
228 case impl_fifo : |
212 case impl_fifo : |
229 fifo_nodes.push_back(a); |
213 fifo_nodes.push_back(a); |
230 break; |
214 break; |
231 } |
215 } |
232 |
216 |
233 } |
217 } |
234 |
218 |
235 //Update highest_active label |
219 //Update highest_active label |
236 if (highest_active<level.get(a)){ |
220 if (highest_active<level[a]){ |
237 highest_active=level.get(a); |
221 highest_active=level[a]; |
238 } |
222 } |
239 |
223 |
240 } |
224 } |
241 |
225 |
242 //Changes the level of node a and make sufficent changes |
226 //Changes the level of node a and make sufficent changes |
243 void change_level_to(NodeIt a, int new_value){ |
227 void change_level_to(Node a, int new_value){ |
244 int seged = level.get(a); |
228 int seged = level[a]; |
245 level.set(a,new_value); |
229 level.set(a,new_value); |
246 --num_of_nodes_on_level[seged]; |
230 --num_of_nodes_on_level[seged]; |
247 ++num_of_nodes_on_level[new_value]; |
231 ++num_of_nodes_on_level[new_value]; |
248 } |
232 } |
249 |
233 |
271 |
255 |
272 |
256 |
273 //------------------------------------ |
257 //------------------------------------ |
274 //This is the only part that uses BFS |
258 //This is the only part that uses BFS |
275 //------------------------------------ |
259 //------------------------------------ |
|
260 |
|
261 /*Reverse_bfs from t, to find the starting level.*/ |
|
262 //Copyright: Jacint |
|
263 change_level_to(t,0); |
|
264 |
|
265 std::queue<Node> bfs_queue; |
|
266 bfs_queue.push(t); |
|
267 |
|
268 while (!bfs_queue.empty()) { |
|
269 |
|
270 Node v=bfs_queue.front(); |
|
271 bfs_queue.pop(); |
|
272 int l=level[v]+1; |
|
273 |
|
274 InEdgeIt e; |
|
275 for(G.first(e,v); G.valid(e); G.next(e)) { |
|
276 Node w=G.tail(e); |
|
277 if ( level[w] == number_of_nodes && w != s ) { |
|
278 bfs_queue.push(w); |
|
279 //Node first=level_list[l]; |
|
280 //if ( G.valid(first) ) left.set(first,w); |
|
281 //right.set(w,first); |
|
282 //level_list[l]=w; |
|
283 change_level_to(w, l); |
|
284 //level.set(w, l); |
|
285 } |
|
286 } |
|
287 } |
|
288 change_level_to(s,number_of_nodes); |
|
289 //level.set(s,number_of_nodes); |
|
290 |
|
291 /* |
276 //Setting starting level values using reverse bfs |
292 //Setting starting level values using reverse bfs |
277 reverse_bfs<graph_type> rev_bfs(G,t); |
293 reverse_bfs<Graph> rev_bfs(G,t); |
278 rev_bfs.run(); |
294 rev_bfs.run(); |
279 //write_property_vector(rev_bfs.dist,"rev_bfs"); |
295 //write_property_vector(rev_bfs.dist,"rev_bfs"); |
280 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) { |
296 for(NodeIt i=G.template first<NodeIt>(); G.valid(i); G.next(i)) { |
281 change_level_to(i,rev_bfs.dist(i)); |
297 change_level_to(i,rev_bfs.dist(i)); |
282 //level.put(i,rev_bfs.dist.get(i)); |
298 //level.put(i,rev_bfs.dist.get(i)); |
283 } |
299 } |
|
300 */ |
284 //------------------------------------ |
301 //------------------------------------ |
285 //This is the only part that uses BFS |
302 //This is the only part that uses BFS |
286 //------------------------------------ |
303 //------------------------------------ |
287 |
304 |
288 |
305 |
290 change_level_to(s,number_of_nodes); |
307 change_level_to(s,number_of_nodes); |
291 //level.put(s,number_of_nodes); |
308 //level.put(s,number_of_nodes); |
292 |
309 |
293 |
310 |
294 //we push as much preflow from s as possible to start with |
311 //we push as much preflow from s as possible to start with |
295 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){ |
312 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ |
296 modify_preflow(j,capacity.get(j) ); |
313 modify_preflow(j,capacity[j] ); |
297 make_active(G.head(j)); |
314 make_active(G.head(j)); |
298 int lev=level.get(G.head(j)); |
315 int lev=level[G.head(j)]; |
299 if(highest_active<lev){ |
316 if(highest_active<lev){ |
300 highest_active=lev; |
317 highest_active=lev; |
301 } |
318 } |
302 } |
319 } |
303 //cout<<highest_active<<endl; |
320 //cout<<highest_active<<endl; |
304 } |
321 } |
305 |
322 |
306 |
323 |
307 //If the preflow is less than the capacity on the given edge |
324 //If the preflow is less than the capacity on the given edge |
308 //then it is an edge in the residual graph |
325 //then it is an edge in the residual graph |
309 bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){ |
326 bool is_admissible_forward_edge(Edge j, int& new_level){ |
310 |
327 |
311 if (capacity.get(j)>preflow.get(j)){ |
328 if (capacity[j]>preflow[j]){ |
312 if(level.get(G.tail(j))==level.get(G.head(j))+1){ |
329 if(level[G.tail(j)]==level[G.head(j)]+1){ |
313 return true; |
330 return true; |
314 } |
331 } |
315 else{ |
332 else{ |
316 if (level.get(G.head(j)) < new_level) |
333 if (level[G.head(j)] < new_level) |
317 new_level=level.get(G.head(j)); |
334 new_level=level[G.head(j)]; |
318 } |
335 } |
319 } |
336 } |
320 return false; |
337 return false; |
321 } |
338 } |
322 |
339 |
323 //If the preflow is greater than 0 on the given edge |
340 //If the preflow is greater than 0 on the given edge |
324 //then the edge reversd is an edge in the residual graph |
341 //then the edge reversd is an edge in the residual graph |
325 bool is_admissible_backward_edge(InEdgeIt j, int& new_level){ |
342 bool is_admissible_backward_edge(Edge j, int& new_level){ |
326 |
343 |
327 if (0<preflow.get(j)){ |
344 if (0<preflow[j]){ |
328 if(level.get(G.tail(j))==level.get(G.head(j))-1){ |
345 if(level[G.tail(j)]==level[G.head(j)]-1){ |
329 |
346 |
330 return true; |
347 return true; |
331 } |
348 } |
332 else{ |
349 else{ |
333 if (level.get(G.tail(j)) < new_level) |
350 if (level[G.tail(j)] < new_level) |
334 new_level=level.get(G.tail(j)); |
351 new_level=level[G.tail(j)]; |
335 } |
352 } |
336 |
353 |
337 } |
354 } |
338 return false; |
355 return false; |
339 } |
356 } |
340 |
357 |
341 |
358 |
342 }; //class preflow_push |
359 }; //class preflow_push |
343 |
360 |
344 template<typename graph_type, typename T> |
361 template<typename Graph, typename T> |
345 T preflow_push<graph_type, T>::run() { |
362 T preflow_push<Graph, T>::run() { |
|
363 |
|
364 //We need a residual graph |
|
365 ResGraphType res_graph(G, preflow, capacity); |
346 |
366 |
347 preprocess(); |
367 preprocess(); |
348 //write_property_vector(level,"level"); |
368 //write_property_vector(level,"level"); |
349 T e,v; |
369 T e,v; |
350 NodeIt a; |
370 Node a; |
351 while (a=get_active_node(), a.valid()){ |
371 while (a=get_active_node(), G.valid(a)){ |
352 |
372 |
353 //cout<<G.id(a)<<endl; |
|
354 //write_property_vector(excess,"excess"); |
|
355 //write_property_vector(level,"level"); |
|
356 |
|
357 |
|
358 bool go_to_next_node=false; |
373 bool go_to_next_node=false; |
359 e = excess.get(a); |
374 e = excess[a]; |
360 while (!go_to_next_node){ |
375 while (!go_to_next_node){ |
|
376 |
361 //Initial value for the new level for the active node we are dealing with |
377 //Initial value for the new level for the active node we are dealing with |
362 int new_level=2*number_of_nodes; |
378 int new_level=2*number_of_nodes; |
363 //write_property_vector(excess,"excess"); |
379 |
364 //write_property_vector(level,"level"); |
380 |
365 //cout<<G.id(a)<<endl; |
|
366 //Out edges from node a |
381 //Out edges from node a |
367 { |
382 { |
368 OutEdgeIt j=G.template first<OutEdgeIt>(a); |
383 OutEdgeIt j=G.template first<OutEdgeIt>(a); |
369 while (j.valid() && e){ |
384 while (G.valid(j) && e){ |
370 |
385 |
371 if (is_admissible_forward_edge(j,new_level)){ |
386 if (is_admissible_forward_edge(j,new_level)){ |
372 v=min(e,capacity.get(j) - preflow.get(j)); |
387 v=min(e,capacity[j] - preflow[j]); |
373 e -= v; |
388 e -= v; |
374 //New node might become active |
389 //New node might become active |
375 if (excess.get(G.head(j))==0){ |
390 if (excess[G.head(j)]==0){ |
376 make_active(G.head(j)); |
391 make_active(G.head(j)); |
377 } |
392 } |
378 modify_preflow(j,v); |
393 modify_preflow(j,v); |
379 } |
394 } |
380 ++j; |
395 G.next(j); |
381 } |
396 } |
382 } |
397 } |
383 //In edges to node a |
398 //In edges to node a |
384 { |
399 { |
385 InEdgeIt j=G.template first<InEdgeIt>(a); |
400 InEdgeIt j=G.template first<InEdgeIt>(a); |
386 while (j.valid() && e){ |
401 while (G.valid(j) && e){ |
387 if (is_admissible_backward_edge(j,new_level)){ |
402 if (is_admissible_backward_edge(j,new_level)){ |
388 v=min(e,preflow.get(j)); |
403 v=min(e,preflow[j]); |
389 e -= v; |
404 e -= v; |
390 //New node might become active |
405 //New node might become active |
391 if (excess.get(G.tail(j))==0){ |
406 if (excess[G.tail(j)]==0){ |
392 make_active(G.tail(j)); |
407 make_active(G.tail(j)); |
393 } |
408 } |
394 modify_preflow(j,-v); |
409 modify_preflow(j,-v); |
395 } |
410 } |
396 ++j; |
411 G.next(j); |
397 } |
412 } |
398 } |
413 } |
399 |
414 |
400 //if (G.id(a)==999) |
415 //if (G.id(a)==999) |
401 //cout<<new_level<<" e: "<<e<<endl; |
416 //cout<<new_level<<" e: "<<e<<endl; |