equal
deleted
inserted
replaced
474 /// given flow map. |
474 /// given flow map. |
475 /// |
475 /// |
476 /// Initializes the internal data structures and sets the initial |
476 /// Initializes the internal data structures and sets the initial |
477 /// flow to the given \c flowMap. The \c flowMap should contain a |
477 /// flow to the given \c flowMap. The \c flowMap should contain a |
478 /// flow or at least a preflow, i.e. at each node excluding the |
478 /// flow or at least a preflow, i.e. at each node excluding the |
479 /// source node the incoming flow should greater or equal to the |
479 /// source node the incoming flow should be greater or equal to the |
480 /// outgoing flow. |
480 /// outgoing flow. |
481 /// \return \c false if the given \c flowMap is not a preflow. |
481 /// \return \c false if the given \c flowMap is not a preflow. |
482 template <typename FlowMap> |
482 template <typename FlowMap> |
483 bool init(const FlowMap& flowMap) { |
483 bool init(const FlowMap& flowMap) { |
484 createStructures(); |
484 createStructures(); |
493 excess += (*_flow)[e]; |
493 excess += (*_flow)[e]; |
494 } |
494 } |
495 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
495 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
496 excess -= (*_flow)[e]; |
496 excess -= (*_flow)[e]; |
497 } |
497 } |
498 if (excess < 0 && n != _source) return false; |
498 if (_tolerance.negative(excess) && n != _source) return false; |
499 (*_excess)[n] = excess; |
499 (*_excess)[n] = excess; |
500 } |
500 } |
501 |
501 |
502 typename Digraph::template NodeMap<bool> reached(_graph, false); |
502 typename Digraph::template NodeMap<bool> reached(_graph, false); |
503 |
503 |
637 |
637 |
638 no_more_push_1: |
638 no_more_push_1: |
639 |
639 |
640 (*_excess)[n] = excess; |
640 (*_excess)[n] = excess; |
641 |
641 |
642 if (excess != 0) { |
642 if (_tolerance.nonZero(excess)) { |
643 if (new_level + 1 < _level->maxLevel()) { |
643 if (new_level + 1 < _level->maxLevel()) { |
644 _level->liftHighestActive(new_level + 1); |
644 _level->liftHighestActive(new_level + 1); |
645 } else { |
645 } else { |
646 _level->liftHighestActiveToTop(); |
646 _level->liftHighestActiveToTop(); |
647 } |
647 } |
718 |
718 |
719 no_more_push_2: |
719 no_more_push_2: |
720 |
720 |
721 (*_excess)[n] = excess; |
721 (*_excess)[n] = excess; |
722 |
722 |
723 if (excess != 0) { |
723 if (_tolerance.nonZero(excess)) { |
724 if (new_level + 1 < _level->maxLevel()) { |
724 if (new_level + 1 < _level->maxLevel()) { |
725 _level->liftActiveOn(level, new_level + 1); |
725 _level->liftActiveOn(level, new_level + 1); |
726 } else { |
726 } else { |
727 _level->liftActiveToTop(level); |
727 _level->liftActiveToTop(level); |
728 } |
728 } |
789 _level->initFinish(); |
789 _level->initFinish(); |
790 |
790 |
791 for (NodeIt n(_graph); n != INVALID; ++n) { |
791 for (NodeIt n(_graph); n != INVALID; ++n) { |
792 if (!reached[n]) { |
792 if (!reached[n]) { |
793 _level->dirtyTopButOne(n); |
793 _level->dirtyTopButOne(n); |
794 } else if ((*_excess)[n] > 0 && _target != n) { |
794 } else if (_tolerance.positive((*_excess)[n]) && _target != n) { |
795 _level->activate(n); |
795 _level->activate(n); |
796 } |
796 } |
797 } |
797 } |
798 |
798 |
799 Node n; |
799 Node n; |
850 |
850 |
851 no_more_push: |
851 no_more_push: |
852 |
852 |
853 (*_excess)[n] = excess; |
853 (*_excess)[n] = excess; |
854 |
854 |
855 if (excess != 0) { |
855 if (_tolerance.nonZero(excess)) { |
856 if (new_level + 1 < _level->maxLevel()) { |
856 if (new_level + 1 < _level->maxLevel()) { |
857 _level->liftHighestActive(new_level + 1); |
857 _level->liftHighestActive(new_level + 1); |
858 } else { |
858 } else { |
859 // Calculation error |
859 // Calculation error |
860 _level->liftHighestActiveToTop(); |
860 _level->liftHighestActiveToTop(); |