lemon/circulation.h
changeset 680 257e91516e09
parent 622 28f58740b6f8
child 688 1f08e846df29
child 713 4ac30454f1c1
equal deleted inserted replaced
10:35e38c53a9ec 11:e1b5e2985d89
    62     /// The type of the map that stores the signed supply values of the 
    62     /// The type of the map that stores the signed supply values of the 
    63     /// nodes. 
    63     /// nodes. 
    64     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    64     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    65     typedef SM SupplyMap;
    65     typedef SM SupplyMap;
    66 
    66 
    67     /// \brief The type of the flow values.
    67     /// \brief The type of the flow and supply values.
    68     typedef typename SupplyMap::Value Flow;
    68     typedef typename SupplyMap::Value Value;
    69 
    69 
    70     /// \brief The type of the map that stores the flow values.
    70     /// \brief The type of the map that stores the flow values.
    71     ///
    71     ///
    72     /// The type of the map that stores the flow values.
    72     /// The type of the map that stores the flow values.
    73     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    73     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    74     /// concept.
    74     /// concept.
    75     typedef typename Digraph::template ArcMap<Flow> FlowMap;
    75     typedef typename Digraph::template ArcMap<Value> FlowMap;
    76 
    76 
    77     /// \brief Instantiates a FlowMap.
    77     /// \brief Instantiates a FlowMap.
    78     ///
    78     ///
    79     /// This function instantiates a \ref FlowMap.
    79     /// This function instantiates a \ref FlowMap.
    80     /// \param digraph The digraph for which we would like to define
    80     /// \param digraph The digraph for which we would like to define
   102     }
   102     }
   103 
   103 
   104     /// \brief The tolerance used by the algorithm
   104     /// \brief The tolerance used by the algorithm
   105     ///
   105     ///
   106     /// The tolerance used by the algorithm to handle inexact computation.
   106     /// The tolerance used by the algorithm to handle inexact computation.
   107     typedef lemon::Tolerance<Flow> Tolerance;
   107     typedef lemon::Tolerance<Value> Tolerance;
   108 
   108 
   109   };
   109   };
   110 
   110 
   111   /**
   111   /**
   112      \brief Push-relabel algorithm for the network circulation problem.
   112      \brief Push-relabel algorithm for the network circulation problem.
   185 
   185 
   186     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   186     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   187     typedef TR Traits;
   187     typedef TR Traits;
   188     ///The type of the digraph the algorithm runs on.
   188     ///The type of the digraph the algorithm runs on.
   189     typedef typename Traits::Digraph Digraph;
   189     typedef typename Traits::Digraph Digraph;
   190     ///The type of the flow values.
   190     ///The type of the flow and supply values.
   191     typedef typename Traits::Flow Flow;
   191     typedef typename Traits::Value Value;
   192 
   192 
   193     ///The type of the lower bound map.
   193     ///The type of the lower bound map.
   194     typedef typename Traits::LowerMap LowerMap;
   194     typedef typename Traits::LowerMap LowerMap;
   195     ///The type of the upper bound (capacity) map.
   195     ///The type of the upper bound (capacity) map.
   196     typedef typename Traits::UpperMap UpperMap;
   196     typedef typename Traits::UpperMap UpperMap;
   219     bool _local_flow;
   219     bool _local_flow;
   220 
   220 
   221     Elevator* _level;
   221     Elevator* _level;
   222     bool _local_level;
   222     bool _local_level;
   223 
   223 
   224     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
   224     typedef typename Digraph::template NodeMap<Value> ExcessMap;
   225     ExcessMap* _excess;
   225     ExcessMap* _excess;
   226 
   226 
   227     Tolerance _tol;
   227     Tolerance _tol;
   228     int _el;
   228     int _el;
   229 
   229 
   528         } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
   528         } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
   529           _flow->set(e, (*_lo)[e]);
   529           _flow->set(e, (*_lo)[e]);
   530           (*_excess)[_g.target(e)] += (*_lo)[e];
   530           (*_excess)[_g.target(e)] += (*_lo)[e];
   531           (*_excess)[_g.source(e)] -= (*_lo)[e];
   531           (*_excess)[_g.source(e)] -= (*_lo)[e];
   532         } else {
   532         } else {
   533           Flow fc = -(*_excess)[_g.target(e)];
   533           Value fc = -(*_excess)[_g.target(e)];
   534           _flow->set(e, fc);
   534           _flow->set(e, fc);
   535           (*_excess)[_g.target(e)] = 0;
   535           (*_excess)[_g.target(e)] = 0;
   536           (*_excess)[_g.source(e)] -= fc;
   536           (*_excess)[_g.source(e)] -= fc;
   537         }
   537         }
   538       }
   538       }
   561       Node bact=INVALID;
   561       Node bact=INVALID;
   562       Node last_activated=INVALID;
   562       Node last_activated=INVALID;
   563       while((act=_level->highestActive())!=INVALID) {
   563       while((act=_level->highestActive())!=INVALID) {
   564         int actlevel=(*_level)[act];
   564         int actlevel=(*_level)[act];
   565         int mlevel=_node_num;
   565         int mlevel=_node_num;
   566         Flow exc=(*_excess)[act];
   566         Value exc=(*_excess)[act];
   567 
   567 
   568         for(OutArcIt e(_g,act);e!=INVALID; ++e) {
   568         for(OutArcIt e(_g,act);e!=INVALID; ++e) {
   569           Node v = _g.target(e);
   569           Node v = _g.target(e);
   570           Flow fc=(*_up)[e]-(*_flow)[e];
   570           Value fc=(*_up)[e]-(*_flow)[e];
   571           if(!_tol.positive(fc)) continue;
   571           if(!_tol.positive(fc)) continue;
   572           if((*_level)[v]<actlevel) {
   572           if((*_level)[v]<actlevel) {
   573             if(!_tol.less(fc, exc)) {
   573             if(!_tol.less(fc, exc)) {
   574               _flow->set(e, (*_flow)[e] + exc);
   574               _flow->set(e, (*_flow)[e] + exc);
   575               (*_excess)[v] += exc;
   575               (*_excess)[v] += exc;
   589           }
   589           }
   590           else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
   590           else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
   591         }
   591         }
   592         for(InArcIt e(_g,act);e!=INVALID; ++e) {
   592         for(InArcIt e(_g,act);e!=INVALID; ++e) {
   593           Node v = _g.source(e);
   593           Node v = _g.source(e);
   594           Flow fc=(*_flow)[e]-(*_lo)[e];
   594           Value fc=(*_flow)[e]-(*_lo)[e];
   595           if(!_tol.positive(fc)) continue;
   595           if(!_tol.positive(fc)) continue;
   596           if((*_level)[v]<actlevel) {
   596           if((*_level)[v]<actlevel) {
   597             if(!_tol.less(fc, exc)) {
   597             if(!_tol.less(fc, exc)) {
   598               _flow->set(e, (*_flow)[e] - exc);
   598               _flow->set(e, (*_flow)[e] - exc);
   599               (*_excess)[v] += exc;
   599               (*_excess)[v] += exc;
   659     /// Either \ref run() or \ref start() should be called before
   659     /// Either \ref run() or \ref start() should be called before
   660     /// using them.
   660     /// using them.
   661 
   661 
   662     ///@{
   662     ///@{
   663 
   663 
   664     /// \brief Returns the flow on the given arc.
   664     /// \brief Returns the flow value on the given arc.
   665     ///
   665     ///
   666     /// Returns the flow on the given arc.
   666     /// Returns the flow value on the given arc.
   667     ///
   667     ///
   668     /// \pre Either \ref run() or \ref init() must be called before
   668     /// \pre Either \ref run() or \ref init() must be called before
   669     /// using this function.
   669     /// using this function.
   670     Flow flow(const Arc& arc) const {
   670     Value flow(const Arc& arc) const {
   671       return (*_flow)[arc];
   671       return (*_flow)[arc];
   672     }
   672     }
   673 
   673 
   674     /// \brief Returns a const reference to the flow map.
   674     /// \brief Returns a const reference to the flow map.
   675     ///
   675     ///
   748     bool checkFlow() const {
   748     bool checkFlow() const {
   749       for(ArcIt e(_g);e!=INVALID;++e)
   749       for(ArcIt e(_g);e!=INVALID;++e)
   750         if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
   750         if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
   751       for(NodeIt n(_g);n!=INVALID;++n)
   751       for(NodeIt n(_g);n!=INVALID;++n)
   752         {
   752         {
   753           Flow dif=-(*_supply)[n];
   753           Value dif=-(*_supply)[n];
   754           for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
   754           for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
   755           for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
   755           for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
   756           if(_tol.negative(dif)) return false;
   756           if(_tol.negative(dif)) return false;
   757         }
   757         }
   758       return true;
   758       return true;
   763     ///Check whether or not the last execution provides a barrier.
   763     ///Check whether or not the last execution provides a barrier.
   764     ///\sa barrier()
   764     ///\sa barrier()
   765     ///\sa barrierMap()
   765     ///\sa barrierMap()
   766     bool checkBarrier() const
   766     bool checkBarrier() const
   767     {
   767     {
   768       Flow delta=0;
   768       Value delta=0;
   769       Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
   769       Value inf_cap = std::numeric_limits<Value>::has_infinity ?
   770         std::numeric_limits<Flow>::infinity() :
   770         std::numeric_limits<Value>::infinity() :
   771         std::numeric_limits<Flow>::max();
   771         std::numeric_limits<Value>::max();
   772       for(NodeIt n(_g);n!=INVALID;++n)
   772       for(NodeIt n(_g);n!=INVALID;++n)
   773         if(barrier(n))
   773         if(barrier(n))
   774           delta-=(*_supply)[n];
   774           delta-=(*_supply)[n];
   775       for(ArcIt e(_g);e!=INVALID;++e)
   775       for(ArcIt e(_g);e!=INVALID;++e)
   776         {
   776         {