415 |
415 |
416 _level->initStart(); |
416 _level->initStart(); |
417 _level->initAddItem(_target); |
417 _level->initAddItem(_target); |
418 |
418 |
419 std::vector<Node> queue; |
419 std::vector<Node> queue; |
420 reached.set(_source, true); |
420 reached[_source] = true; |
421 |
421 |
422 queue.push_back(_target); |
422 queue.push_back(_target); |
423 reached.set(_target, true); |
423 reached[_target] = true; |
424 while (!queue.empty()) { |
424 while (!queue.empty()) { |
425 _level->initNewLevel(); |
425 _level->initNewLevel(); |
426 std::vector<Node> nqueue; |
426 std::vector<Node> nqueue; |
427 for (int i = 0; i < int(queue.size()); ++i) { |
427 for (int i = 0; i < int(queue.size()); ++i) { |
428 Node n = queue[i]; |
428 Node n = queue[i]; |
429 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
429 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
430 Node u = _graph.source(e); |
430 Node u = _graph.source(e); |
431 if (!reached[u] && _tolerance.positive((*_capacity)[e])) { |
431 if (!reached[u] && _tolerance.positive((*_capacity)[e])) { |
432 reached.set(u, true); |
432 reached[u] = true; |
433 _level->initAddItem(u); |
433 _level->initAddItem(u); |
434 nqueue.push_back(u); |
434 nqueue.push_back(u); |
435 } |
435 } |
436 } |
436 } |
437 } |
437 } |
442 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
442 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { |
443 if (_tolerance.positive((*_capacity)[e])) { |
443 if (_tolerance.positive((*_capacity)[e])) { |
444 Node u = _graph.target(e); |
444 Node u = _graph.target(e); |
445 if ((*_level)[u] == _level->maxLevel()) continue; |
445 if ((*_level)[u] == _level->maxLevel()) continue; |
446 _flow->set(e, (*_capacity)[e]); |
446 _flow->set(e, (*_capacity)[e]); |
447 _excess->set(u, (*_excess)[u] + (*_capacity)[e]); |
447 (*_excess)[u] += (*_capacity)[e]; |
448 if (u != _target && !_level->active(u)) { |
448 if (u != _target && !_level->active(u)) { |
449 _level->activate(u); |
449 _level->activate(u); |
450 } |
450 } |
451 } |
451 } |
452 } |
452 } |
476 } |
476 } |
477 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
477 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
478 excess -= (*_flow)[e]; |
478 excess -= (*_flow)[e]; |
479 } |
479 } |
480 if (excess < 0 && n != _source) return false; |
480 if (excess < 0 && n != _source) return false; |
481 _excess->set(n, excess); |
481 (*_excess)[n] = excess; |
482 } |
482 } |
483 |
483 |
484 typename Digraph::template NodeMap<bool> reached(_graph, false); |
484 typename Digraph::template NodeMap<bool> reached(_graph, false); |
485 |
485 |
486 _level->initStart(); |
486 _level->initStart(); |
487 _level->initAddItem(_target); |
487 _level->initAddItem(_target); |
488 |
488 |
489 std::vector<Node> queue; |
489 std::vector<Node> queue; |
490 reached.set(_source, true); |
490 reached[_source] = true; |
491 |
491 |
492 queue.push_back(_target); |
492 queue.push_back(_target); |
493 reached.set(_target, true); |
493 reached[_target] = true; |
494 while (!queue.empty()) { |
494 while (!queue.empty()) { |
495 _level->initNewLevel(); |
495 _level->initNewLevel(); |
496 std::vector<Node> nqueue; |
496 std::vector<Node> nqueue; |
497 for (int i = 0; i < int(queue.size()); ++i) { |
497 for (int i = 0; i < int(queue.size()); ++i) { |
498 Node n = queue[i]; |
498 Node n = queue[i]; |
499 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
499 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
500 Node u = _graph.source(e); |
500 Node u = _graph.source(e); |
501 if (!reached[u] && |
501 if (!reached[u] && |
502 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { |
502 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { |
503 reached.set(u, true); |
503 reached[u] = true; |
504 _level->initAddItem(u); |
504 _level->initAddItem(u); |
505 nqueue.push_back(u); |
505 nqueue.push_back(u); |
506 } |
506 } |
507 } |
507 } |
508 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
508 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
509 Node v = _graph.target(e); |
509 Node v = _graph.target(e); |
510 if (!reached[v] && _tolerance.positive((*_flow)[e])) { |
510 if (!reached[v] && _tolerance.positive((*_flow)[e])) { |
511 reached.set(v, true); |
511 reached[v] = true; |
512 _level->initAddItem(v); |
512 _level->initAddItem(v); |
513 nqueue.push_back(v); |
513 nqueue.push_back(v); |
514 } |
514 } |
515 } |
515 } |
516 } |
516 } |
522 Value rem = (*_capacity)[e] - (*_flow)[e]; |
522 Value rem = (*_capacity)[e] - (*_flow)[e]; |
523 if (_tolerance.positive(rem)) { |
523 if (_tolerance.positive(rem)) { |
524 Node u = _graph.target(e); |
524 Node u = _graph.target(e); |
525 if ((*_level)[u] == _level->maxLevel()) continue; |
525 if ((*_level)[u] == _level->maxLevel()) continue; |
526 _flow->set(e, (*_capacity)[e]); |
526 _flow->set(e, (*_capacity)[e]); |
527 _excess->set(u, (*_excess)[u] + rem); |
527 (*_excess)[u] += rem; |
528 if (u != _target && !_level->active(u)) { |
528 if (u != _target && !_level->active(u)) { |
529 _level->activate(u); |
529 _level->activate(u); |
530 } |
530 } |
531 } |
531 } |
532 } |
532 } |
534 Value rem = (*_flow)[e]; |
534 Value rem = (*_flow)[e]; |
535 if (_tolerance.positive(rem)) { |
535 if (_tolerance.positive(rem)) { |
536 Node v = _graph.source(e); |
536 Node v = _graph.source(e); |
537 if ((*_level)[v] == _level->maxLevel()) continue; |
537 if ((*_level)[v] == _level->maxLevel()) continue; |
538 _flow->set(e, 0); |
538 _flow->set(e, 0); |
539 _excess->set(v, (*_excess)[v] + rem); |
539 (*_excess)[v] += rem; |
540 if (v != _target && !_level->active(v)) { |
540 if (v != _target && !_level->active(v)) { |
541 _level->activate(v); |
541 _level->activate(v); |
542 } |
542 } |
543 } |
543 } |
544 } |
544 } |
575 if (!_level->active(v) && v != _target) { |
575 if (!_level->active(v) && v != _target) { |
576 _level->activate(v); |
576 _level->activate(v); |
577 } |
577 } |
578 if (!_tolerance.less(rem, excess)) { |
578 if (!_tolerance.less(rem, excess)) { |
579 _flow->set(e, (*_flow)[e] + excess); |
579 _flow->set(e, (*_flow)[e] + excess); |
580 _excess->set(v, (*_excess)[v] + excess); |
580 (*_excess)[v] += excess; |
581 excess = 0; |
581 excess = 0; |
582 goto no_more_push_1; |
582 goto no_more_push_1; |
583 } else { |
583 } else { |
584 excess -= rem; |
584 excess -= rem; |
585 _excess->set(v, (*_excess)[v] + rem); |
585 (*_excess)[v] += rem; |
586 _flow->set(e, (*_capacity)[e]); |
586 _flow->set(e, (*_capacity)[e]); |
587 } |
587 } |
588 } else if (new_level > (*_level)[v]) { |
588 } else if (new_level > (*_level)[v]) { |
589 new_level = (*_level)[v]; |
589 new_level = (*_level)[v]; |
590 } |
590 } |
598 if (!_level->active(v) && v != _target) { |
598 if (!_level->active(v) && v != _target) { |
599 _level->activate(v); |
599 _level->activate(v); |
600 } |
600 } |
601 if (!_tolerance.less(rem, excess)) { |
601 if (!_tolerance.less(rem, excess)) { |
602 _flow->set(e, (*_flow)[e] - excess); |
602 _flow->set(e, (*_flow)[e] - excess); |
603 _excess->set(v, (*_excess)[v] + excess); |
603 (*_excess)[v] += excess; |
604 excess = 0; |
604 excess = 0; |
605 goto no_more_push_1; |
605 goto no_more_push_1; |
606 } else { |
606 } else { |
607 excess -= rem; |
607 excess -= rem; |
608 _excess->set(v, (*_excess)[v] + rem); |
608 (*_excess)[v] += rem; |
609 _flow->set(e, 0); |
609 _flow->set(e, 0); |
610 } |
610 } |
611 } else if (new_level > (*_level)[v]) { |
611 } else if (new_level > (*_level)[v]) { |
612 new_level = (*_level)[v]; |
612 new_level = (*_level)[v]; |
613 } |
613 } |
614 } |
614 } |
615 |
615 |
616 no_more_push_1: |
616 no_more_push_1: |
617 |
617 |
618 _excess->set(n, excess); |
618 (*_excess)[n] = excess; |
619 |
619 |
620 if (excess != 0) { |
620 if (excess != 0) { |
621 if (new_level + 1 < _level->maxLevel()) { |
621 if (new_level + 1 < _level->maxLevel()) { |
622 _level->liftHighestActive(new_level + 1); |
622 _level->liftHighestActive(new_level + 1); |
623 } else { |
623 } else { |
648 if (!_level->active(v) && v != _target) { |
648 if (!_level->active(v) && v != _target) { |
649 _level->activate(v); |
649 _level->activate(v); |
650 } |
650 } |
651 if (!_tolerance.less(rem, excess)) { |
651 if (!_tolerance.less(rem, excess)) { |
652 _flow->set(e, (*_flow)[e] + excess); |
652 _flow->set(e, (*_flow)[e] + excess); |
653 _excess->set(v, (*_excess)[v] + excess); |
653 (*_excess)[v] += excess; |
654 excess = 0; |
654 excess = 0; |
655 goto no_more_push_2; |
655 goto no_more_push_2; |
656 } else { |
656 } else { |
657 excess -= rem; |
657 excess -= rem; |
658 _excess->set(v, (*_excess)[v] + rem); |
658 (*_excess)[v] += rem; |
659 _flow->set(e, (*_capacity)[e]); |
659 _flow->set(e, (*_capacity)[e]); |
660 } |
660 } |
661 } else if (new_level > (*_level)[v]) { |
661 } else if (new_level > (*_level)[v]) { |
662 new_level = (*_level)[v]; |
662 new_level = (*_level)[v]; |
663 } |
663 } |
671 if (!_level->active(v) && v != _target) { |
671 if (!_level->active(v) && v != _target) { |
672 _level->activate(v); |
672 _level->activate(v); |
673 } |
673 } |
674 if (!_tolerance.less(rem, excess)) { |
674 if (!_tolerance.less(rem, excess)) { |
675 _flow->set(e, (*_flow)[e] - excess); |
675 _flow->set(e, (*_flow)[e] - excess); |
676 _excess->set(v, (*_excess)[v] + excess); |
676 (*_excess)[v] += excess; |
677 excess = 0; |
677 excess = 0; |
678 goto no_more_push_2; |
678 goto no_more_push_2; |
679 } else { |
679 } else { |
680 excess -= rem; |
680 excess -= rem; |
681 _excess->set(v, (*_excess)[v] + rem); |
681 (*_excess)[v] += rem; |
682 _flow->set(e, 0); |
682 _flow->set(e, 0); |
683 } |
683 } |
684 } else if (new_level > (*_level)[v]) { |
684 } else if (new_level > (*_level)[v]) { |
685 new_level = (*_level)[v]; |
685 new_level = (*_level)[v]; |
686 } |
686 } |
687 } |
687 } |
688 |
688 |
689 no_more_push_2: |
689 no_more_push_2: |
690 |
690 |
691 _excess->set(n, excess); |
691 (*_excess)[n] = excess; |
692 |
692 |
693 if (excess != 0) { |
693 if (excess != 0) { |
694 if (new_level + 1 < _level->maxLevel()) { |
694 if (new_level + 1 < _level->maxLevel()) { |
695 _level->liftActiveOn(level, new_level + 1); |
695 _level->liftActiveOn(level, new_level + 1); |
696 } else { |
696 } else { |
729 void startSecondPhase() { |
729 void startSecondPhase() { |
730 _phase = false; |
730 _phase = false; |
731 |
731 |
732 typename Digraph::template NodeMap<bool> reached(_graph); |
732 typename Digraph::template NodeMap<bool> reached(_graph); |
733 for (NodeIt n(_graph); n != INVALID; ++n) { |
733 for (NodeIt n(_graph); n != INVALID; ++n) { |
734 reached.set(n, (*_level)[n] < _level->maxLevel()); |
734 reached[n] = (*_level)[n] < _level->maxLevel(); |
735 } |
735 } |
736 |
736 |
737 _level->initStart(); |
737 _level->initStart(); |
738 _level->initAddItem(_source); |
738 _level->initAddItem(_source); |
739 |
739 |
740 std::vector<Node> queue; |
740 std::vector<Node> queue; |
741 queue.push_back(_source); |
741 queue.push_back(_source); |
742 reached.set(_source, true); |
742 reached[_source] = true; |
743 |
743 |
744 while (!queue.empty()) { |
744 while (!queue.empty()) { |
745 _level->initNewLevel(); |
745 _level->initNewLevel(); |
746 std::vector<Node> nqueue; |
746 std::vector<Node> nqueue; |
747 for (int i = 0; i < int(queue.size()); ++i) { |
747 for (int i = 0; i < int(queue.size()); ++i) { |
748 Node n = queue[i]; |
748 Node n = queue[i]; |
749 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
749 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
750 Node v = _graph.target(e); |
750 Node v = _graph.target(e); |
751 if (!reached[v] && _tolerance.positive((*_flow)[e])) { |
751 if (!reached[v] && _tolerance.positive((*_flow)[e])) { |
752 reached.set(v, true); |
752 reached[v] = true; |
753 _level->initAddItem(v); |
753 _level->initAddItem(v); |
754 nqueue.push_back(v); |
754 nqueue.push_back(v); |
755 } |
755 } |
756 } |
756 } |
757 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
757 for (InArcIt e(_graph, n); e != INVALID; ++e) { |
758 Node u = _graph.source(e); |
758 Node u = _graph.source(e); |
759 if (!reached[u] && |
759 if (!reached[u] && |
760 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { |
760 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { |
761 reached.set(u, true); |
761 reached[u] = true; |
762 _level->initAddItem(u); |
762 _level->initAddItem(u); |
763 nqueue.push_back(u); |
763 nqueue.push_back(u); |
764 } |
764 } |
765 } |
765 } |
766 } |
766 } |
790 if (!_level->active(v) && v != _source) { |
790 if (!_level->active(v) && v != _source) { |
791 _level->activate(v); |
791 _level->activate(v); |
792 } |
792 } |
793 if (!_tolerance.less(rem, excess)) { |
793 if (!_tolerance.less(rem, excess)) { |
794 _flow->set(e, (*_flow)[e] + excess); |
794 _flow->set(e, (*_flow)[e] + excess); |
795 _excess->set(v, (*_excess)[v] + excess); |
795 (*_excess)[v] += excess; |
796 excess = 0; |
796 excess = 0; |
797 goto no_more_push; |
797 goto no_more_push; |
798 } else { |
798 } else { |
799 excess -= rem; |
799 excess -= rem; |
800 _excess->set(v, (*_excess)[v] + rem); |
800 (*_excess)[v] += rem; |
801 _flow->set(e, (*_capacity)[e]); |
801 _flow->set(e, (*_capacity)[e]); |
802 } |
802 } |
803 } else if (new_level > (*_level)[v]) { |
803 } else if (new_level > (*_level)[v]) { |
804 new_level = (*_level)[v]; |
804 new_level = (*_level)[v]; |
805 } |
805 } |
813 if (!_level->active(v) && v != _source) { |
813 if (!_level->active(v) && v != _source) { |
814 _level->activate(v); |
814 _level->activate(v); |
815 } |
815 } |
816 if (!_tolerance.less(rem, excess)) { |
816 if (!_tolerance.less(rem, excess)) { |
817 _flow->set(e, (*_flow)[e] - excess); |
817 _flow->set(e, (*_flow)[e] - excess); |
818 _excess->set(v, (*_excess)[v] + excess); |
818 (*_excess)[v] += excess; |
819 excess = 0; |
819 excess = 0; |
820 goto no_more_push; |
820 goto no_more_push; |
821 } else { |
821 } else { |
822 excess -= rem; |
822 excess -= rem; |
823 _excess->set(v, (*_excess)[v] + rem); |
823 (*_excess)[v] += rem; |
824 _flow->set(e, 0); |
824 _flow->set(e, 0); |
825 } |
825 } |
826 } else if (new_level > (*_level)[v]) { |
826 } else if (new_level > (*_level)[v]) { |
827 new_level = (*_level)[v]; |
827 new_level = (*_level)[v]; |
828 } |
828 } |
829 } |
829 } |
830 |
830 |
831 no_more_push: |
831 no_more_push: |
832 |
832 |
833 _excess->set(n, excess); |
833 (*_excess)[n] = excess; |
834 |
834 |
835 if (excess != 0) { |
835 if (excess != 0) { |
836 if (new_level + 1 < _level->maxLevel()) { |
836 if (new_level + 1 < _level->maxLevel()) { |
837 _level->liftHighestActive(new_level + 1); |
837 _level->liftHighestActive(new_level + 1); |
838 } else { |
838 } else { |