173 } |
173 } |
174 |
174 |
175 //Gives the active node to work with |
175 //Gives the active node to work with |
176 //(depending on the implementation to be used) |
176 //(depending on the implementation to be used) |
177 NodeIt get_active_node(){ |
177 NodeIt get_active_node(){ |
178 //cout<<highest_active<<endl; |
178 |
179 |
179 |
180 switch(implementation) { |
180 switch(implementation) { |
181 case impl_highest_label : { |
181 case impl_highest_label : { |
182 |
182 |
183 //First need to find the highest label for which there"s an active node |
183 //First need to find the highest label for which there"s an active node |
184 while( highest_active>=0 && active_nodes[highest_active].empty() ){ |
184 while( highest_active>=0 && active_nodes[highest_active].empty() ){ |
185 --highest_active; |
185 --highest_active; |
186 } |
186 } |
187 |
187 |
188 if( highest_active>=0) { |
188 if( highest_active>=0) { |
|
189 |
|
190 |
189 NodeIt a=active_nodes[highest_active].front(); |
191 NodeIt a=active_nodes[highest_active].front(); |
190 active_nodes[highest_active].pop_front(); |
192 active_nodes[highest_active].pop_front(); |
|
193 |
191 return a; |
194 return a; |
192 } |
195 } |
193 else { |
196 else { |
194 return NodeIt(); |
197 return NodeIt(); |
195 } |
198 } |
302 |
305 |
303 |
306 |
304 //If the preflow is less than the capacity on the given edge |
307 //If the preflow is less than the capacity on the given edge |
305 //then it is an edge in the residual graph |
308 //then it is an edge in the residual graph |
306 bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){ |
309 bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){ |
|
310 |
307 if (capacity.get(j)>preflow.get(j)){ |
311 if (capacity.get(j)>preflow.get(j)){ |
308 if(level.get(G.tail(j))==level.get(G.head(j))+1){ |
312 if(level.get(G.tail(j))==level.get(G.head(j))+1){ |
309 return true; |
313 return true; |
310 } |
314 } |
311 else{ |
315 else{ |
317 } |
321 } |
318 |
322 |
319 //If the preflow is greater than 0 on the given edge |
323 //If the preflow is greater than 0 on the given edge |
320 //then the edge reversd is an edge in the residual graph |
324 //then the edge reversd is an edge in the residual graph |
321 bool is_admissible_backward_edge(InEdgeIt j, int& new_level){ |
325 bool is_admissible_backward_edge(InEdgeIt j, int& new_level){ |
|
326 |
322 if (0<preflow.get(j)){ |
327 if (0<preflow.get(j)){ |
323 if(level.get(G.tail(j))==level.get(G.head(j))-1){ |
328 if(level.get(G.tail(j))==level.get(G.head(j))-1){ |
|
329 |
324 return true; |
330 return true; |
325 } |
331 } |
326 else{ |
332 else{ |
327 if (level.get(G.tail(j)) < new_level) |
333 if (level.get(G.tail(j)) < new_level) |
328 new_level=level.get(G.tail(j)); |
334 new_level=level.get(G.tail(j)); |
337 |
343 |
338 template<typename graph_type, typename T> |
344 template<typename graph_type, typename T> |
339 T preflow_push<graph_type, T>::run() { |
345 T preflow_push<graph_type, T>::run() { |
340 |
346 |
341 preprocess(); |
347 preprocess(); |
342 |
348 //write_property_vector(level,"level"); |
343 T e,v; |
349 T e,v; |
344 NodeIt a; |
350 NodeIt a; |
345 while (a=get_active_node(), a.valid()){ |
351 while (a=get_active_node(), a.valid()){ |
|
352 |
346 //cout<<G.id(a)<<endl; |
353 //cout<<G.id(a)<<endl; |
347 //write_property_vector(excess,"excess"); |
354 //write_property_vector(excess,"excess"); |
348 //write_property_vector(level,"level"); |
355 //write_property_vector(level,"level"); |
349 |
356 |
350 |
357 |
351 bool go_to_next_node=false; |
358 bool go_to_next_node=false; |
352 e = excess.get(a); |
359 e = excess.get(a); |
353 while (!go_to_next_node){ |
360 while (!go_to_next_node){ |
354 |
|
355 //Initial value for the new level for the active node we are dealing with |
361 //Initial value for the new level for the active node we are dealing with |
356 int new_level=2*number_of_nodes; |
362 int new_level=2*number_of_nodes; |
357 //write_property_vector(excess,"excess"); |
363 //write_property_vector(excess,"excess"); |
358 //write_property_vector(level,"level"); |
364 //write_property_vector(level,"level"); |
359 //cout<<G.id(a)<<endl; |
365 //cout<<G.id(a)<<endl; |