317 bool _augment=false; |
317 bool _augment=false; |
318 |
318 |
319 AugGraph res_graph(*G, *flow, *capacity); |
319 AugGraph res_graph(*G, *flow, *capacity); |
320 |
320 |
321 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
321 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
322 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
322 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); |
323 |
323 |
324 bfs.pushAndSetReached(s); |
324 bfs.pushAndSetReached(s); |
325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
326 while ( !bfs.finished() ) { |
326 while ( !bfs.finished() ) { |
327 AugOutEdgeIt e=bfs; |
327 AugOutEdgeIt e=bfs; |
360 bool __augment=true; |
360 bool __augment=true; |
361 |
361 |
362 while (__augment) { |
362 while (__augment) { |
363 __augment=false; |
363 __augment=false; |
364 //computing blocking flow with dfs |
364 //computing blocking flow with dfs |
365 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
365 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
366 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
366 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
368 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
368 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
369 //invalid iterators for sources |
369 //invalid iterators for sources |
370 |
370 |
371 typename MutableGraph::NodeMap<Number> free(F); |
371 typename MutableGraph::NodeMap<Number> free(F); |
418 |
418 |
419 AugGraph res_graph(*G, *flow, *capacity); |
419 AugGraph res_graph(*G, *flow, *capacity); |
420 |
420 |
421 //bfs for distances on the residual graph |
421 //bfs for distances on the residual graph |
422 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
422 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
423 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
423 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); |
424 bfs.pushAndSetReached(s); |
424 bfs.pushAndSetReached(s); |
425 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
425 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
426 |
426 |
427 //F will contain the physical copy of the residual graph |
427 //F will contain the physical copy of the residual graph |
428 //with the set of edges which areon shortest paths |
428 //with the set of edges which areon shortest paths |
463 bool __augment=true; |
463 bool __augment=true; |
464 |
464 |
465 while (__augment) { |
465 while (__augment) { |
466 __augment=false; |
466 __augment=false; |
467 //computing blocking flow with dfs |
467 //computing blocking flow with dfs |
468 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; |
468 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
469 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); |
469 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
470 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
470 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
471 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
471 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
472 //invalid iterators for sources |
472 //invalid iterators for sources |
473 |
473 |
474 typename MutableGraph::NodeMap<Number> free(F); |
474 typename MutableGraph::NodeMap<Number> free(F); |
525 typedef typename EAugGraph::Edge EAugEdge; |
525 typedef typename EAugGraph::Edge EAugEdge; |
526 |
526 |
527 EAugGraph res_graph(*G, *flow, *capacity); |
527 EAugGraph res_graph(*G, *flow, *capacity); |
528 |
528 |
529 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
529 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
530 BfsIterator4< |
530 BfsIterator5< |
531 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
531 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
532 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
532 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
533 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
533 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
534 |
534 |
535 bfs.pushAndSetReached(s); |
535 bfs.pushAndSetReached(s); |
536 |
536 |
537 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
537 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
550 while (__augment) { |
550 while (__augment) { |
551 |
551 |
552 __augment=false; |
552 __augment=false; |
553 //computing blocking flow with dfs |
553 //computing blocking flow with dfs |
554 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
554 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
555 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
555 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
556 dfs(res_graph); |
556 dfs(res_graph); |
557 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
557 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
558 pred.set(s, EAugEdge(INVALID)); |
558 pred.set(s, EAugEdge(INVALID)); |
559 //invalid iterators for sources |
559 //invalid iterators for sources |
560 |
560 |
852 typedef typename EAugGraph::Edge EAugEdge; |
852 typedef typename EAugGraph::Edge EAugEdge; |
853 |
853 |
854 EAugGraph res_graph(*G, *flow, *capacity); |
854 EAugGraph res_graph(*G, *flow, *capacity); |
855 |
855 |
856 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
856 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
857 BfsIterator4< |
857 BfsIterator5< |
858 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
858 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
859 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
859 /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
860 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
860 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
861 |
861 |
862 |
862 |
863 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
863 //typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
864 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
864 for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
892 while (__augment) { |
892 while (__augment) { |
893 |
893 |
894 __augment=false; |
894 __augment=false; |
895 //computing blocking flow with dfs |
895 //computing blocking flow with dfs |
896 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
896 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
897 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
897 DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
898 dfs(res_graph); |
898 dfs(res_graph); |
899 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
899 typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
900 //pred.set(s, EAugEdge(INVALID)); |
900 //pred.set(s, EAugEdge(INVALID)); |
901 //invalid iterators for sources |
901 //invalid iterators for sources |
902 |
902 |