lemon/circulation.h
changeset 621 b536eaacb39b
parent 581 aa1804409f29
parent 610 dacc2cee2b4c
child 622 28f58740b6f8
equal deleted inserted replaced
7:27531e6b14ad 9:6b2b32df34e3
    29 namespace lemon {
    29 namespace lemon {
    30 
    30 
    31   /// \brief Default traits class of Circulation class.
    31   /// \brief Default traits class of Circulation class.
    32   ///
    32   ///
    33   /// Default traits class of Circulation class.
    33   /// Default traits class of Circulation class.
    34   /// \tparam GR Digraph type.
    34   ///
    35   /// \tparam LM Lower bound capacity map type.
    35   /// \tparam GR Type of the digraph the algorithm runs on.
    36   /// \tparam UM Upper bound capacity map type.
    36   /// \tparam LM The type of the lower bound map.
    37   /// \tparam DM Delta map type.
    37   /// \tparam UM The type of the upper bound (capacity) map.
       
    38   /// \tparam SM The type of the supply map.
    38   template <typename GR, typename LM,
    39   template <typename GR, typename LM,
    39             typename UM, typename DM>
    40             typename UM, typename SM>
    40   struct CirculationDefaultTraits {
    41   struct CirculationDefaultTraits {
    41 
    42 
    42     /// \brief The type of the digraph the algorithm runs on.
    43     /// \brief The type of the digraph the algorithm runs on.
    43     typedef GR Digraph;
    44     typedef GR Digraph;
    44 
    45 
    45     /// \brief The type of the map that stores the circulation lower
    46     /// \brief The type of the lower bound map.
    46     /// bound.
    47     ///
    47     ///
    48     /// The type of the map that stores the lower bounds on the arcs.
    48     /// The type of the map that stores the circulation lower bound.
    49     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef LM LowerMap;
    50     typedef LM LCapMap;
    51 
    51 
    52     /// \brief The type of the upper bound (capacity) map.
    52     /// \brief The type of the map that stores the circulation upper
    53     ///
    53     /// bound.
    54     /// The type of the map that stores the upper bounds (capacities)
    54     ///
    55     /// on the arcs.
    55     /// The type of the map that stores the circulation upper bound.
    56     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    56     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    57     typedef UM UpperMap;
    57     typedef UM UCapMap;
    58 
    58 
    59     /// \brief The type of supply map.
    59     /// \brief The type of the map that stores the lower bound for
    60     ///
    60     /// the supply of the nodes.
    61     /// The type of the map that stores the signed supply values of the 
    61     ///
    62     /// nodes. 
    62     /// The type of the map that stores the lower bound for the supply
    63     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    63     /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
    64     typedef SM SupplyMap;
       
    65 
       
    66     /// \brief The type of the flow values.
       
    67     typedef typename SupplyMap::Value Flow;
       
    68 
       
    69     /// \brief The type of the map that stores the flow values.
       
    70     ///
       
    71     /// The type of the map that stores the flow values.
       
    72     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    64     /// concept.
    73     /// concept.
    65     typedef DM DeltaMap;
    74     typedef typename Digraph::template ArcMap<Flow> FlowMap;
    66 
       
    67     /// \brief The type of the flow values.
       
    68     typedef typename DeltaMap::Value Value;
       
    69 
       
    70     /// \brief The type of the map that stores the flow values.
       
    71     ///
       
    72     /// The type of the map that stores the flow values.
       
    73     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
       
    74     typedef typename Digraph::template ArcMap<Value> FlowMap;
       
    75 
    75 
    76     /// \brief Instantiates a FlowMap.
    76     /// \brief Instantiates a FlowMap.
    77     ///
    77     ///
    78     /// This function instantiates a \ref FlowMap.
    78     /// This function instantiates a \ref FlowMap.
    79     /// \param digraph The digraph, to which we would like to define
    79     /// \param digraph The digraph for which we would like to define
    80     /// the flow map.
    80     /// the flow map.
    81     static FlowMap* createFlowMap(const Digraph& digraph) {
    81     static FlowMap* createFlowMap(const Digraph& digraph) {
    82       return new FlowMap(digraph);
    82       return new FlowMap(digraph);
    83     }
    83     }
    84 
    84 
    91     typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    91     typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    92 
    92 
    93     /// \brief Instantiates an Elevator.
    93     /// \brief Instantiates an Elevator.
    94     ///
    94     ///
    95     /// This function instantiates an \ref Elevator.
    95     /// This function instantiates an \ref Elevator.
    96     /// \param digraph The digraph, to which we would like to define
    96     /// \param digraph The digraph for which we would like to define
    97     /// the elevator.
    97     /// the elevator.
    98     /// \param max_level The maximum level of the elevator.
    98     /// \param max_level The maximum level of the elevator.
    99     static Elevator* createElevator(const Digraph& digraph, int max_level) {
    99     static Elevator* createElevator(const Digraph& digraph, int max_level) {
   100       return new Elevator(digraph, max_level);
   100       return new Elevator(digraph, max_level);
   101     }
   101     }
   102 
   102 
   103     /// \brief The tolerance used by the algorithm
   103     /// \brief The tolerance used by the algorithm
   104     ///
   104     ///
   105     /// The tolerance used by the algorithm to handle inexact computation.
   105     /// The tolerance used by the algorithm to handle inexact computation.
   106     typedef lemon::Tolerance<Value> Tolerance;
   106     typedef lemon::Tolerance<Flow> Tolerance;
   107 
   107 
   108   };
   108   };
   109 
   109 
   110   /**
   110   /**
   111      \brief Push-relabel algorithm for the network circulation problem.
   111      \brief Push-relabel algorithm for the network circulation problem.
   112 
   112 
   113      \ingroup max_flow
   113      \ingroup max_flow
   114      This class implements a push-relabel algorithm for the network
   114      This class implements a push-relabel algorithm for the \e network
   115      circulation problem.
   115      \e circulation problem.
   116      It is to find a feasible circulation when lower and upper bounds
   116      It is to find a feasible circulation when lower and upper bounds
   117      are given for the flow values on the arcs and lower bounds
   117      are given for the flow values on the arcs and lower bounds are
   118      are given for the supply values of the nodes.
   118      given for the difference between the outgoing and incoming flow
       
   119      at the nodes.
   119 
   120 
   120      The exact formulation of this problem is the following.
   121      The exact formulation of this problem is the following.
   121      Let \f$G=(V,A)\f$ be a digraph,
   122      Let \f$G=(V,A)\f$ be a digraph,
   122      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
   123      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
   123      \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
   124      upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
   124      \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
   125      holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
   125      \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
   126      denotes the signed supply values of the nodes.
   126      \geq delta(v) \quad \forall v\in V, \f]
   127      If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
   127      \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
   128      supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
   128      \note \f$delta(v)\f$ specifies a lower bound for the supply of node
   129      \f$-sup(u)\f$ demand.
   129      \f$v\f$. It can be either positive or negative, however note that
   130      A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
   130      \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
   131      solution of the following problem.
   131      have a feasible solution.
   132 
   132 
   133      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
   133      \note A special case of this problem is when
   134      \geq sup(u) \quad \forall u\in V, \f]
   134      \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
   135      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
   135      will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
   136      
   136      Thus a feasible solution for the
   137      The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
   137      \ref min_cost_flow "minimum cost flow" problem can be calculated
   138      zero or negative in order to have a feasible solution (since the sum
   138      in this way.
   139      of the expressions on the left-hand side of the inequalities is zero).
       
   140      It means that the total demand must be greater or equal to the total
       
   141      supply and all the supplies have to be carried out from the supply nodes,
       
   142      but there could be demands that are not satisfied.
       
   143      If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
       
   144      constraints have to be satisfied with equality, i.e. all demands
       
   145      have to be satisfied and all supplies have to be used.
       
   146      
       
   147      If you need the opposite inequalities in the supply/demand constraints
       
   148      (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      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      (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
       
   153 
       
   154      Note that this algorithm also provides a feasible solution for the
       
   155      \ref min_cost_flow "minimum cost flow problem".
   139 
   156 
   140      \tparam GR The type of the digraph the algorithm runs on.
   157      \tparam GR The type of the digraph the algorithm runs on.
   141      \tparam LM The type of the lower bound capacity map. The default
   158      \tparam LM The type of the lower bound map. The default
   142      map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   159      map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   143      \tparam UM The type of the upper bound capacity map. The default
   160      \tparam UM The type of the upper bound (capacity) map.
   144      map type is \c LM.
   161      The default map type is \c LM.
   145      \tparam DM The type of the map that stores the lower bound
   162      \tparam SM The type of the supply map. The default map type is
   146      for the supply of the nodes. The default map type is
       
   147      \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
   163      \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
   148   */
   164   */
   149 #ifdef DOXYGEN
   165 #ifdef DOXYGEN
   150 template< typename GR,
   166 template< typename GR,
   151           typename LM,
   167           typename LM,
   152           typename UM,
   168           typename UM,
   153           typename DM,
   169           typename SM,
   154           typename TR >
   170           typename TR >
   155 #else
   171 #else
   156 template< typename GR,
   172 template< typename GR,
   157           typename LM = typename GR::template ArcMap<int>,
   173           typename LM = typename GR::template ArcMap<int>,
   158           typename UM = LM,
   174           typename UM = LM,
   159           typename DM = typename GR::template NodeMap<typename UM::Value>,
   175           typename SM = typename GR::template NodeMap<typename UM::Value>,
   160           typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
   176           typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
   161 #endif
   177 #endif
   162   class Circulation {
   178   class Circulation {
   163   public:
   179   public:
   164 
   180 
   165     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   181     ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   166     typedef TR Traits;
   182     typedef TR Traits;
   167     ///The type of the digraph the algorithm runs on.
   183     ///The type of the digraph the algorithm runs on.
   168     typedef typename Traits::Digraph Digraph;
   184     typedef typename Traits::Digraph Digraph;
   169     ///The type of the flow values.
   185     ///The type of the flow values.
   170     typedef typename Traits::Value Value;
   186     typedef typename Traits::Flow Flow;
   171 
   187 
   172     /// The type of the lower bound capacity map.
   188     ///The type of the lower bound map.
   173     typedef typename Traits::LCapMap LCapMap;
   189     typedef typename Traits::LowerMap LowerMap;
   174     /// The type of the upper bound capacity map.
   190     ///The type of the upper bound (capacity) map.
   175     typedef typename Traits::UCapMap UCapMap;
   191     typedef typename Traits::UpperMap UpperMap;
   176     /// \brief The type of the map that stores the lower bound for
   192     ///The type of the supply map.
   177     /// the supply of the nodes.
   193     typedef typename Traits::SupplyMap SupplyMap;
   178     typedef typename Traits::DeltaMap DeltaMap;
       
   179     ///The type of the flow map.
   194     ///The type of the flow map.
   180     typedef typename Traits::FlowMap FlowMap;
   195     typedef typename Traits::FlowMap FlowMap;
   181 
   196 
   182     ///The type of the elevator.
   197     ///The type of the elevator.
   183     typedef typename Traits::Elevator Elevator;
   198     typedef typename Traits::Elevator Elevator;
   189     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   204     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   190 
   205 
   191     const Digraph &_g;
   206     const Digraph &_g;
   192     int _node_num;
   207     int _node_num;
   193 
   208 
   194     const LCapMap *_lo;
   209     const LowerMap *_lo;
   195     const UCapMap *_up;
   210     const UpperMap *_up;
   196     const DeltaMap *_delta;
   211     const SupplyMap *_supply;
   197 
   212 
   198     FlowMap *_flow;
   213     FlowMap *_flow;
   199     bool _local_flow;
   214     bool _local_flow;
   200 
   215 
   201     Elevator* _level;
   216     Elevator* _level;
   202     bool _local_level;
   217     bool _local_level;
   203 
   218 
   204     typedef typename Digraph::template NodeMap<Value> ExcessMap;
   219     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
   205     ExcessMap* _excess;
   220     ExcessMap* _excess;
   206 
   221 
   207     Tolerance _tol;
   222     Tolerance _tol;
   208     int _el;
   223     int _el;
   209 
   224 
   229     ///
   244     ///
   230     /// \ref named-templ-param "Named parameter" for setting FlowMap
   245     /// \ref named-templ-param "Named parameter" for setting FlowMap
   231     /// type.
   246     /// type.
   232     template <typename T>
   247     template <typename T>
   233     struct SetFlowMap
   248     struct SetFlowMap
   234       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   249       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   235                            SetFlowMapTraits<T> > {
   250                            SetFlowMapTraits<T> > {
   236       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   251       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   237                           SetFlowMapTraits<T> > Create;
   252                           SetFlowMapTraits<T> > Create;
   238     };
   253     };
   239 
   254 
   240     template <typename T>
   255     template <typename T>
   241     struct SetElevatorTraits : public Traits {
   256     struct SetElevatorTraits : public Traits {
   255     /// \ref elevator(Elevator&) "elevator()" function before calling
   270     /// \ref elevator(Elevator&) "elevator()" function before calling
   256     /// \ref run() or \ref init().
   271     /// \ref run() or \ref init().
   257     /// \sa SetStandardElevator
   272     /// \sa SetStandardElevator
   258     template <typename T>
   273     template <typename T>
   259     struct SetElevator
   274     struct SetElevator
   260       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   275       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   261                            SetElevatorTraits<T> > {
   276                            SetElevatorTraits<T> > {
   262       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   277       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   263                           SetElevatorTraits<T> > Create;
   278                           SetElevatorTraits<T> > Create;
   264     };
   279     };
   265 
   280 
   266     template <typename T>
   281     template <typename T>
   267     struct SetStandardElevatorTraits : public Traits {
   282     struct SetStandardElevatorTraits : public Traits {
   283     /// algorithm with the \ref elevator(Elevator&) "elevator()" function
   298     /// algorithm with the \ref elevator(Elevator&) "elevator()" function
   284     /// before calling \ref run() or \ref init().
   299     /// before calling \ref run() or \ref init().
   285     /// \sa SetElevator
   300     /// \sa SetElevator
   286     template <typename T>
   301     template <typename T>
   287     struct SetStandardElevator
   302     struct SetStandardElevator
   288       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   303       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   289                        SetStandardElevatorTraits<T> > {
   304                        SetStandardElevatorTraits<T> > {
   290       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
   305       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
   291                       SetStandardElevatorTraits<T> > Create;
   306                       SetStandardElevatorTraits<T> > Create;
   292     };
   307     };
   293 
   308 
   294     /// @}
   309     /// @}
   295 
   310 
   297 
   312 
   298     Circulation() {}
   313     Circulation() {}
   299 
   314 
   300   public:
   315   public:
   301 
   316 
       
   317     /// Constructor.
       
   318 
   302     /// The constructor of the class.
   319     /// The constructor of the class.
   303 
   320     ///
   304     /// The constructor of the class.
   321     /// \param graph The digraph the algorithm runs on.
   305     /// \param g The digraph the algorithm runs on.
   322     /// \param lower The lower bounds for the flow values on the arcs.
   306     /// \param lo The lower bound capacity of the arcs.
   323     /// \param upper The upper bounds (capacities) for the flow values 
   307     /// \param up The upper bound capacity of the arcs.
   324     /// on the arcs.
   308     /// \param delta The lower bound for the supply of the nodes.
   325     /// \param supply The signed supply values of the nodes.
   309     Circulation(const Digraph &g,const LCapMap &lo,
   326     Circulation(const Digraph &graph, const LowerMap &lower,
   310                 const UCapMap &up,const DeltaMap &delta)
   327                 const UpperMap &upper, const SupplyMap &supply)
   311       : _g(g), _node_num(),
   328       : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
   312         _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
   329         _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
   313         _level(0), _local_level(false), _excess(0), _el() {}
   330         _excess(NULL) {}
   314 
   331 
   315     /// Destructor.
   332     /// Destructor.
   316     ~Circulation() {
   333     ~Circulation() {
   317       destroyStructures();
   334       destroyStructures();
   318     }
   335     }
   348       }
   365       }
   349     }
   366     }
   350 
   367 
   351   public:
   368   public:
   352 
   369 
   353     /// Sets the lower bound capacity map.
   370     /// Sets the lower bound map.
   354 
   371 
   355     /// Sets the lower bound capacity map.
   372     /// Sets the lower bound map.
   356     /// \return <tt>(*this)</tt>
   373     /// \return <tt>(*this)</tt>
   357     Circulation& lowerCapMap(const LCapMap& map) {
   374     Circulation& lowerMap(const LowerMap& map) {
   358       _lo = &map;
   375       _lo = &map;
   359       return *this;
   376       return *this;
   360     }
   377     }
   361 
   378 
   362     /// Sets the upper bound capacity map.
   379     /// Sets the upper bound (capacity) map.
   363 
   380 
   364     /// Sets the upper bound capacity map.
   381     /// Sets the upper bound (capacity) map.
   365     /// \return <tt>(*this)</tt>
   382     /// \return <tt>(*this)</tt>
   366     Circulation& upperCapMap(const LCapMap& map) {
   383     Circulation& upperMap(const LowerMap& map) {
   367       _up = &map;
   384       _up = &map;
   368       return *this;
   385       return *this;
   369     }
   386     }
   370 
   387 
   371     /// Sets the lower bound map for the supply of the nodes.
   388     /// Sets the supply map.
   372 
   389 
   373     /// Sets the lower bound map for the supply of the nodes.
   390     /// Sets the supply map.
   374     /// \return <tt>(*this)</tt>
   391     /// \return <tt>(*this)</tt>
   375     Circulation& deltaMap(const DeltaMap& map) {
   392     Circulation& supplyMap(const SupplyMap& map) {
   376       _delta = &map;
   393       _supply = &map;
   377       return *this;
   394       return *this;
   378     }
   395     }
   379 
   396 
   380     /// \brief Sets the flow map.
   397     /// \brief Sets the flow map.
   381     ///
   398     ///
   451     void init()
   468     void init()
   452     {
   469     {
   453       createStructures();
   470       createStructures();
   454 
   471 
   455       for(NodeIt n(_g);n!=INVALID;++n) {
   472       for(NodeIt n(_g);n!=INVALID;++n) {
   456         (*_excess)[n] = (*_delta)[n];
   473         (*_excess)[n] = (*_supply)[n];
   457       }
   474       }
   458 
   475 
   459       for (ArcIt e(_g);e!=INVALID;++e) {
   476       for (ArcIt e(_g);e!=INVALID;++e) {
   460         _flow->set(e, (*_lo)[e]);
   477         _flow->set(e, (*_lo)[e]);
   461         (*_excess)[_g.target(e)] += (*_flow)[e];
   478         (*_excess)[_g.target(e)] += (*_flow)[e];
   480     void greedyInit()
   497     void greedyInit()
   481     {
   498     {
   482       createStructures();
   499       createStructures();
   483 
   500 
   484       for(NodeIt n(_g);n!=INVALID;++n) {
   501       for(NodeIt n(_g);n!=INVALID;++n) {
   485         (*_excess)[n] = (*_delta)[n];
   502         (*_excess)[n] = (*_supply)[n];
   486       }
   503       }
   487 
   504 
   488       for (ArcIt e(_g);e!=INVALID;++e) {
   505       for (ArcIt e(_g);e!=INVALID;++e) {
   489         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
   506         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
   490           _flow->set(e, (*_up)[e]);
   507           _flow->set(e, (*_up)[e]);
   493         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
   510         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
   494           _flow->set(e, (*_lo)[e]);
   511           _flow->set(e, (*_lo)[e]);
   495           (*_excess)[_g.target(e)] += (*_lo)[e];
   512           (*_excess)[_g.target(e)] += (*_lo)[e];
   496           (*_excess)[_g.source(e)] -= (*_lo)[e];
   513           (*_excess)[_g.source(e)] -= (*_lo)[e];
   497         } else {
   514         } else {
   498           Value fc = -(*_excess)[_g.target(e)];
   515           Flow fc = -(*_excess)[_g.target(e)];
   499           _flow->set(e, fc);
   516           _flow->set(e, fc);
   500           (*_excess)[_g.target(e)] = 0;
   517           (*_excess)[_g.target(e)] = 0;
   501           (*_excess)[_g.source(e)] -= fc;
   518           (*_excess)[_g.source(e)] -= fc;
   502         }
   519         }
   503       }
   520       }
   526       Node bact=INVALID;
   543       Node bact=INVALID;
   527       Node last_activated=INVALID;
   544       Node last_activated=INVALID;
   528       while((act=_level->highestActive())!=INVALID) {
   545       while((act=_level->highestActive())!=INVALID) {
   529         int actlevel=(*_level)[act];
   546         int actlevel=(*_level)[act];
   530         int mlevel=_node_num;
   547         int mlevel=_node_num;
   531         Value exc=(*_excess)[act];
   548         Flow exc=(*_excess)[act];
   532 
   549 
   533         for(OutArcIt e(_g,act);e!=INVALID; ++e) {
   550         for(OutArcIt e(_g,act);e!=INVALID; ++e) {
   534           Node v = _g.target(e);
   551           Node v = _g.target(e);
   535           Value fc=(*_up)[e]-(*_flow)[e];
   552           Flow fc=(*_up)[e]-(*_flow)[e];
   536           if(!_tol.positive(fc)) continue;
   553           if(!_tol.positive(fc)) continue;
   537           if((*_level)[v]<actlevel) {
   554           if((*_level)[v]<actlevel) {
   538             if(!_tol.less(fc, exc)) {
   555             if(!_tol.less(fc, exc)) {
   539               _flow->set(e, (*_flow)[e] + exc);
   556               _flow->set(e, (*_flow)[e] + exc);
   540               (*_excess)[v] += exc;
   557               (*_excess)[v] += exc;
   554           }
   571           }
   555           else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
   572           else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
   556         }
   573         }
   557         for(InArcIt e(_g,act);e!=INVALID; ++e) {
   574         for(InArcIt e(_g,act);e!=INVALID; ++e) {
   558           Node v = _g.source(e);
   575           Node v = _g.source(e);
   559           Value fc=(*_flow)[e]-(*_lo)[e];
   576           Flow fc=(*_flow)[e]-(*_lo)[e];
   560           if(!_tol.positive(fc)) continue;
   577           if(!_tol.positive(fc)) continue;
   561           if((*_level)[v]<actlevel) {
   578           if((*_level)[v]<actlevel) {
   562             if(!_tol.less(fc, exc)) {
   579             if(!_tol.less(fc, exc)) {
   563               _flow->set(e, (*_flow)[e] - exc);
   580               _flow->set(e, (*_flow)[e] - exc);
   564               (*_excess)[v] += exc;
   581               (*_excess)[v] += exc;
   630     ///
   647     ///
   631     /// Returns the flow on the given arc.
   648     /// Returns the flow on the given arc.
   632     ///
   649     ///
   633     /// \pre Either \ref run() or \ref init() must be called before
   650     /// \pre Either \ref run() or \ref init() must be called before
   634     /// using this function.
   651     /// using this function.
   635     Value flow(const Arc& arc) const {
   652     Flow flow(const Arc& arc) const {
   636       return (*_flow)[arc];
   653       return (*_flow)[arc];
   637     }
   654     }
   638 
   655 
   639     /// \brief Returns a const reference to the flow map.
   656     /// \brief Returns a const reference to the flow map.
   640     ///
   657     ///
   649     /**
   666     /**
   650        \brief Returns \c true if the given node is in a barrier.
   667        \brief Returns \c true if the given node is in a barrier.
   651 
   668 
   652        Barrier is a set \e B of nodes for which
   669        Barrier is a set \e B of nodes for which
   653 
   670 
   654        \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
   671        \f[ \sum_{uv\in A: u\in B} upper(uv) -
   655            \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
   672            \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
   656 
   673 
   657        holds. The existence of a set with this property prooves that a
   674        holds. The existence of a set with this property prooves that a
   658        feasible circualtion cannot exist.
   675        feasible circualtion cannot exist.
   659 
   676 
   660        This function returns \c true if the given node is in the found
   677        This function returns \c true if the given node is in the found
   713     bool checkFlow() const {
   730     bool checkFlow() const {
   714       for(ArcIt e(_g);e!=INVALID;++e)
   731       for(ArcIt e(_g);e!=INVALID;++e)
   715         if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
   732         if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
   716       for(NodeIt n(_g);n!=INVALID;++n)
   733       for(NodeIt n(_g);n!=INVALID;++n)
   717         {
   734         {
   718           Value dif=-(*_delta)[n];
   735           Flow dif=-(*_supply)[n];
   719           for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
   736           for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
   720           for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
   737           for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
   721           if(_tol.negative(dif)) return false;
   738           if(_tol.negative(dif)) return false;
   722         }
   739         }
   723       return true;
   740       return true;
   728     ///Check whether or not the last execution provides a barrier.
   745     ///Check whether or not the last execution provides a barrier.
   729     ///\sa barrier()
   746     ///\sa barrier()
   730     ///\sa barrierMap()
   747     ///\sa barrierMap()
   731     bool checkBarrier() const
   748     bool checkBarrier() const
   732     {
   749     {
   733       Value delta=0;
   750       Flow delta=0;
   734       for(NodeIt n(_g);n!=INVALID;++n)
   751       for(NodeIt n(_g);n!=INVALID;++n)
   735         if(barrier(n))
   752         if(barrier(n))
   736           delta-=(*_delta)[n];
   753           delta-=(*_supply)[n];
   737       for(ArcIt e(_g);e!=INVALID;++e)
   754       for(ArcIt e(_g);e!=INVALID;++e)
   738         {
   755         {
   739           Node s=_g.source(e);
   756           Node s=_g.source(e);
   740           Node t=_g.target(e);
   757           Node t=_g.target(e);
   741           if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
   758           if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];