354 original_edge.set(f, e); |
354 original_edge.set(f, e); |
355 residual_capacity.update(); |
355 residual_capacity.update(); |
356 residual_capacity.set(f, res_graph.free(e)); |
356 residual_capacity.set(f, res_graph.free(e)); |
357 } |
357 } |
358 } |
358 } |
|
359 |
|
360 bool __augment=true; |
|
361 |
|
362 while (__augment) { |
|
363 __augment=false; |
|
364 //computing blocking flow with dfs |
|
365 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
|
366 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
|
367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
|
368 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
|
369 //invalid iterators for sources |
|
370 |
|
371 typename MutableGraph::NodeMap<Number> free(F); |
|
372 |
|
373 dfs.pushAndSetReached(sF); |
|
374 while (!dfs.finished()) { |
|
375 ++dfs; |
|
376 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
|
377 if (dfs.isBNodeNewlyReached()) { |
|
378 typename MutableGraph::Node v=F.aNode(dfs); |
|
379 typename MutableGraph::Node w=F.bNode(dfs); |
|
380 pred.set(w, dfs); |
|
381 if (F.valid(pred.get(v))) { |
|
382 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
383 } else { |
|
384 free.set(w, residual_capacity.get(dfs)); |
|
385 } |
|
386 if (w==tF) { |
|
387 __augment=true; |
|
388 _augment=true; |
|
389 break; |
|
390 } |
|
391 |
|
392 } else { |
|
393 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
|
394 } |
|
395 } |
|
396 } |
|
397 |
|
398 if (__augment) { |
|
399 typename MutableGraph::Node n=tF; |
|
400 Number augment_value=free.get(tF); |
|
401 while (F.valid(pred.get(n))) { |
|
402 typename MutableGraph::Edge e=pred.get(n); |
|
403 res_graph.augment(original_edge.get(e), augment_value); |
|
404 n=F.tail(e); |
|
405 if (residual_capacity.get(e)==augment_value) |
|
406 F.erase(e); |
|
407 else |
|
408 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
409 } |
|
410 } |
|
411 |
|
412 } |
|
413 |
|
414 return _augment; |
|
415 } |
|
416 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
|
417 bool _augment=false; |
|
418 |
|
419 AugGraph res_graph(*G, *flow, *capacity); |
|
420 |
|
421 //bfs for distances on the residual graph |
|
422 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
423 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
|
424 bfs.pushAndSetReached(s); |
|
425 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
426 |
|
427 //F will contain the physical copy of the residual graph |
|
428 //with the set of edges which areon shortest paths |
|
429 MutableGraph F; |
|
430 typename AugGraph::NodeMap<typename MutableGraph::Node> |
|
431 res_graph_to_F(res_graph); |
|
432 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
433 res_graph_to_F.set(n, F.addNode()); |
|
434 } |
|
435 typename MutableGraph::Node sF=res_graph_to_F.get(s); |
|
436 typename MutableGraph::Node tF=res_graph_to_F.get(t); |
|
437 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
|
438 typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
439 |
|
440 while ( !bfs.finished() ) { |
|
441 AugOutEdgeIt e=bfs; |
|
442 if (res_graph.valid(e)) { |
|
443 if (bfs.isBNodeNewlyReached()) { |
|
444 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
445 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
446 original_edge.update(); |
|
447 original_edge.set(f, e); |
|
448 residual_capacity.update(); |
|
449 residual_capacity.set(f, res_graph.free(e)); |
|
450 } else { |
|
451 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
|
452 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
|
453 original_edge.update(); |
|
454 original_edge.set(f, e); |
|
455 residual_capacity.update(); |
|
456 residual_capacity.set(f, res_graph.free(e)); |
|
457 } |
|
458 } |
|
459 } |
|
460 ++bfs; |
|
461 } //computing distances from s in the residual graph |
359 |
462 |
360 bool __augment=true; |
463 bool __augment=true; |
361 |
464 |
362 while (__augment) { |
465 while (__augment) { |
363 __augment=false; |
466 __augment=false; |