equal
deleted
inserted
replaced
272 |
272 |
273 bool augmentOnShortestPath() { |
273 bool augmentOnShortestPath() { |
274 ResGW res_graph(*g, *flow, *capacity); |
274 ResGW res_graph(*g, *flow, *capacity); |
275 bool _augment=false; |
275 bool _augment=false; |
276 |
276 |
277 typedef typename ResGW::NodeMap<bool> ReachedMap; |
277 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
278 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
|
279 bfs.pushAndSetReached(s); |
278 bfs.pushAndSetReached(s); |
280 |
279 |
281 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); |
280 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); |
282 pred.set(s, INVALID); |
281 pred.set(s, INVALID); |
283 |
282 |
337 typedef MutableGraph MG; |
336 typedef MutableGraph MG; |
338 bool _augment=false; |
337 bool _augment=false; |
339 |
338 |
340 ResGW res_graph(*g, *flow, *capacity); |
339 ResGW res_graph(*g, *flow, *capacity); |
341 |
340 |
342 typedef typename ResGW::NodeMap<bool> ReachedMap; |
341 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
343 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
|
344 |
342 |
345 bfs.pushAndSetReached(s); |
343 bfs.pushAndSetReached(s); |
346 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
344 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
347 DistanceMap<ResGW> dist(res_graph); |
345 DistanceMap<ResGW> dist(res_graph); |
348 while ( !bfs.finished() ) { |
346 while ( !bfs.finished() ) { |
389 bool __augment=true; |
387 bool __augment=true; |
390 |
388 |
391 while (__augment) { |
389 while (__augment) { |
392 __augment=false; |
390 __augment=false; |
393 //computing blocking flow with dfs |
391 //computing blocking flow with dfs |
394 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; |
392 |
395 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); |
393 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F); |
396 typename MG::NodeMap<typename MG::Edge> pred(F); |
394 typename MG::NodeMap<typename MG::Edge> pred(F); |
397 pred.set(sF, INVALID); |
395 pred.set(sF, INVALID); |
398 //invalid iterators for sources |
396 //invalid iterators for sources |
399 |
397 |
400 typename MG::NodeMap<Number> free(F); |
398 typename MG::NodeMap<Number> free(F); |
448 bool _augment=false; |
446 bool _augment=false; |
449 |
447 |
450 ResGW res_graph(*g, *flow, *capacity); |
448 ResGW res_graph(*g, *flow, *capacity); |
451 |
449 |
452 //bfs for distances on the residual graph |
450 //bfs for distances on the residual graph |
453 typedef typename ResGW::NodeMap<bool> ReachedMap; |
451 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
454 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
|
455 bfs.pushAndSetReached(s); |
452 bfs.pushAndSetReached(s); |
456 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
453 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
457 |
454 |
458 //F will contain the physical copy of the residual graph |
455 //F will contain the physical copy of the residual graph |
459 //with the set of edges which are on shortest paths |
456 //with the set of edges which are on shortest paths |
497 bool __augment=true; |
494 bool __augment=true; |
498 |
495 |
499 while (__augment) { |
496 while (__augment) { |
500 __augment=false; |
497 __augment=false; |
501 //computing blocking flow with dfs |
498 //computing blocking flow with dfs |
502 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; |
499 DfsIterator5< MG, typename MG::NodeMap<bool> > dfs(F); |
503 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); |
|
504 typename MG::NodeMap<typename MG::Edge> pred(F); |
500 typename MG::NodeMap<typename MG::Edge> pred(F); |
505 pred.set(sF, INVALID); |
501 pred.set(sF, INVALID); |
506 //invalid iterators for sources |
502 //invalid iterators for sources |
507 |
503 |
508 typename MG::NodeMap<Number> free(F); |
504 typename MG::NodeMap<Number> free(F); |
554 bool augmentOnBlockingFlow2() { |
550 bool augmentOnBlockingFlow2() { |
555 bool _augment=false; |
551 bool _augment=false; |
556 |
552 |
557 ResGW res_graph(*g, *flow, *capacity); |
553 ResGW res_graph(*g, *flow, *capacity); |
558 |
554 |
559 typedef typename ResGW::NodeMap<bool> ReachedMap; |
555 BfsIterator5< ResGW, typename ResGW::NodeMap<bool> > bfs(res_graph); |
560 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
|
561 |
556 |
562 bfs.pushAndSetReached(s); |
557 bfs.pushAndSetReached(s); |
563 DistanceMap<ResGW> dist(res_graph); |
558 DistanceMap<ResGW> dist(res_graph); |
564 while ( !bfs.finished() ) { |
559 while ( !bfs.finished() ) { |
565 ResGWOutEdgeIt e=bfs; |
560 ResGWOutEdgeIt e=bfs; |
595 |
590 |
596 while (__augment) { |
591 while (__augment) { |
597 |
592 |
598 __augment=false; |
593 __augment=false; |
599 //computing blocking flow with dfs |
594 //computing blocking flow with dfs |
600 typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap; |
595 DfsIterator5< ErasingResGW, typename ErasingResGW::NodeMap<bool> > |
601 DfsIterator5< ErasingResGW, BlockingReachedMap > |
|
602 dfs(erasing_res_graph); |
596 dfs(erasing_res_graph); |
603 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> |
597 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> |
604 pred(erasing_res_graph); |
598 pred(erasing_res_graph); |
605 pred.set(s, INVALID); |
599 pred.set(s, INVALID); |
606 //invalid iterators for sources |
600 //invalid iterators for sources |