137 excess[a] += v; |
137 excess[a] += v; |
138 } |
138 } |
139 |
139 |
140 //This private procedure is supposed to modify the preflow on edge j |
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) |
141 //by value v (which can be positive or negative as well) |
142 //and maintain the excess on the head and tail |
142 //and maintain the excess on the target and source |
143 //Here we do not check whether this is possible or not |
143 //Here we do not check whether this is possible or not |
144 void modify_preflow(Edge j, const T& v){ |
144 void modify_preflow(Edge j, const T& v){ |
145 |
145 |
146 //Modifiyng the edge |
146 //Modifiyng the edge |
147 preflow[j] += v; |
147 preflow[j] += v; |
148 |
148 |
149 |
149 |
150 //Modifiyng the head |
150 //Modifiyng the target |
151 modify_excess(G.head(j),v); |
151 modify_excess(G.target(j),v); |
152 |
152 |
153 //Modifiyng the tail |
153 //Modifiyng the source |
154 modify_excess(G.tail(j),-v); |
154 modify_excess(G.source(j),-v); |
155 |
155 |
156 } |
156 } |
157 |
157 |
158 //Gives the active node to work with |
158 //Gives the active node to work with |
159 //(depending on the implementation to be used) |
159 //(depending on the implementation to be used) |
270 bfs_queue.pop(); |
270 bfs_queue.pop(); |
271 int l=level[v]+1; |
271 int l=level[v]+1; |
272 |
272 |
273 InEdgeIt e; |
273 InEdgeIt e; |
274 for(G.first(e,v); G.valid(e); G.next(e)) { |
274 for(G.first(e,v); G.valid(e); G.next(e)) { |
275 Node w=G.tail(e); |
275 Node w=G.source(e); |
276 if ( level[w] == number_of_nodes && w != s ) { |
276 if ( level[w] == number_of_nodes && w != s ) { |
277 bfs_queue.push(w); |
277 bfs_queue.push(w); |
278 //Node first=level_list[l]; |
278 //Node first=level_list[l]; |
279 //if ( G.valid(first) ) left.set(first,w); |
279 //if ( G.valid(first) ) left.set(first,w); |
280 //right.set(w,first); |
280 //right.set(w,first); |
308 |
308 |
309 |
309 |
310 //we push as much preflow from s as possible to start with |
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)){ |
311 for(OutEdgeIt j=G.template first<OutEdgeIt>(s); G.valid(j); G.next(j)){ |
312 modify_preflow(j,capacity[j] ); |
312 modify_preflow(j,capacity[j] ); |
313 make_active(G.head(j)); |
313 make_active(G.target(j)); |
314 int lev=level[G.head(j)]; |
314 int lev=level[G.target(j)]; |
315 if(highest_active<lev){ |
315 if(highest_active<lev){ |
316 highest_active=lev; |
316 highest_active=lev; |
317 } |
317 } |
318 } |
318 } |
319 //cout<<highest_active<<endl; |
319 //cout<<highest_active<<endl; |
323 //If the preflow is less than the capacity on the given edge |
323 //If the preflow is less than the capacity on the given edge |
324 //then it is an edge in the residual graph |
324 //then it is an edge in the residual graph |
325 bool is_admissible_forward_edge(Edge j, int& new_level){ |
325 bool is_admissible_forward_edge(Edge j, int& new_level){ |
326 |
326 |
327 if (capacity[j]>preflow[j]){ |
327 if (capacity[j]>preflow[j]){ |
328 if(level[G.tail(j)]==level[G.head(j)]+1){ |
328 if(level[G.source(j)]==level[G.target(j)]+1){ |
329 return true; |
329 return true; |
330 } |
330 } |
331 else{ |
331 else{ |
332 if (level[G.head(j)] < new_level) |
332 if (level[G.target(j)] < new_level) |
333 new_level=level[G.head(j)]; |
333 new_level=level[G.target(j)]; |
334 } |
334 } |
335 } |
335 } |
336 return false; |
336 return false; |
337 } |
337 } |
338 |
338 |
339 //If the preflow is greater than 0 on the given edge |
339 //If the preflow is greater than 0 on the given edge |
340 //then the edge reversd is an edge in the residual graph |
340 //then the edge reversd is an edge in the residual graph |
341 bool is_admissible_backward_edge(Edge j, int& new_level){ |
341 bool is_admissible_backward_edge(Edge j, int& new_level){ |
342 |
342 |
343 if (0<preflow[j]){ |
343 if (0<preflow[j]){ |
344 if(level[G.tail(j)]==level[G.head(j)]-1){ |
344 if(level[G.source(j)]==level[G.target(j)]-1){ |
345 |
345 |
346 return true; |
346 return true; |
347 } |
347 } |
348 else{ |
348 else{ |
349 if (level[G.tail(j)] < new_level) |
349 if (level[G.source(j)] < new_level) |
350 new_level=level[G.tail(j)]; |
350 new_level=level[G.source(j)]; |
351 } |
351 } |
352 |
352 |
353 } |
353 } |
354 return false; |
354 return false; |
355 } |
355 } |
386 |
386 |
387 if (is_admissible_forward_edge(j,new_level)){ |
387 if (is_admissible_forward_edge(j,new_level)){ |
388 v=min(e,capacity[j] - preflow[j]); |
388 v=min(e,capacity[j] - preflow[j]); |
389 e -= v; |
389 e -= v; |
390 //New node might become active |
390 //New node might become active |
391 if (excess[G.head(j)]==0){ |
391 if (excess[G.target(j)]==0){ |
392 make_active(G.head(j)); |
392 make_active(G.target(j)); |
393 } |
393 } |
394 modify_preflow(j,v); |
394 modify_preflow(j,v); |
395 } |
395 } |
396 G.next(j); |
396 G.next(j); |
397 } |
397 } |
402 while (G.valid(j) && e){ |
402 while (G.valid(j) && e){ |
403 if (is_admissible_backward_edge(j,new_level)){ |
403 if (is_admissible_backward_edge(j,new_level)){ |
404 v=min(e,preflow[j]); |
404 v=min(e,preflow[j]); |
405 e -= v; |
405 e -= v; |
406 //New node might become active |
406 //New node might become active |
407 if (excess[G.tail(j)]==0){ |
407 if (excess[G.source(j)]==0){ |
408 make_active(G.tail(j)); |
408 make_active(G.source(j)); |
409 } |
409 } |
410 modify_preflow(j,-v); |
410 modify_preflow(j,-v); |
411 } |
411 } |
412 G.next(j); |
412 G.next(j); |
413 } |
413 } |