Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h	(revision 628)
+++ lemon/circulation.h	(revision 657)
@@ -32,10 +32,11 @@
   ///
   /// Default traits class of Circulation class.
-  /// \tparam GR Digraph type.
-  /// \tparam LM Lower bound capacity map type.
-  /// \tparam UM Upper bound capacity map type.
-  /// \tparam DM Delta map type.
+  ///
+  /// \tparam GR Type of the digraph the algorithm runs on.
+  /// \tparam LM The type of the lower bound map.
+  /// \tparam UM The type of the upper bound (capacity) map.
+  /// \tparam SM The type of the supply map.
   template <typename GR, typename LM,
-            typename UM, typename DM>
+            typename UM, typename SM>
   struct CirculationDefaultTraits {
 
@@ -43,39 +44,38 @@
     typedef GR Digraph;
 
-    /// \brief The type of the map that stores the circulation lower
-    /// bound.
-    ///
-    /// The type of the map that stores the circulation lower bound.
-    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef LM LCapMap;
-
-    /// \brief The type of the map that stores the circulation upper
-    /// bound.
-    ///
-    /// The type of the map that stores the circulation upper bound.
-    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
-    typedef UM UCapMap;
-
-    /// \brief The type of the map that stores the lower bound for
-    /// the supply of the nodes.
-    ///
-    /// The type of the map that stores the lower bound for the supply
-    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
+    /// \brief The type of the lower bound map.
+    ///
+    /// The type of the map that stores the lower bounds on the arcs.
+    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    typedef LM LowerMap;
+
+    /// \brief The type of the upper bound (capacity) map.
+    ///
+    /// The type of the map that stores the upper bounds (capacities)
+    /// on the arcs.
+    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    typedef UM UpperMap;
+
+    /// \brief The type of supply map.
+    ///
+    /// The type of the map that stores the signed supply values of the 
+    /// nodes. 
+    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    typedef SM SupplyMap;
+
+    /// \brief The type of the flow values.
+    typedef typename SupplyMap::Value Flow;
+
+    /// \brief The type of the map that stores the flow values.
+    ///
+    /// The type of the map that stores the flow values.
+    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
     /// concept.
-    typedef DM DeltaMap;
-
-    /// \brief The type of the flow values.
-    typedef typename DeltaMap::Value Value;
-
-    /// \brief The type of the map that stores the flow values.
-    ///
-    /// The type of the map that stores the flow values.
-    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
-    typedef typename Digraph::template ArcMap<Value> FlowMap;
+    typedef typename Digraph::template ArcMap<Flow> FlowMap;
 
     /// \brief Instantiates a FlowMap.
     ///
     /// This function instantiates a \ref FlowMap.
-    /// \param digraph The digraph, to which we would like to define
+    /// \param digraph The digraph for which we would like to define
     /// the flow map.
     static FlowMap* createFlowMap(const Digraph& digraph) {
@@ -94,5 +94,5 @@
     ///
     /// This function instantiates an \ref Elevator.
-    /// \param digraph The digraph, to which we would like to define
+    /// \param digraph The digraph for which we would like to define
     /// the elevator.
     /// \param max_level The maximum level of the elevator.
@@ -104,5 +104,5 @@
     ///
     /// The tolerance used by the algorithm to handle inexact computation.
-    typedef lemon::Tolerance<Value> Tolerance;
+    typedef lemon::Tolerance<Flow> Tolerance;
 
   };
@@ -112,37 +112,53 @@
 
      \ingroup max_flow
-     This class implements a push-relabel algorithm for the network
-     circulation problem.
+     This class implements a push-relabel algorithm for the \e network
+     \e circulation problem.
      It is to find a feasible circulation when lower and upper bounds
-     are given for the flow values on the arcs and lower bounds
-     are given for the supply values of the nodes.
+     are given for the flow values on the arcs and lower bounds are
+     given for the difference between the outgoing and incoming flow
+     at the nodes.
 
      The exact formulation of this problem is the following.
      Let \f$G=(V,A)\f$ be a digraph,
-     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
-     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
-     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
-     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
-     \geq delta(v) \quad \forall v\in V, \f]
-     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
-     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
-     \f$v\f$. It can be either positive or negative, however note that
-     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
-     have a feasible solution.
-
-     \note A special case of this problem is when
-     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
-     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
-     Thus a feasible solution for the
-     \ref min_cost_flow "minimum cost flow" problem can be calculated
-     in this way.
+     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
+     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
+     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
+     denotes the signed supply values of the nodes.
+     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
+     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
+     \f$-sup(u)\f$ demand.
+     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
+     solution of the following problem.
+
+     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
+     \geq sup(u) \quad \forall u\in V, \f]
+     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
+     
+     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
+     zero or negative in order to have a feasible solution (since the sum
+     of the expressions on the left-hand side of the inequalities is zero).
+     It means that the total demand must be greater or equal to the total
+     supply and all the supplies have to be carried out from the supply nodes,
+     but there could be demands that are not satisfied.
+     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
+     constraints have to be satisfied with equality, i.e. all demands
+     have to be satisfied and all supplies have to be used.
+     
+     If you need the opposite inequalities in the supply/demand constraints
+     (i.e. the total demand is less than the total supply and all the demands
+     have to be satisfied while there could be supplies that are not used),
+     then you could easily transform the problem to the above form by reversing
+     the direction of the arcs and taking the negative of the supply values
+     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
+
+     Note that this algorithm also provides a feasible solution for the
+     \ref min_cost_flow "minimum cost flow problem".
 
      \tparam GR The type of the digraph the algorithm runs on.
-     \tparam LM The type of the lower bound capacity map. The default
+     \tparam LM The type of the lower bound map. The default
      map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
-     \tparam UM The type of the upper bound capacity map. The default
-     map type is \c LM.
-     \tparam DM The type of the map that stores the lower bound
-     for the supply of the nodes. The default map type is
+     \tparam UM The type of the upper bound (capacity) map.
+     The default map type is \c LM.
+     \tparam SM The type of the supply map. The default map type is
      \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
   */
@@ -151,5 +167,5 @@
           typename LM,
           typename UM,
-          typename DM,
+          typename SM,
           typename TR >
 #else
@@ -157,6 +173,6 @@
           typename LM = typename GR::template ArcMap<int>,
           typename UM = LM,
-          typename DM = typename GR::template NodeMap<typename UM::Value>,
-          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
+          typename SM = typename GR::template NodeMap<typename UM::Value>,
+          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 #endif
   class Circulation {
@@ -168,13 +184,12 @@
     typedef typename Traits::Digraph Digraph;
     ///The type of the flow values.
-    typedef typename Traits::Value Value;
-
-    /// The type of the lower bound capacity map.
-    typedef typename Traits::LCapMap LCapMap;
-    /// The type of the upper bound capacity map.
-    typedef typename Traits::UCapMap UCapMap;
-    /// \brief The type of the map that stores the lower bound for
-    /// the supply of the nodes.
-    typedef typename Traits::DeltaMap DeltaMap;
+    typedef typename Traits::Flow Flow;
+
+    ///The type of the lower bound map.
+    typedef typename Traits::LowerMap LowerMap;
+    ///The type of the upper bound (capacity) map.
+    typedef typename Traits::UpperMap UpperMap;
+    ///The type of the supply map.
+    typedef typename Traits::SupplyMap SupplyMap;
     ///The type of the flow map.
     typedef typename Traits::FlowMap FlowMap;
@@ -192,7 +207,7 @@
     int _node_num;
 
-    const LCapMap *_lo;
-    const UCapMap *_up;
-    const DeltaMap *_delta;
+    const LowerMap *_lo;
+    const UpperMap *_up;
+    const SupplyMap *_supply;
 
     FlowMap *_flow;
@@ -202,5 +217,5 @@
     bool _local_level;
 
-    typedef typename Digraph::template NodeMap<Value> ExcessMap;
+    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     ExcessMap* _excess;
 
@@ -216,7 +231,7 @@
     ///@{
 
-    template <typename T>
+    template <typename _FlowMap>
     struct SetFlowMapTraits : public Traits {
-      typedef T FlowMap;
+      typedef _FlowMap FlowMap;
       static FlowMap *createFlowMap(const Digraph&) {
         LEMON_ASSERT(false, "FlowMap is not initialized");
@@ -230,15 +245,15 @@
     /// \ref named-templ-param "Named parameter" for setting FlowMap
     /// type.
-    template <typename T>
+    template <typename _FlowMap>
     struct SetFlowMap
-      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-                           SetFlowMapTraits<T> > {
-      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-                          SetFlowMapTraits<T> > Create;
+      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
+                           SetFlowMapTraits<_FlowMap> > {
+      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
+                          SetFlowMapTraits<_FlowMap> > Create;
     };
 
-    template <typename T>
+    template <typename _Elevator>
     struct SetElevatorTraits : public Traits {
-      typedef T Elevator;
+      typedef _Elevator Elevator;
       static Elevator *createElevator(const Digraph&, int) {
         LEMON_ASSERT(false, "Elevator is not initialized");
@@ -256,15 +271,15 @@
     /// \ref run() or \ref init().
     /// \sa SetStandardElevator
-    template <typename T>
+    template <typename _Elevator>
     struct SetElevator
-      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-                           SetElevatorTraits<T> > {
-      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-                          SetElevatorTraits<T> > Create;
+      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
+                           SetElevatorTraits<_Elevator> > {
+      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
+                          SetElevatorTraits<_Elevator> > Create;
     };
 
-    template <typename T>
+    template <typename _Elevator>
     struct SetStandardElevatorTraits : public Traits {
-      typedef T Elevator;
+      typedef _Elevator Elevator;
       static Elevator *createElevator(const Digraph& digraph, int max_level) {
         return new Elevator(digraph, max_level);
@@ -284,10 +299,10 @@
     /// before calling \ref run() or \ref init().
     /// \sa SetElevator
-    template <typename T>
+    template <typename _Elevator>
     struct SetStandardElevator
-      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-                       SetStandardElevatorTraits<T> > {
-      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
-                      SetStandardElevatorTraits<T> > Create;
+      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
+                       SetStandardElevatorTraits<_Elevator> > {
+      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
+                      SetStandardElevatorTraits<_Elevator> > Create;
     };
 
@@ -300,16 +315,18 @@
   public:
 
+    /// Constructor.
+
     /// The constructor of the class.
-
-    /// The constructor of the class.
-    /// \param g The digraph the algorithm runs on.
-    /// \param lo The lower bound capacity of the arcs.
-    /// \param up The upper bound capacity of the arcs.
-    /// \param delta The lower bound for the supply of the nodes.
-    Circulation(const Digraph &g,const LCapMap &lo,
-                const UCapMap &up,const DeltaMap &delta)
-      : _g(g), _node_num(),
-        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
-        _level(0), _local_level(false), _excess(0), _el() {}
+    ///
+    /// \param graph The digraph the algorithm runs on.
+    /// \param lower The lower bounds for the flow values on the arcs.
+    /// \param upper The upper bounds (capacities) for the flow values 
+    /// on the arcs.
+    /// \param supply The signed supply values of the nodes.
+    Circulation(const Digraph &graph, const LowerMap &lower,
+                const UpperMap &upper, const SupplyMap &supply)
+      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
+        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
+        _excess(NULL) {}
 
     /// Destructor.
@@ -351,28 +368,28 @@
   public:
 
-    /// Sets the lower bound capacity map.
-
-    /// Sets the lower bound capacity map.
+    /// Sets the lower bound map.
+
+    /// Sets the lower bound map.
     /// \return <tt>(*this)</tt>
-    Circulation& lowerCapMap(const LCapMap& map) {
+    Circulation& lowerMap(const LowerMap& map) {
       _lo = &map;
       return *this;
     }
 
-    /// Sets the upper bound capacity map.
-
-    /// Sets the upper bound capacity map.
+    /// Sets the upper bound (capacity) map.
+
+    /// Sets the upper bound (capacity) map.
     /// \return <tt>(*this)</tt>
-    Circulation& upperCapMap(const LCapMap& map) {
+    Circulation& upperMap(const LowerMap& map) {
       _up = &map;
       return *this;
     }
 
-    /// Sets the lower bound map for the supply of the nodes.
-
-    /// Sets the lower bound map for the supply of the nodes.
+    /// Sets the supply map.
+
+    /// Sets the supply map.
     /// \return <tt>(*this)</tt>
-    Circulation& deltaMap(const DeltaMap& map) {
-      _delta = &map;
+    Circulation& supplyMap(const SupplyMap& map) {
+      _supply = &map;
       return *this;
     }
@@ -454,11 +471,11 @@
 
       for(NodeIt n(_g);n!=INVALID;++n) {
-        (*_excess)[n] = (*_delta)[n];
+        _excess->set(n, (*_supply)[n]);
       }
 
       for (ArcIt e(_g);e!=INVALID;++e) {
         _flow->set(e, (*_lo)[e]);
-        (*_excess)[_g.target(e)] += (*_flow)[e];
-        (*_excess)[_g.source(e)] -= (*_flow)[e];
+        _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
+        _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
       }
 
@@ -483,5 +500,5 @@
 
       for(NodeIt n(_g);n!=INVALID;++n) {
-        (*_excess)[n] = (*_delta)[n];
+        _excess->set(n, (*_supply)[n]);
       }
 
@@ -489,15 +506,15 @@
         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
           _flow->set(e, (*_up)[e]);
-          (*_excess)[_g.target(e)] += (*_up)[e];
-          (*_excess)[_g.source(e)] -= (*_up)[e];
+          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
+          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
           _flow->set(e, (*_lo)[e]);
-          (*_excess)[_g.target(e)] += (*_lo)[e];
-          (*_excess)[_g.source(e)] -= (*_lo)[e];
+          _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
+          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
         } else {
-          Value fc = -(*_excess)[_g.target(e)];
+          Flow fc = -(*_excess)[_g.target(e)];
           _flow->set(e, fc);
-          (*_excess)[_g.target(e)] = 0;
-          (*_excess)[_g.source(e)] -= fc;
+          _excess->set(_g.target(e), 0);
+          _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
         }
       }
@@ -529,17 +546,17 @@
         int actlevel=(*_level)[act];
         int mlevel=_node_num;
-        Value exc=(*_excess)[act];
+        Flow exc=(*_excess)[act];
 
         for(OutArcIt e(_g,act);e!=INVALID; ++e) {
           Node v = _g.target(e);
-          Value fc=(*_up)[e]-(*_flow)[e];
+          Flow fc=(*_up)[e]-(*_flow)[e];
           if(!_tol.positive(fc)) continue;
           if((*_level)[v]<actlevel) {
             if(!_tol.less(fc, exc)) {
               _flow->set(e, (*_flow)[e] + exc);
-              (*_excess)[v] += exc;
+              _excess->set(v, (*_excess)[v] + exc);
               if(!_level->active(v) && _tol.positive((*_excess)[v]))
                 _level->activate(v);
-              (*_excess)[act] = 0;
+              _excess->set(act,0);
               _level->deactivate(act);
               goto next_l;
@@ -547,5 +564,5 @@
             else {
               _flow->set(e, (*_up)[e]);
-              (*_excess)[v] += fc;
+              _excess->set(v, (*_excess)[v] + fc);
               if(!_level->active(v) && _tol.positive((*_excess)[v]))
                 _level->activate(v);
@@ -557,13 +574,13 @@
         for(InArcIt e(_g,act);e!=INVALID; ++e) {
           Node v = _g.source(e);
-          Value fc=(*_flow)[e]-(*_lo)[e];
+          Flow fc=(*_flow)[e]-(*_lo)[e];
           if(!_tol.positive(fc)) continue;
           if((*_level)[v]<actlevel) {
             if(!_tol.less(fc, exc)) {
               _flow->set(e, (*_flow)[e] - exc);
-              (*_excess)[v] += exc;
+              _excess->set(v, (*_excess)[v] + exc);
               if(!_level->active(v) && _tol.positive((*_excess)[v]))
                 _level->activate(v);
-              (*_excess)[act] = 0;
+              _excess->set(act,0);
               _level->deactivate(act);
               goto next_l;
@@ -571,5 +588,5 @@
             else {
               _flow->set(e, (*_lo)[e]);
-              (*_excess)[v] += fc;
+              _excess->set(v, (*_excess)[v] + fc);
               if(!_level->active(v) && _tol.positive((*_excess)[v]))
                 _level->activate(v);
@@ -580,5 +597,5 @@
         }
 
-        (*_excess)[act] = exc;
+        _excess->set(act, exc);
         if(!_tol.positive(exc)) _level->deactivate(act);
         else if(mlevel==_node_num) {
@@ -633,5 +650,5 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    Value flow(const Arc& arc) const {
+    Flow flow(const Arc& arc) const {
       return (*_flow)[arc];
     }
@@ -652,6 +669,6 @@
        Barrier is a set \e B of nodes for which
 
-       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
-           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
+       \f[ \sum_{uv\in A: u\in B} upper(uv) -
+           \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
 
        holds. The existence of a set with this property prooves that a
@@ -683,5 +700,5 @@
     ///
     /// \note This function calls \ref barrier() for each node,
-    /// so it runs in O(n) time.
+    /// so it runs in \f$O(n)\f$ time.
     ///
     /// \pre Either \ref run() or \ref init() must be called before
@@ -716,5 +733,5 @@
       for(NodeIt n(_g);n!=INVALID;++n)
         {
-          Value dif=-(*_delta)[n];
+          Flow dif=-(*_supply)[n];
           for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
           for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
@@ -731,8 +748,8 @@
     bool checkBarrier() const
     {
-      Value delta=0;
+      Flow delta=0;
       for(NodeIt n(_g);n!=INVALID;++n)
         if(barrier(n))
-          delta-=(*_delta)[n];
+          delta-=(*_supply)[n];
       for(ArcIt e(_g);e!=INVALID;++e)
         {
