lemon/preflow.h
changeset 1208 c6aa2cc1af04
parent 1092 dceba191c00d
equal deleted inserted replaced
32:9896955d82d0 33:9b05708e093e
   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();