equal
deleted
inserted
replaced
556 /// \pre One of the \ref init() functions must be called before |
556 /// \pre One of the \ref init() functions must be called before |
557 /// using this function. |
557 /// using this function. |
558 void startFirstPhase() { |
558 void startFirstPhase() { |
559 _phase = true; |
559 _phase = true; |
560 |
560 |
561 Node n = _level->highestActive(); |
561 while (true) { |
562 int level = _level->highestActiveLevel(); |
|
563 while (n != INVALID) { |
|
564 int num = _node_num; |
562 int num = _node_num; |
565 |
563 |
566 while (num > 0 && n != INVALID) { |
564 Node n = INVALID; |
|
565 int level = -1; |
|
566 |
|
567 while (num > 0) { |
|
568 n = _level->highestActive(); |
|
569 if (n == INVALID) goto first_phase_done; |
|
570 level = _level->highestActiveLevel(); |
|
571 --num; |
|
572 |
567 Value excess = (*_excess)[n]; |
573 Value excess = (*_excess)[n]; |
568 int new_level = _level->maxLevel(); |
574 int new_level = _level->maxLevel(); |
569 |
575 |
570 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
576 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
571 Value rem = (*_capacity)[e] - (*_flow)[e]; |
577 Value rem = (*_capacity)[e] - (*_flow)[e]; |
627 _level->liftToTop(level); |
633 _level->liftToTop(level); |
628 } |
634 } |
629 } else { |
635 } else { |
630 _level->deactivate(n); |
636 _level->deactivate(n); |
631 } |
637 } |
632 |
638 } |
633 n = _level->highestActive(); |
639 |
634 level = _level->highestActiveLevel(); |
640 num = _node_num * 20; |
|
641 while (num > 0) { |
|
642 while (level >= 0 && _level->activeFree(level)) { |
|
643 --level; |
|
644 } |
|
645 if (level == -1) { |
|
646 n = _level->highestActive(); |
|
647 level = _level->highestActiveLevel(); |
|
648 if (n == INVALID) goto first_phase_done; |
|
649 } else { |
|
650 n = _level->activeOn(level); |
|
651 } |
635 --num; |
652 --num; |
636 } |
653 |
637 |
|
638 num = _node_num * 20; |
|
639 while (num > 0 && n != INVALID) { |
|
640 Value excess = (*_excess)[n]; |
654 Value excess = (*_excess)[n]; |
641 int new_level = _level->maxLevel(); |
655 int new_level = _level->maxLevel(); |
642 |
656 |
643 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
657 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
644 Value rem = (*_capacity)[e] - (*_flow)[e]; |
658 Value rem = (*_capacity)[e] - (*_flow)[e]; |
700 _level->liftToTop(level); |
714 _level->liftToTop(level); |
701 } |
715 } |
702 } else { |
716 } else { |
703 _level->deactivate(n); |
717 _level->deactivate(n); |
704 } |
718 } |
705 |
719 } |
706 while (level >= 0 && _level->activeFree(level)) { |
720 } |
707 --level; |
721 first_phase_done:; |
708 } |
|
709 if (level == -1) { |
|
710 n = _level->highestActive(); |
|
711 level = _level->highestActiveLevel(); |
|
712 } else { |
|
713 n = _level->activeOn(level); |
|
714 } |
|
715 --num; |
|
716 } |
|
717 } |
|
718 } |
722 } |
719 |
723 |
720 /// \brief Starts the second phase of the preflow algorithm. |
724 /// \brief Starts the second phase of the preflow algorithm. |
721 /// |
725 /// |
722 /// The preflow algorithm consists of two phases, this method runs |
726 /// The preflow algorithm consists of two phases, this method runs |