374 |
375 |
375 dfs.pushAndSetReached(sF); |
376 dfs.pushAndSetReached(sF); |
376 while (!dfs.finished()) { |
377 while (!dfs.finished()) { |
377 ++dfs; |
378 ++dfs; |
378 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
379 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
379 //std::cout << "OutEdgeIt: " << dfs; |
380 if (dfs.isBNodeNewlyReached()) { |
380 //std::cout << " aNode: " << F.aNode(dfs); |
381 // std::cout << "OutEdgeIt: " << dfs; |
381 //std::cout << " bNode: " << F.bNode(dfs) << " "; |
382 // std::cout << " aNode: " << F.aNode(dfs); |
|
383 // std::cout << " bNode: " << F.bNode(dfs) << " "; |
382 |
384 |
383 typename MutableGraph::NodeIt v=F.aNode(dfs); |
385 typename MutableGraph::NodeIt v=F.aNode(dfs); |
384 typename MutableGraph::NodeIt w=F.bNode(dfs); |
386 typename MutableGraph::NodeIt w=F.bNode(dfs); |
385 pred.set(w, dfs); |
387 pred.set(w, dfs); |
386 if (F.valid(pred.get(v))) { |
388 if (F.valid(pred.get(v))) { |
387 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
389 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
|
390 } else { |
|
391 free.set(w, residual_capacity.get(dfs)); |
|
392 } |
|
393 if (w==tF) { |
|
394 //std::cout << "AUGMENTATION"<<std::endl; |
|
395 __augment=true; |
|
396 _augment=true; |
|
397 break; |
|
398 } |
|
399 |
388 } else { |
400 } else { |
389 free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/); |
|
390 } |
|
391 if (w==tF) { |
|
392 //std::cout << "AUGMENTATION"<<std::endl; |
|
393 __augment=true; |
|
394 _augment=true; |
|
395 break; |
|
396 } |
|
397 } else { |
|
398 //std::cout << "OutEdgeIt: " << "invalid"; |
|
399 //std::cout << " aNode: " << dfs.aNode(); |
|
400 //std::cout << " bNode: " << "invalid" << " "; |
|
401 } |
|
402 if (dfs.isBNodeNewlyReached()) { |
|
403 //std::cout << "bNodeIsNewlyReached "; |
|
404 } else { |
|
405 //std::cout << "bNodeIsNotNewlyReached "; |
|
406 if (typename MutableGraph::OutEdgeIt(dfs).valid()) { |
|
407 //std::cout << "DELETE "; |
|
408 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
401 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
409 } |
402 } |
410 } |
403 } |
411 //if (dfs.isANodeExamined()) { |
|
412 //std::cout << "aNodeIsExamined "; |
|
413 //} else { |
|
414 //std::cout << "aNodeIsNotExamined "; |
|
415 //} |
|
416 //std::cout<<std::endl; |
|
417 } |
404 } |
418 |
405 |
419 if (__augment) { |
406 if (__augment) { |
420 typename MutableGraph::NodeIt n=tF; |
407 typename MutableGraph::NodeIt n=tF; |
421 Number augment_value=free.get(tF); |
408 Number augment_value=free.get(tF); |
422 while (F.valid(pred.get(n))) { |
409 while (F.valid(pred.get(n))) { |
423 typename MutableGraph::EdgeIt e=pred.get(n); |
410 typename MutableGraph::EdgeIt e=pred.get(n); |
424 original_edge.get(e).augment(augment_value); |
411 res_graph.augment(original_edge.get(e), augment_value); |
|
412 //original_edge.get(e).augment(augment_value); |
425 n=F.tail(e); |
413 n=F.tail(e); |
426 if (residual_capacity.get(e)==augment_value) |
414 if (residual_capacity.get(e)==augment_value) |
427 F.erase(e); |
415 F.erase(e); |
428 else |
416 else |
429 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
417 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
|
418 } |
|
419 } |
|
420 |
|
421 } |
|
422 |
|
423 return _augment; |
|
424 } |
|
425 bool augmentOnBlockingFlow2() { |
|
426 bool _augment=false; |
|
427 |
|
428 //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph; |
|
429 typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph; |
|
430 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
|
431 typedef typename EAugGraph::EdgeIt EAugEdgeIt; |
|
432 |
|
433 EAugGraph res_graph(*G, *flow, *capacity); |
|
434 |
|
435 //std::cout << "meg jo1" << std::endl; |
|
436 |
|
437 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
|
438 BfsIterator4< |
|
439 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
|
440 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
|
441 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
|
442 |
|
443 //std::cout << "meg jo2" << std::endl; |
|
444 |
|
445 bfs.pushAndSetReached(s); |
|
446 //std::cout << "meg jo2.5" << std::endl; |
|
447 |
|
448 //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
449 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
|
450 NodeMap<int>& dist=res_graph.dist; |
|
451 //std::cout << "meg jo2.6" << std::endl; |
|
452 |
|
453 while ( !bfs.finished() ) { |
|
454 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
|
455 // EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
|
456 //if (res_graph.valid(e)) { |
|
457 // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl; |
|
458 //} |
|
459 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
460 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
461 } |
|
462 |
|
463 ++bfs; |
|
464 } //computing distances from s in the residual graph |
|
465 |
|
466 |
|
467 //std::cout << "meg jo3" << std::endl; |
|
468 |
|
469 // typedef typename EAugGraph::EachNodeIt EAugEachNodeIt; |
|
470 // for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
471 // std::cout << "dist: " << dist.get(n) << std::endl; |
|
472 // } |
|
473 |
|
474 bool __augment=true; |
|
475 |
|
476 while (__augment) { |
|
477 // std::cout << "new iteration"<< std::endl; |
|
478 |
|
479 __augment=false; |
|
480 //computing blocking flow with dfs |
|
481 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
|
482 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
|
483 dfs(res_graph); |
|
484 typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators |
|
485 typename EAugGraph::NodeMap<Number> free(res_graph); |
|
486 |
|
487 dfs.pushAndSetReached(s); |
|
488 while (!dfs.finished()) { |
|
489 ++dfs; |
|
490 if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
|
491 if (dfs.isBNodeNewlyReached()) { |
|
492 // std::cout << "OutEdgeIt: " << dfs; |
|
493 // std::cout << " aNode: " << res_graph.aNode(dfs); |
|
494 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); |
|
495 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; |
|
496 |
|
497 typename EAugGraph::NodeIt v=res_graph.aNode(dfs); |
|
498 typename EAugGraph::NodeIt w=res_graph.bNode(dfs); |
|
499 |
|
500 pred.set(w, EAugOutEdgeIt(dfs)); |
|
501 |
|
502 //std::cout << EAugOutEdgeIt(dfs).free() << std::endl; |
|
503 if (res_graph.valid(pred.get(v))) { |
|
504 free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs)))); |
|
505 } else { |
|
506 free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); |
|
507 } |
|
508 |
|
509 if (w==t) { |
|
510 // std::cout << "t is reached, AUGMENTATION"<<std::endl; |
|
511 __augment=true; |
|
512 _augment=true; |
|
513 break; |
|
514 } |
|
515 } else { |
|
516 // std::cout << "<<DELETE "; |
|
517 // std::cout << " aNode: " << res_graph.aNode(dfs); |
|
518 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); |
|
519 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; |
|
520 // std::cout << "DELETE>> "; |
|
521 |
|
522 res_graph.erase(dfs); |
|
523 } |
|
524 } |
|
525 |
|
526 } |
|
527 |
|
528 if (__augment) { |
|
529 typename EAugGraph::NodeIt n=t; |
|
530 Number augment_value=free.get(t); |
|
531 // std::cout << "av:" << augment_value << std::endl; |
|
532 while (res_graph.valid(pred.get(n))) { |
|
533 EAugEdgeIt e=pred.get(n); |
|
534 res_graph.augment(e, augment_value); |
|
535 //e.augment(augment_value); |
|
536 n=res_graph.tail(e); |
|
537 if (res_graph.free(e)==0) |
|
538 res_graph.erase(e); |
430 } |
539 } |
431 } |
540 } |
432 |
541 |
433 } |
542 } |
434 |
543 |