245 S get(Node nit) const { return node_map.get(nit); } |
246 S get(Node nit) const { return node_map.get(nit); } |
246 }; |
247 }; |
247 }; |
248 }; |
248 |
249 |
249 |
250 |
250 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap> |
251 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
251 class MaxFlow { |
252 class MaxFlow { |
252 protected: |
253 protected: |
253 typedef GraphWrapper GW; |
254 typedef typename Graph::Node Node; |
254 typedef typename GW::Node Node; |
255 typedef typename Graph::Edge Edge; |
255 typedef typename GW::Edge Edge; |
256 typedef typename Graph::EdgeIt EdgeIt; |
256 typedef typename GW::EdgeIt EdgeIt; |
257 typedef typename Graph::OutEdgeIt OutEdgeIt; |
257 typedef typename GW::OutEdgeIt OutEdgeIt; |
258 typedef typename Graph::InEdgeIt InEdgeIt; |
258 typedef typename GW::InEdgeIt InEdgeIt; |
259 const Graph* g; |
259 //const Graph* G; |
|
260 GW gw; |
|
261 Node s; |
260 Node s; |
262 Node t; |
261 Node t; |
263 FlowMap* flow; |
262 FlowMap* flow; |
264 const CapacityMap* capacity; |
263 const CapacityMap* capacity; |
265 typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW; |
264 typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW; |
266 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
265 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
267 typedef typename ResGW::Edge ResGWEdge; |
266 typedef typename ResGW::Edge ResGWEdge; |
268 public: |
267 public: |
269 |
268 |
270 MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
269 MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
271 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
270 g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
272 |
271 |
273 bool augmentOnShortestPath() { |
272 bool augmentOnShortestPath() { |
274 ResGW res_graph(gw, *flow, *capacity); |
273 ResGW res_graph(*g, *flow, *capacity); |
275 bool _augment=false; |
274 bool _augment=false; |
276 |
275 |
277 typedef typename ResGW::NodeMap<bool> ReachedMap; |
276 typedef typename ResGW::NodeMap<bool> ReachedMap; |
278 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
277 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
279 bfs.pushAndSetReached(s); |
278 bfs.pushAndSetReached(s); |
288 ResGWOutEdgeIt e=bfs; |
287 ResGWOutEdgeIt e=bfs; |
289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
290 Node v=res_graph.tail(e); |
289 Node v=res_graph.tail(e); |
291 Node w=res_graph.head(e); |
290 Node w=res_graph.head(e); |
292 pred.set(w, e); |
291 pred.set(w, e); |
293 if (res_graph.valid(pred.get(v))) { |
292 if (res_graph.valid(pred[v])) { |
294 free.set(w, std::min(free.get(v), res_graph.resCap(e))); |
293 free.set(w, std::min(free[v], res_graph.resCap(e))); |
295 } else { |
294 } else { |
296 free.set(w, res_graph.resCap(e)); |
295 free.set(w, res_graph.resCap(e)); |
297 } |
296 } |
298 if (res_graph.head(e)==t) { _augment=true; break; } |
297 if (res_graph.head(e)==t) { _augment=true; break; } |
299 } |
298 } |
315 } |
314 } |
316 |
315 |
317 template<typename MapGraphWrapper> |
316 template<typename MapGraphWrapper> |
318 class DistanceMap { |
317 class DistanceMap { |
319 protected: |
318 protected: |
320 MapGraphWrapper gw; |
319 const MapGraphWrapper* g; |
321 typename MapGraphWrapper::NodeMap<int> dist; |
320 typename MapGraphWrapper::NodeMap<int> dist; |
322 public: |
321 public: |
323 DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } |
322 DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { } |
324 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
323 void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; } |
325 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } |
324 int operator[](const typename MapGraphWrapper::Node& n) |
326 bool get(const typename MapGraphWrapper::Edge& e) const { |
325 { return dist[n]; } |
327 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); |
326 // int get(const typename MapGraphWrapper::Node& n) const { |
|
327 // return dist[n]; } |
|
328 // bool get(const typename MapGraphWrapper::Edge& e) const { |
|
329 // return (dist.get(g->tail(e))<dist.get(g->head(e))); } |
|
330 bool operator[](const typename MapGraphWrapper::Edge& e) const { |
|
331 return (dist[g->tail(e)]<dist[g->head(e)]); |
328 } |
332 } |
329 }; |
333 }; |
330 |
334 |
331 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
335 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
332 typedef MutableGraph MG; |
336 typedef MutableGraph MG; |
333 bool _augment=false; |
337 bool _augment=false; |
334 |
338 |
335 ResGW res_graph(gw, *flow, *capacity); |
339 ResGW res_graph(*g, *flow, *capacity); |
336 |
340 |
337 typedef typename ResGW::NodeMap<bool> ReachedMap; |
341 typedef typename ResGW::NodeMap<bool> ReachedMap; |
338 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
342 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
339 |
343 |
340 bfs.pushAndSetReached(s); |
344 bfs.pushAndSetReached(s); |
341 //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 |
342 DistanceMap<ResGW> dist(res_graph); |
346 DistanceMap<ResGW> dist(res_graph); |
343 while ( !bfs.finished() ) { |
347 while ( !bfs.finished() ) { |
344 ResGWOutEdgeIt e=bfs; |
348 ResGWOutEdgeIt e=bfs; |
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
349 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
346 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
350 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); |
347 } |
351 } |
348 ++bfs; |
352 ++bfs; |
349 } //computing distances from s in the residual graph |
353 } //computing distances from s in the residual graph |
350 |
354 |
351 MG F; |
355 MG F; |
357 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
361 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
358 res_graph_to_F.set(n, F.addNode()); |
362 res_graph_to_F.set(n, F.addNode()); |
359 } |
363 } |
360 } |
364 } |
361 |
365 |
362 typename MG::Node sF=res_graph_to_F.get(s); |
366 typename MG::Node sF=res_graph_to_F[s]; |
363 typename MG::Node tF=res_graph_to_F.get(t); |
367 typename MG::Node tF=res_graph_to_F[t]; |
364 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
368 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
365 typename MG::EdgeMap<Number> residual_capacity(F); |
369 typename MG::EdgeMap<Number> residual_capacity(F); |
366 |
370 |
367 //Making F to the graph containing the edges of the residual graph |
371 //Making F to the graph containing the edges of the residual graph |
368 //which are in some shortest paths |
372 //which are in some shortest paths |
369 { |
373 { |
370 typename FilterResGW::EdgeIt e; |
374 typename FilterResGW::EdgeIt e; |
371 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
375 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
372 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
376 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
373 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
377 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); |
374 original_edge.update(); |
378 original_edge.update(); |
375 original_edge.set(f, e); |
379 original_edge.set(f, e); |
376 residual_capacity.update(); |
380 residual_capacity.update(); |
377 residual_capacity.set(f, res_graph.resCap(e)); |
381 residual_capacity.set(f, res_graph.resCap(e)); |
378 //} |
382 //} |
398 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
402 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
399 if (dfs.isBNodeNewlyReached()) { |
403 if (dfs.isBNodeNewlyReached()) { |
400 typename MG::Node v=F.aNode(dfs); |
404 typename MG::Node v=F.aNode(dfs); |
401 typename MG::Node w=F.bNode(dfs); |
405 typename MG::Node w=F.bNode(dfs); |
402 pred.set(w, dfs); |
406 pred.set(w, dfs); |
403 if (F.valid(pred.get(v))) { |
407 if (F.valid(pred[v])) { |
404 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
408 free.set(w, std::min(free[v], residual_capacity[dfs])); |
405 } else { |
409 } else { |
406 free.set(w, residual_capacity.get(dfs)); |
410 free.set(w, residual_capacity[dfs]); |
407 } |
411 } |
408 if (w==tF) { |
412 if (w==tF) { |
409 __augment=true; |
413 __augment=true; |
410 _augment=true; |
414 _augment=true; |
411 break; |
415 break; |
417 } |
421 } |
418 } |
422 } |
419 |
423 |
420 if (__augment) { |
424 if (__augment) { |
421 typename MG::Node n=tF; |
425 typename MG::Node n=tF; |
422 Number augment_value=free.get(tF); |
426 Number augment_value=free[tF]; |
423 while (F.valid(pred.get(n))) { |
427 while (F.valid(pred[n])) { |
424 typename MG::Edge e=pred.get(n); |
428 typename MG::Edge e=pred[n]; |
425 res_graph.augment(original_edge.get(e), augment_value); |
429 res_graph.augment(original_edge[e], augment_value); |
426 n=F.tail(e); |
430 n=F.tail(e); |
427 if (residual_capacity.get(e)==augment_value) |
431 if (residual_capacity[e]==augment_value) |
428 F.erase(e); |
432 F.erase(e); |
429 else |
433 else |
430 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
434 residual_capacity.set(e, residual_capacity[e]-augment_value); |
431 } |
435 } |
432 } |
436 } |
433 |
437 |
434 } |
438 } |
435 |
439 |
438 |
442 |
439 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
443 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
440 typedef MutableGraph MG; |
444 typedef MutableGraph MG; |
441 bool _augment=false; |
445 bool _augment=false; |
442 |
446 |
443 ResGW res_graph(gw, *flow, *capacity); |
447 ResGW res_graph(*g, *flow, *capacity); |
444 |
448 |
445 //bfs for distances on the residual graph |
449 //bfs for distances on the residual graph |
446 typedef typename ResGW::NodeMap<bool> ReachedMap; |
450 typedef typename ResGW::NodeMap<bool> ReachedMap; |
447 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
451 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
448 bfs.pushAndSetReached(s); |
452 bfs.pushAndSetReached(s); |
457 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
461 for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) { |
458 res_graph_to_F.set(n, F.addNode()); |
462 res_graph_to_F.set(n, F.addNode()); |
459 } |
463 } |
460 } |
464 } |
461 |
465 |
462 typename MG::Node sF=res_graph_to_F.get(s); |
466 typename MG::Node sF=res_graph_to_F[s]; |
463 typename MG::Node tF=res_graph_to_F.get(t); |
467 typename MG::Node tF=res_graph_to_F[t]; |
464 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
468 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
465 typename MG::EdgeMap<Number> residual_capacity(F); |
469 typename MG::EdgeMap<Number> residual_capacity(F); |
466 |
470 |
467 while ( !bfs.finished() ) { |
471 while ( !bfs.finished() ) { |
468 ResGWOutEdgeIt e=bfs; |
472 ResGWOutEdgeIt e=bfs; |
469 if (res_graph.valid(e)) { |
473 if (res_graph.valid(e)) { |
470 if (bfs.isBNodeNewlyReached()) { |
474 if (bfs.isBNodeNewlyReached()) { |
471 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
475 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); |
472 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
476 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); |
473 original_edge.update(); |
477 original_edge.update(); |
474 original_edge.set(f, e); |
478 original_edge.set(f, e); |
475 residual_capacity.update(); |
479 residual_capacity.update(); |
476 residual_capacity.set(f, res_graph.resCap(e)); |
480 residual_capacity.set(f, res_graph.resCap(e)); |
477 } else { |
481 } else { |
478 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
482 if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) { |
479 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
483 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]); |
480 original_edge.update(); |
484 original_edge.update(); |
481 original_edge.set(f, e); |
485 original_edge.set(f, e); |
482 residual_capacity.update(); |
486 residual_capacity.update(); |
483 residual_capacity.set(f, res_graph.resCap(e)); |
487 residual_capacity.set(f, res_graph.resCap(e)); |
484 } |
488 } |
506 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
510 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
507 if (dfs.isBNodeNewlyReached()) { |
511 if (dfs.isBNodeNewlyReached()) { |
508 typename MG::Node v=F.aNode(dfs); |
512 typename MG::Node v=F.aNode(dfs); |
509 typename MG::Node w=F.bNode(dfs); |
513 typename MG::Node w=F.bNode(dfs); |
510 pred.set(w, dfs); |
514 pred.set(w, dfs); |
511 if (F.valid(pred.get(v))) { |
515 if (F.valid(pred[v])) { |
512 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
516 free.set(w, std::min(free[v], residual_capacity[dfs])); |
513 } else { |
517 } else { |
514 free.set(w, residual_capacity.get(dfs)); |
518 free.set(w, residual_capacity[dfs]); |
515 } |
519 } |
516 if (w==tF) { |
520 if (w==tF) { |
517 __augment=true; |
521 __augment=true; |
518 _augment=true; |
522 _augment=true; |
519 break; |
523 break; |
525 } |
529 } |
526 } |
530 } |
527 |
531 |
528 if (__augment) { |
532 if (__augment) { |
529 typename MG::Node n=tF; |
533 typename MG::Node n=tF; |
530 Number augment_value=free.get(tF); |
534 Number augment_value=free[tF]; |
531 while (F.valid(pred.get(n))) { |
535 while (F.valid(pred[n])) { |
532 typename MG::Edge e=pred.get(n); |
536 typename MG::Edge e=pred[n]; |
533 res_graph.augment(original_edge.get(e), augment_value); |
537 res_graph.augment(original_edge[e], augment_value); |
534 n=F.tail(e); |
538 n=F.tail(e); |
535 if (residual_capacity.get(e)==augment_value) |
539 if (residual_capacity[e]==augment_value) |
536 F.erase(e); |
540 F.erase(e); |
537 else |
541 else |
538 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
542 residual_capacity.set(e, residual_capacity[e]-augment_value); |
539 } |
543 } |
540 } |
544 } |
541 |
545 |
542 } |
546 } |
543 |
547 |
545 } |
549 } |
546 |
550 |
547 bool augmentOnBlockingFlow2() { |
551 bool augmentOnBlockingFlow2() { |
548 bool _augment=false; |
552 bool _augment=false; |
549 |
553 |
550 ResGW res_graph(gw, *flow, *capacity); |
554 ResGW res_graph(*g, *flow, *capacity); |
551 |
555 |
552 typedef typename ResGW::NodeMap<bool> ReachedMap; |
556 typedef typename ResGW::NodeMap<bool> ReachedMap; |
553 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
557 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
554 |
558 |
555 bfs.pushAndSetReached(s); |
559 bfs.pushAndSetReached(s); |
556 DistanceMap<ResGW> dist(res_graph); |
560 DistanceMap<ResGW> dist(res_graph); |
557 while ( !bfs.finished() ) { |
561 while ( !bfs.finished() ) { |
558 ResGWOutEdgeIt e=bfs; |
562 ResGWOutEdgeIt e=bfs; |
559 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
563 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
560 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
564 dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1); |
561 } |
565 } |
562 ++bfs; |
566 ++bfs; |
563 } //computing distances from s in the residual graph |
567 } //computing distances from s in the residual graph |
564 |
568 |
565 //Subgraph containing the edges on some shortest paths |
569 //Subgraph containing the edges on some shortest paths |
608 |
612 |
609 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); |
613 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); |
610 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); |
614 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); |
611 |
615 |
612 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); |
616 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); |
613 if (erasing_res_graph.valid(pred.get(v))) { |
617 if (erasing_res_graph.valid(pred[v])) { |
614 free.set(w, std::min(free.get(v), res_graph.resCap(dfs))); |
618 free.set(w, std::min(free[v], res_graph.resCap(dfs))); |
615 } else { |
619 } else { |
616 free.set(w, res_graph.resCap(dfs)); |
620 free.set(w, res_graph.resCap(dfs)); |
617 } |
621 } |
618 |
622 |
619 if (w==t) { |
623 if (w==t) { |
627 } |
631 } |
628 } |
632 } |
629 |
633 |
630 if (__augment) { |
634 if (__augment) { |
631 typename ErasingResGW::Node n=t; |
635 typename ErasingResGW::Node n=t; |
632 Number augment_value=free.get(n); |
636 Number augment_value=free[n]; |
633 while (erasing_res_graph.valid(pred.get(n))) { |
637 while (erasing_res_graph.valid(pred[n])) { |
634 typename ErasingResGW::OutEdgeIt e=pred.get(n); |
638 typename ErasingResGW::OutEdgeIt e=pred[n]; |
635 res_graph.augment(e, augment_value); |
639 res_graph.augment(e, augment_value); |
636 n=erasing_res_graph.tail(e); |
640 n=erasing_res_graph.tail(e); |
637 if (res_graph.resCap(e)==0) |
641 if (res_graph.resCap(e)==0) |
638 erasing_res_graph.erase(e); |
642 erasing_res_graph.erase(e); |
639 } |
643 } |
642 } //while (__augment) |
646 } //while (__augment) |
643 |
647 |
644 return _augment; |
648 return _augment; |
645 } |
649 } |
646 |
650 |
647 // bool augmentOnBlockingFlow2() { |
|
648 // bool _augment=false; |
|
649 |
|
650 // //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
651 // typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
652 // typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
653 // typedef typename EAugGraph::Edge EAugEdge; |
|
654 |
|
655 // EAugGraph res_graph(*G, *flow, *capacity); |
|
656 |
|
657 // //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
658 // BfsIterator5< |
|
659 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
660 // /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ |
|
661 // ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
662 |
|
663 // bfs.pushAndSetReached(s); |
|
664 |
|
665 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
666 // NodeMap<int>& dist=res_graph.dist; |
|
667 |
|
668 // while ( !bfs.finished() ) { |
|
669 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
670 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
671 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
672 // } |
|
673 // ++bfs; |
|
674 // } //computing distances from s in the residual graph |
|
675 |
|
676 // bool __augment=true; |
|
677 |
|
678 // while (__augment) { |
|
679 |
|
680 // __augment=false; |
|
681 // //computing blocking flow with dfs |
|
682 // typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
683 // DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap > |
|
684 // dfs(res_graph); |
|
685 // typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); |
|
686 // pred.set(s, EAugEdge(INVALID)); |
|
687 // //invalid iterators for sources |
|
688 |
|
689 // typename EAugGraph::NodeMap<Number> free(res_graph); |
|
690 |
|
691 // dfs.pushAndSetReached(s); |
|
692 // while (!dfs.finished()) { |
|
693 // ++dfs; |
|
694 // if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
695 // if (dfs.isBNodeNewlyReached()) { |
|
696 |
|
697 // typename EAugGraph::Node v=res_graph.aNode(dfs); |
|
698 // typename EAugGraph::Node w=res_graph.bNode(dfs); |
|
699 |
|
700 // pred.set(w, EAugOutEdgeIt(dfs)); |
|
701 // if (res_graph.valid(pred.get(v))) { |
|
702 // free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
|
703 // } else { |
|
704 // free.set(w, res_graph.free(dfs)); |
|
705 // } |
|
706 |
|
707 // if (w==t) { |
|
708 // __augment=true; |
|
709 // _augment=true; |
|
710 // break; |
|
711 // } |
|
712 // } else { |
|
713 // res_graph.erase(dfs); |
|
714 // } |
|
715 // } |
|
716 |
|
717 // } |
|
718 |
|
719 // if (__augment) { |
|
720 // typename EAugGraph::Node n=t; |
|
721 // Number augment_value=free.get(t); |
|
722 // while (res_graph.valid(pred.get(n))) { |
|
723 // EAugEdge e=pred.get(n); |
|
724 // res_graph.augment(e, augment_value); |
|
725 // n=res_graph.tail(e); |
|
726 // if (res_graph.free(e)==0) |
|
727 // res_graph.erase(e); |
|
728 // } |
|
729 // } |
|
730 |
|
731 // } |
|
732 |
|
733 // return _augment; |
|
734 // } |
|
735 |
|
736 void run() { |
651 void run() { |
737 //int num_of_augmentations=0; |
652 //int num_of_augmentations=0; |
738 while (augmentOnShortestPath()) { |
653 while (augmentOnShortestPath()) { |
739 //while (augmentOnBlockingFlow<MutableGraph>()) { |
654 //while (augmentOnBlockingFlow<MutableGraph>()) { |
740 //std::cout << ++num_of_augmentations << " "; |
655 //std::cout << ++num_of_augmentations << " "; |