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