equal
deleted
inserted
replaced
574 /// \pre One of the \ref init() functions must be called before |
574 /// \pre One of the \ref init() functions must be called before |
575 /// using this function. |
575 /// using this function. |
576 void startFirstPhase() { |
576 void startFirstPhase() { |
577 _phase = true; |
577 _phase = true; |
578 |
578 |
579 Node n = _level->highestActive(); |
579 while (true) { |
580 int level = _level->highestActiveLevel(); |
|
581 while (n != INVALID) { |
|
582 int num = _node_num; |
580 int num = _node_num; |
583 |
581 |
584 while (num > 0 && n != INVALID) { |
582 Node n = INVALID; |
|
583 int level = -1; |
|
584 |
|
585 while (num > 0) { |
|
586 n = _level->highestActive(); |
|
587 if (n == INVALID) goto first_phase_done; |
|
588 level = _level->highestActiveLevel(); |
|
589 --num; |
|
590 |
585 Value excess = (*_excess)[n]; |
591 Value excess = (*_excess)[n]; |
586 int new_level = _level->maxLevel(); |
592 int new_level = _level->maxLevel(); |
587 |
593 |
588 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
594 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
589 Value rem = (*_capacity)[e] - (*_flow)[e]; |
595 Value rem = (*_capacity)[e] - (*_flow)[e]; |
645 _level->liftToTop(level); |
651 _level->liftToTop(level); |
646 } |
652 } |
647 } else { |
653 } else { |
648 _level->deactivate(n); |
654 _level->deactivate(n); |
649 } |
655 } |
650 |
656 } |
651 n = _level->highestActive(); |
657 |
652 level = _level->highestActiveLevel(); |
658 num = _node_num * 20; |
|
659 while (num > 0) { |
|
660 while (level >= 0 && _level->activeFree(level)) { |
|
661 --level; |
|
662 } |
|
663 if (level == -1) { |
|
664 n = _level->highestActive(); |
|
665 level = _level->highestActiveLevel(); |
|
666 if (n == INVALID) goto first_phase_done; |
|
667 } else { |
|
668 n = _level->activeOn(level); |
|
669 } |
653 --num; |
670 --num; |
654 } |
671 |
655 |
|
656 num = _node_num * 20; |
|
657 while (num > 0 && n != INVALID) { |
|
658 Value excess = (*_excess)[n]; |
672 Value excess = (*_excess)[n]; |
659 int new_level = _level->maxLevel(); |
673 int new_level = _level->maxLevel(); |
660 |
674 |
661 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
675 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
662 Value rem = (*_capacity)[e] - (*_flow)[e]; |
676 Value rem = (*_capacity)[e] - (*_flow)[e]; |
718 _level->liftToTop(level); |
732 _level->liftToTop(level); |
719 } |
733 } |
720 } else { |
734 } else { |
721 _level->deactivate(n); |
735 _level->deactivate(n); |
722 } |
736 } |
723 |
737 } |
724 while (level >= 0 && _level->activeFree(level)) { |
738 } |
725 --level; |
739 first_phase_done:; |
726 } |
|
727 if (level == -1) { |
|
728 n = _level->highestActive(); |
|
729 level = _level->highestActiveLevel(); |
|
730 } else { |
|
731 n = _level->activeOn(level); |
|
732 } |
|
733 --num; |
|
734 } |
|
735 } |
|
736 } |
740 } |
737 |
741 |
738 /// \brief Starts the second phase of the preflow algorithm. |
742 /// \brief Starts the second phase of the preflow algorithm. |
739 /// |
743 /// |
740 /// The preflow algorithm consists of two phases, this method runs |
744 /// The preflow algorithm consists of two phases, this method runs |