lemon/circulation.h
changeset 628 586b65073025
parent 611 85cb3aa71cce
child 641 756a5ec551c8
equal deleted inserted replaced
9:6b2b32df34e3 10:35e38c53a9ec
    19 #ifndef LEMON_CIRCULATION_H
    19 #ifndef LEMON_CIRCULATION_H
    20 #define LEMON_CIRCULATION_H
    20 #define LEMON_CIRCULATION_H
    21 
    21 
    22 #include <lemon/tolerance.h>
    22 #include <lemon/tolerance.h>
    23 #include <lemon/elevator.h>
    23 #include <lemon/elevator.h>
       
    24 #include <limits>
    24 
    25 
    25 ///\ingroup max_flow
    26 ///\ingroup max_flow
    26 ///\file
    27 ///\file
    27 ///\brief Push-relabel algorithm for finding a feasible circulation.
    28 ///\brief Push-relabel algorithm for finding a feasible circulation.
    28 ///
    29 ///
   117      are given for the flow values on the arcs and lower bounds are
   118      are given for the flow values on the arcs and lower bounds are
   118      given for the difference between the outgoing and incoming flow
   119      given for the difference between the outgoing and incoming flow
   119      at the nodes.
   120      at the nodes.
   120 
   121 
   121      The exact formulation of this problem is the following.
   122      The exact formulation of this problem is the following.
   122      Let \f$G=(V,A)\f$ be a digraph,
   123      Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
   123      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
   124      \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
   124      upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
   125      upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
   125      holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
   126      holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
   126      denotes the signed supply values of the nodes.
   127      denotes the signed supply values of the nodes.
   127      If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   128      If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   128      supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   129      supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   129      \f$-sup(u)\f$ demand.
   130      \f$-sup(u)\f$ demand.
   130      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
   131      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
   131      solution of the following problem.
   132      solution of the following problem.
   132 
   133 
   133      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
   134      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
   134      \geq sup(u) \quad \forall u\in V, \f]
   135      \geq sup(u) \quad \forall u\in V, \f]
   135      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
   136      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
   148      (i.e. the total demand is less than the total supply and all the demands
   149      (i.e. the total demand is less than the total supply and all the demands
   149      have to be satisfied while there could be supplies that are not used),
   150      have to be satisfied while there could be supplies that are not used),
   150      then you could easily transform the problem to the above form by reversing
   151      then you could easily transform the problem to the above form by reversing
   151      the direction of the arcs and taking the negative of the supply values
   152      the direction of the arcs and taking the negative of the supply values
   152      (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
   153      (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
       
   154 
       
   155      This algorithm either calculates a feasible circulation, or provides
       
   156      a \ref barrier() "barrier", which prooves that a feasible soultion
       
   157      cannot exist.
   153 
   158 
   154      Note that this algorithm also provides a feasible solution for the
   159      Note that this algorithm also provides a feasible solution for the
   155      \ref min_cost_flow "minimum cost flow problem".
   160      \ref min_cost_flow "minimum cost flow problem".
   156 
   161 
   157      \tparam GR The type of the digraph the algorithm runs on.
   162      \tparam GR The type of the digraph the algorithm runs on.
   335     }
   340     }
   336 
   341 
   337 
   342 
   338   private:
   343   private:
   339 
   344 
       
   345     bool checkBoundMaps() {
       
   346       for (ArcIt e(_g);e!=INVALID;++e) {
       
   347         if (_tol.less((*_up)[e], (*_lo)[e])) return false;
       
   348       }
       
   349       return true;
       
   350     }
       
   351 
   340     void createStructures() {
   352     void createStructures() {
   341       _node_num = _el = countNodes(_g);
   353       _node_num = _el = countNodes(_g);
   342 
   354 
   343       if (!_flow) {
   355       if (!_flow) {
   344         _flow = Traits::createFlowMap(_g);
   356         _flow = Traits::createFlowMap(_g);
   378 
   390 
   379     /// Sets the upper bound (capacity) map.
   391     /// Sets the upper bound (capacity) map.
   380 
   392 
   381     /// Sets the upper bound (capacity) map.
   393     /// Sets the upper bound (capacity) map.
   382     /// \return <tt>(*this)</tt>
   394     /// \return <tt>(*this)</tt>
   383     Circulation& upperMap(const LowerMap& map) {
   395     Circulation& upperMap(const UpperMap& map) {
   384       _up = &map;
   396       _up = &map;
   385       return *this;
   397       return *this;
   386     }
   398     }
   387 
   399 
   388     /// Sets the supply map.
   400     /// Sets the supply map.
   465 
   477 
   466     /// Initializes the internal data structures and sets all flow values
   478     /// Initializes the internal data structures and sets all flow values
   467     /// to the lower bound.
   479     /// to the lower bound.
   468     void init()
   480     void init()
   469     {
   481     {
       
   482       LEMON_DEBUG(checkBoundMaps(),
       
   483         "Upper bounds must be greater or equal to the lower bounds");
       
   484 
   470       createStructures();
   485       createStructures();
   471 
   486 
   472       for(NodeIt n(_g);n!=INVALID;++n) {
   487       for(NodeIt n(_g);n!=INVALID;++n) {
   473         (*_excess)[n] = (*_supply)[n];
   488         (*_excess)[n] = (*_supply)[n];
   474       }
   489       }
   494 
   509 
   495     /// Initializes the internal data structures using a greedy approach
   510     /// Initializes the internal data structures using a greedy approach
   496     /// to construct the initial solution.
   511     /// to construct the initial solution.
   497     void greedyInit()
   512     void greedyInit()
   498     {
   513     {
       
   514       LEMON_DEBUG(checkBoundMaps(),
       
   515         "Upper bounds must be greater or equal to the lower bounds");
       
   516 
   499       createStructures();
   517       createStructures();
   500 
   518 
   501       for(NodeIt n(_g);n!=INVALID;++n) {
   519       for(NodeIt n(_g);n!=INVALID;++n) {
   502         (*_excess)[n] = (*_supply)[n];
   520         (*_excess)[n] = (*_supply)[n];
   503       }
   521       }
   504 
   522 
   505       for (ArcIt e(_g);e!=INVALID;++e) {
   523       for (ArcIt e(_g);e!=INVALID;++e) {
   506         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
   524         if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
   507           _flow->set(e, (*_up)[e]);
   525           _flow->set(e, (*_up)[e]);
   508           (*_excess)[_g.target(e)] += (*_up)[e];
   526           (*_excess)[_g.target(e)] += (*_up)[e];
   509           (*_excess)[_g.source(e)] -= (*_up)[e];
   527           (*_excess)[_g.source(e)] -= (*_up)[e];
   510         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
   528         } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
   511           _flow->set(e, (*_lo)[e]);
   529           _flow->set(e, (*_lo)[e]);
   512           (*_excess)[_g.target(e)] += (*_lo)[e];
   530           (*_excess)[_g.target(e)] += (*_lo)[e];
   513           (*_excess)[_g.source(e)] -= (*_lo)[e];
   531           (*_excess)[_g.source(e)] -= (*_lo)[e];
   514         } else {
   532         } else {
   515           Flow fc = -(*_excess)[_g.target(e)];
   533           Flow fc = -(*_excess)[_g.target(e)];
   746     ///\sa barrier()
   764     ///\sa barrier()
   747     ///\sa barrierMap()
   765     ///\sa barrierMap()
   748     bool checkBarrier() const
   766     bool checkBarrier() const
   749     {
   767     {
   750       Flow delta=0;
   768       Flow delta=0;
       
   769       Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
       
   770         std::numeric_limits<Flow>::infinity() :
       
   771         std::numeric_limits<Flow>::max();
   751       for(NodeIt n(_g);n!=INVALID;++n)
   772       for(NodeIt n(_g);n!=INVALID;++n)
   752         if(barrier(n))
   773         if(barrier(n))
   753           delta-=(*_supply)[n];
   774           delta-=(*_supply)[n];
   754       for(ArcIt e(_g);e!=INVALID;++e)
   775       for(ArcIt e(_g);e!=INVALID;++e)
   755         {
   776         {
   756           Node s=_g.source(e);
   777           Node s=_g.source(e);
   757           Node t=_g.target(e);
   778           Node t=_g.target(e);
   758           if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
   779           if(barrier(s)&&!barrier(t)) {
       
   780             if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
       
   781             delta+=(*_up)[e];
       
   782           }
   759           else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
   783           else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
   760         }
   784         }
   761       return _tol.negative(delta);
   785       return _tol.negative(delta);
   762     }
   786     }
   763 
   787