430 } |
430 } |
431 |
431 |
432 return _augment; |
432 return _augment; |
433 } |
433 } |
434 |
434 |
435 // template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
435 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
436 // bool _augment=false; |
436 bool _augment=false; |
437 |
437 |
438 // AugGraph res_graph(*G, *flow, *capacity); |
438 AugGraph res_graph(gw, *flow, *capacity); |
439 |
439 |
440 // //bfs for distances on the residual graph |
440 //bfs for distances on the residual graph |
441 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
441 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
442 // BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
442 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
443 // bfs.pushAndSetReached(s); |
443 bfs.pushAndSetReached(s); |
444 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
444 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
445 |
445 |
446 // //F will contain the physical copy of the residual graph |
446 //F will contain the physical copy of the residual graph |
447 // //with the set of edges which areon shortest paths |
447 //with the set of edges which areon shortest paths |
448 // MutableGraph F; |
448 MutableGraph F; |
449 // typename AugGraph::NodeMap<typename MutableGraph::Node> |
449 typename AugGraph::NodeMap<typename MutableGraph::Node> |
450 // res_graph_to_F(res_graph); |
450 res_graph_to_F(res_graph); |
451 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
451 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
452 // res_graph_to_F.set(n, F.addNode()); |
452 res_graph_to_F.set(n, F.addNode()); |
453 // } |
453 } |
454 // typename MutableGraph::Node sF=res_graph_to_F.get(s); |
454 typename MutableGraph::Node sF=res_graph_to_F.get(s); |
455 // typename MutableGraph::Node tF=res_graph_to_F.get(t); |
455 typename MutableGraph::Node tF=res_graph_to_F.get(t); |
456 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
456 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
457 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
457 typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
458 |
458 |
459 // while ( !bfs.finished() ) { |
459 while ( !bfs.finished() ) { |
460 // AugOutEdgeIt e=bfs; |
460 AugOutEdgeIt e=bfs; |
461 // if (res_graph.valid(e)) { |
461 if (res_graph.valid(e)) { |
462 // if (bfs.isBNodeNewlyReached()) { |
462 if (bfs.isBNodeNewlyReached()) { |
463 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
463 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
464 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
464 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
465 // original_edge.update(); |
465 original_edge.update(); |
466 // original_edge.set(f, e); |
466 original_edge.set(f, e); |
467 // residual_capacity.update(); |
467 residual_capacity.update(); |
468 // residual_capacity.set(f, res_graph.free(e)); |
468 residual_capacity.set(f, res_graph.free(e)); |
469 // } else { |
469 } else { |
470 // if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
470 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
471 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
471 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
472 // original_edge.update(); |
472 original_edge.update(); |
473 // original_edge.set(f, e); |
473 original_edge.set(f, e); |
474 // residual_capacity.update(); |
474 residual_capacity.update(); |
475 // residual_capacity.set(f, res_graph.free(e)); |
475 residual_capacity.set(f, res_graph.free(e)); |
476 // } |
476 } |
477 // } |
477 } |
478 // } |
478 } |
479 // ++bfs; |
479 ++bfs; |
480 // } //computing distances from s in the residual graph |
480 } //computing distances from s in the residual graph |
481 |
481 |
482 // bool __augment=true; |
482 bool __augment=true; |
483 |
483 |
484 // while (__augment) { |
484 while (__augment) { |
485 // __augment=false; |
485 __augment=false; |
486 // //computing blocking flow with dfs |
486 //computing blocking flow with dfs |
487 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
487 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
488 // DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
488 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
489 // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
489 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
490 // pred.set(sF, typename MutableGraph::Edge(INVALID)); |
490 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
491 // //invalid iterators for sources |
491 //invalid iterators for sources |
492 |
492 |
493 // typename MutableGraph::NodeMap<Number> free(F); |
493 typename MutableGraph::NodeMap<Number> free(F); |
494 |
494 |
495 // dfs.pushAndSetReached(sF); |
495 dfs.pushAndSetReached(sF); |
496 // while (!dfs.finished()) { |
496 while (!dfs.finished()) { |
497 // ++dfs; |
497 ++dfs; |
498 // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
498 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
499 // if (dfs.isBNodeNewlyReached()) { |
499 if (dfs.isBNodeNewlyReached()) { |
500 // typename MutableGraph::Node v=F.aNode(dfs); |
500 typename MutableGraph::Node v=F.aNode(dfs); |
501 // typename MutableGraph::Node w=F.bNode(dfs); |
501 typename MutableGraph::Node w=F.bNode(dfs); |
502 // pred.set(w, dfs); |
502 pred.set(w, dfs); |
503 // if (F.valid(pred.get(v))) { |
503 if (F.valid(pred.get(v))) { |
504 // free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
504 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
505 // } else { |
505 } else { |
506 // free.set(w, residual_capacity.get(dfs)); |
506 free.set(w, residual_capacity.get(dfs)); |
507 // } |
507 } |
508 // if (w==tF) { |
508 if (w==tF) { |
509 // __augment=true; |
509 __augment=true; |
510 // _augment=true; |
510 _augment=true; |
511 // break; |
511 break; |
512 // } |
512 } |
513 |
513 |
514 // } else { |
514 } else { |
515 // F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
515 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
516 // } |
516 } |
517 // } |
517 } |
518 // } |
518 } |
519 |
519 |
520 // if (__augment) { |
520 if (__augment) { |
521 // typename MutableGraph::Node n=tF; |
521 typename MutableGraph::Node n=tF; |
522 // Number augment_value=free.get(tF); |
522 Number augment_value=free.get(tF); |
523 // while (F.valid(pred.get(n))) { |
523 while (F.valid(pred.get(n))) { |
524 // typename MutableGraph::Edge e=pred.get(n); |
524 typename MutableGraph::Edge e=pred.get(n); |
525 // res_graph.augment(original_edge.get(e), augment_value); |
525 res_graph.augment(original_edge.get(e), augment_value); |
526 // n=F.tail(e); |
526 n=F.tail(e); |
527 // if (residual_capacity.get(e)==augment_value) |
527 if (residual_capacity.get(e)==augment_value) |
528 // F.erase(e); |
528 F.erase(e); |
529 // else |
529 else |
530 // residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
530 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
531 // } |
531 } |
532 // } |
532 } |
533 |
533 |
534 // } |
534 } |
535 |
535 |
536 // return _augment; |
536 return _augment; |
537 // } |
537 } |
|
538 |
538 // bool augmentOnBlockingFlow2() { |
539 // bool augmentOnBlockingFlow2() { |
539 // bool _augment=false; |
540 // bool _augment=false; |
540 |
541 |
541 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
542 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
542 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
543 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |