7 |
7 |
8 #include <hugo/graph_wrapper.h> |
8 #include <hugo/graph_wrapper.h> |
9 #include <bfs_dfs.h> |
9 #include <bfs_dfs.h> |
10 #include <hugo/invalid.h> |
10 #include <hugo/invalid.h> |
11 #include <hugo/maps.h> |
11 #include <hugo/maps.h> |
12 #include <tight_edge_filter_map.h> |
12 #include <hugo/tight_edge_filter_map.h> |
13 |
13 |
14 /// \file |
14 /// \file |
15 /// \brief Maximum flow algorithms. |
15 /// \brief Maximum flow algorithms. |
16 /// \ingroup galgs |
16 /// \ingroup galgs |
17 |
17 |
245 |
245 |
246 template <typename Graph, typename Num, typename CapMap, typename FlowMap> |
246 template <typename Graph, typename Num, typename CapMap, typename FlowMap> |
247 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() |
247 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath() |
248 { |
248 { |
249 ResGW res_graph(*g, *capacity, *flow); |
249 ResGW res_graph(*g, *capacity, *flow); |
|
250 typename ResGW::ResCap res_cap(res_graph); |
|
251 |
250 bool _augment=false; |
252 bool _augment=false; |
251 |
253 |
252 //ReachedMap level(res_graph); |
254 //ReachedMap level(res_graph); |
253 for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); |
255 for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); |
254 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); |
256 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); |
265 if (e!=INVALID && bfs.isBNodeNewlyReached()) { |
267 if (e!=INVALID && bfs.isBNodeNewlyReached()) { |
266 Node v=res_graph.tail(e); |
268 Node v=res_graph.tail(e); |
267 Node w=res_graph.head(e); |
269 Node w=res_graph.head(e); |
268 pred.set(w, e); |
270 pred.set(w, e); |
269 if (pred[v]!=INVALID) { |
271 if (pred[v]!=INVALID) { |
270 free.set(w, std::min(free[v], res_graph.resCap(e))); |
272 free.set(w, std::min(free[v], res_cap[e])); |
271 } else { |
273 } else { |
272 free.set(w, res_graph.resCap(e)); |
274 free.set(w, res_cap[e]); |
273 } |
275 } |
274 if (res_graph.head(e)==t) { _augment=true; break; } |
276 if (res_graph.head(e)==t) { _augment=true; break; } |
275 } |
277 } |
276 |
278 |
277 ++bfs; |
279 ++bfs; |
293 |
295 |
294 template <typename Graph, typename Num, typename CapMap, typename FlowMap> |
296 template <typename Graph, typename Num, typename CapMap, typename FlowMap> |
295 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2() |
297 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath2() |
296 { |
298 { |
297 ResGW res_graph(*g, *capacity, *flow); |
299 ResGW res_graph(*g, *capacity, *flow); |
|
300 typename ResGW::ResCap res_cap(res_graph); |
|
301 |
298 bool _augment=false; |
302 bool _augment=false; |
299 |
303 |
300 if (status!=AFTER_FAST_AUGMENTING) { |
304 if (status!=AFTER_FAST_AUGMENTING) { |
301 for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); |
305 for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); |
302 number_of_augmentations=1; |
306 number_of_augmentations=1; |
322 if (e!=INVALID && bfs.isBNodeNewlyReached()) { |
326 if (e!=INVALID && bfs.isBNodeNewlyReached()) { |
323 Node v=res_graph.tail(e); |
327 Node v=res_graph.tail(e); |
324 Node w=res_graph.head(e); |
328 Node w=res_graph.head(e); |
325 pred.set(w, e); |
329 pred.set(w, e); |
326 if (pred[v]!=INVALID) { |
330 if (pred[v]!=INVALID) { |
327 free.set(w, std::min(free[v], res_graph.resCap(e))); |
331 free.set(w, std::min(free[v], res_cap[e])); |
328 } else { |
332 } else { |
329 free.set(w, res_graph.resCap(e)); |
333 free.set(w, res_cap[e]); |
330 } |
334 } |
331 if (res_graph.head(e)==t) { _augment=true; break; } |
335 if (res_graph.head(e)==t) { _augment=true; break; } |
332 } |
336 } |
333 |
337 |
334 ++bfs; |
338 ++bfs; |
355 { |
359 { |
356 typedef MutableGraph MG; |
360 typedef MutableGraph MG; |
357 bool _augment=false; |
361 bool _augment=false; |
358 |
362 |
359 ResGW res_graph(*g, *capacity, *flow); |
363 ResGW res_graph(*g, *capacity, *flow); |
|
364 typename ResGW::ResCap res_cap(res_graph); |
360 |
365 |
361 //bfs for distances on the residual graph |
366 //bfs for distances on the residual graph |
362 //ReachedMap level(res_graph); |
367 //ReachedMap level(res_graph); |
363 for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); |
368 for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0); |
364 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); |
369 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level); |
390 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], |
395 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], |
391 res_graph_to_F[res_graph.head(e)]); |
396 res_graph_to_F[res_graph.head(e)]); |
392 //original_edge.update(); |
397 //original_edge.update(); |
393 original_edge.set(f, e); |
398 original_edge.set(f, e); |
394 //residual_capacity.update(); |
399 //residual_capacity.update(); |
395 residual_capacity.set(f, res_graph.resCap(e)); |
400 residual_capacity.set(f, res_cap[e]); |
396 } else { |
401 } else { |
397 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { |
402 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { |
398 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], |
403 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], |
399 res_graph_to_F[res_graph.head(e)]); |
404 res_graph_to_F[res_graph.head(e)]); |
400 //original_edge.update(); |
405 //original_edge.update(); |
401 original_edge.set(f, e); |
406 original_edge.set(f, e); |
402 //residual_capacity.update(); |
407 //residual_capacity.update(); |
403 residual_capacity.set(f, res_graph.resCap(e)); |
408 residual_capacity.set(f, res_cap[e]); |
404 } |
409 } |
405 } |
410 } |
406 } |
411 } |
407 ++bfs; |
412 ++bfs; |
408 } //computing distances from s in the residual graph |
413 } //computing distances from s in the residual graph |
470 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() |
475 bool AugmentingFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2() |
471 { |
476 { |
472 bool _augment=false; |
477 bool _augment=false; |
473 |
478 |
474 ResGW res_graph(*g, *capacity, *flow); |
479 ResGW res_graph(*g, *capacity, *flow); |
|
480 typename ResGW::ResCap res_cap(res_graph); |
475 |
481 |
476 //Potential map, for distances from s |
482 //Potential map, for distances from s |
477 typename ResGW::template NodeMap<int> potential(res_graph, 0); |
483 typename ResGW::template NodeMap<int> potential(res_graph, 0); |
478 typedef ConstMap<typename ResGW::Edge, int> Const1Map; |
484 typedef ConstMap<typename ResGW::Edge, int> Const1Map; |
479 Const1Map const_1_map(1); |
485 Const1Map const_1_map(1); |
547 typename ErasingResGW::Node w=erasing_res_graph.head(dfs); |
553 typename ErasingResGW::Node w=erasing_res_graph.head(dfs); |
548 |
554 |
549 pred.set(w, typename ErasingResGW::Edge(dfs)); |
555 pred.set(w, typename ErasingResGW::Edge(dfs)); |
550 if (pred[v]!=INVALID) { |
556 if (pred[v]!=INVALID) { |
551 free1.set |
557 free1.set |
552 (w, std::min(free1[v], res_graph.resCap |
558 (w, std::min(free1[v], res_cap |
553 (typename ErasingResGW::Edge(dfs)))); |
559 [typename ErasingResGW::Edge(dfs)])); |
554 } else { |
560 } else { |
555 free1.set |
561 free1.set |
556 (w, res_graph.resCap |
562 (w, res_cap |
557 (typename ErasingResGW::Edge(dfs))); |
563 [typename ErasingResGW::Edge(dfs)]); |
558 } |
564 } |
559 |
565 |
560 if (w==t) { |
566 if (w==t) { |
561 __augment=true; |
567 __augment=true; |
562 _augment=true; |
568 _augment=true; |
574 Num augment_value=free1[n]; |
580 Num augment_value=free1[n]; |
575 while (pred[n]!=INVALID) { |
581 while (pred[n]!=INVALID) { |
576 typename ErasingResGW::Edge e=pred[n]; |
582 typename ErasingResGW::Edge e=pred[n]; |
577 res_graph.augment(e, augment_value); |
583 res_graph.augment(e, augment_value); |
578 n=erasing_res_graph.tail(e); |
584 n=erasing_res_graph.tail(e); |
579 if (res_graph.resCap(e)==0) |
585 if (res_cap[e]==0) |
580 erasing_res_graph.erase(e); |
586 erasing_res_graph.erase(e); |
581 } |
587 } |
582 } |
588 } |
583 |
589 |
584 } //while (__augment) |
590 } //while (__augment) |