equal
deleted
inserted
replaced
273 |
273 |
274 bool augmentOnShortestPath() { |
274 bool augmentOnShortestPath() { |
275 ResGW res_graph(*g, *capacity, *flow); |
275 ResGW res_graph(*g, *capacity, *flow); |
276 bool _augment=false; |
276 bool _augment=false; |
277 |
277 |
278 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
278 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
279 bfs.pushAndSetReached(s); |
279 bfs.pushAndSetReached(s); |
280 |
280 |
281 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); |
281 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); |
282 pred.set(s, INVALID); |
282 pred.set(s, INVALID); |
283 |
283 |
337 typedef MutableGraph MG; |
337 typedef MutableGraph MG; |
338 bool _augment=false; |
338 bool _augment=false; |
339 |
339 |
340 ResGW res_graph(*g, *capacity, *flow); |
340 ResGW res_graph(*g, *capacity, *flow); |
341 |
341 |
342 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
342 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
343 |
343 |
344 bfs.pushAndSetReached(s); |
344 bfs.pushAndSetReached(s); |
345 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
345 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
346 DistanceMap<ResGW> dist(res_graph); |
346 DistanceMap<ResGW> dist(res_graph); |
347 while ( !bfs.finished() ) { |
347 while ( !bfs.finished() ) { |
389 |
389 |
390 while (__augment) { |
390 while (__augment) { |
391 __augment=false; |
391 __augment=false; |
392 //computing blocking flow with dfs |
392 //computing blocking flow with dfs |
393 |
393 |
394 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F); |
394 DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F); |
395 typename MG::NodeMap<typename MG::Edge> pred(F); |
395 typename MG::NodeMap<typename MG::Edge> pred(F); |
396 pred.set(sF, INVALID); |
396 pred.set(sF, INVALID); |
397 //invalid iterators for sources |
397 //invalid iterators for sources |
398 |
398 |
399 typename MG::NodeMap<Number> free(F); |
399 typename MG::NodeMap<Number> free(F); |
447 bool _augment=false; |
447 bool _augment=false; |
448 |
448 |
449 ResGW res_graph(*g, *capacity, *flow); |
449 ResGW res_graph(*g, *capacity, *flow); |
450 |
450 |
451 //bfs for distances on the residual graph |
451 //bfs for distances on the residual graph |
452 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
452 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
453 bfs.pushAndSetReached(s); |
453 bfs.pushAndSetReached(s); |
454 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
454 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
455 |
455 |
456 //F will contain the physical copy of the residual graph |
456 //F will contain the physical copy of the residual graph |
457 //with the set of edges which are on shortest paths |
457 //with the set of edges which are on shortest paths |
495 bool __augment=true; |
495 bool __augment=true; |
496 |
496 |
497 while (__augment) { |
497 while (__augment) { |
498 __augment=false; |
498 __augment=false; |
499 //computing blocking flow with dfs |
499 //computing blocking flow with dfs |
500 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F); |
500 DfsIterator< MG, typename MG::NodeMap<bool> > dfs(F); |
501 typename MG::NodeMap<typename MG::Edge> pred(F); |
501 typename MG::NodeMap<typename MG::Edge> pred(F); |
502 pred.set(sF, INVALID); |
502 pred.set(sF, INVALID); |
503 //invalid iterators for sources |
503 //invalid iterators for sources |
504 |
504 |
505 typename MG::NodeMap<Number> free(F); |
505 typename MG::NodeMap<Number> free(F); |
551 bool augmentOnBlockingFlow2() { |
551 bool augmentOnBlockingFlow2() { |
552 bool _augment=false; |
552 bool _augment=false; |
553 |
553 |
554 ResGW res_graph(*g, *capacity, *flow); |
554 ResGW res_graph(*g, *capacity, *flow); |
555 |
555 |
556 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
556 BfsIterator< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
557 |
557 |
558 bfs.pushAndSetReached(s); |
558 bfs.pushAndSetReached(s); |
559 DistanceMap<ResGW> dist(res_graph); |
559 DistanceMap<ResGW> dist(res_graph); |
560 while ( !bfs.finished() ) { |
560 while ( !bfs.finished() ) { |
561 ResGWOutEdgeIt e=bfs; |
561 ResGWOutEdgeIt e=bfs; |
591 |
591 |
592 while (__augment) { |
592 while (__augment) { |
593 |
593 |
594 __augment=false; |
594 __augment=false; |
595 //computing blocking flow with dfs |
595 //computing blocking flow with dfs |
596 DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> > |
596 DfsIterator< ErasingResGW, typename ErasingResGW::NodeMap<bool> > |
597 dfs(erasing_res_graph); |
597 dfs(erasing_res_graph); |
598 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> |
598 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> |
599 pred(erasing_res_graph); |
599 pred(erasing_res_graph); |
600 pred.set(s, INVALID); |
600 pred.set(s, INVALID); |
601 //invalid iterators for sources |
601 //invalid iterators for sources |
726 // bool augmentOnShortestPath() { |
726 // bool augmentOnShortestPath() { |
727 // AugGraph res_graph(*G, *flow, *capacity); |
727 // AugGraph res_graph(*G, *flow, *capacity); |
728 // bool _augment=false; |
728 // bool _augment=false; |
729 |
729 |
730 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
730 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
731 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); |
731 // BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); |
732 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
732 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
733 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
733 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
734 // if ((S->get(s)) && (used.get(s)<1) ) { |
734 // if ((S->get(s)) && (used.get(s)<1) ) { |
735 // //Number u=0; |
735 // //Number u=0; |
736 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
736 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
916 // typedef typename EAugGraph::Edge EAugEdge; |
916 // typedef typename EAugGraph::Edge EAugEdge; |
917 |
917 |
918 // EAugGraph res_graph(*G, *flow, *capacity); |
918 // EAugGraph res_graph(*G, *flow, *capacity); |
919 |
919 |
920 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
920 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
921 // BfsIterator5< |
921 // BfsIterator< |
922 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
922 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
923 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
923 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
924 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
924 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
925 |
925 |
926 |
926 |
956 // while (__augment) { |
956 // while (__augment) { |
957 |
957 |
958 // __augment=false; |
958 // __augment=false; |
959 // //computing blocking flow with dfs |
959 // //computing blocking flow with dfs |
960 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
960 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
961 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
961 // DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
962 // dfs(res_graph); |
962 // dfs(res_graph); |
963 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
963 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID); |
964 // //pred.set(s, EAugEdge(INVALID)); |
964 // //pred.set(s, EAugEdge(INVALID)); |
965 // //invalid iterators for sources |
965 // //invalid iterators for sources |
966 |
966 |