/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  *

  * Permission to use, modify and distribute this software is granted

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * provided that this copyright notice appears in all copies. For

     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

     typedef UM UpperMap;

     typedef UM UpperMap;

     /// \brief The type of supply map.

     /// \brief The type of supply map.

     ///

     ///

     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

     typedef SM SupplyMap;

     typedef SM SupplyMap;

     /// \brief The type of the flow and supply values.

     /// \brief The type of the flow and supply values.

     typedef typename SupplyMap::Value Value;

     typedef typename SupplyMap::Value Value;

      solution of the following problem.

      solution of the following problem.

      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)

      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)

      \geq sup(u) \quad \forall u\in V, \f]

      \geq sup(u) \quad \forall u\in V, \f]

      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \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

      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

      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).

      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

      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,

      supply and all the supplies have to be carried out from the supply nodes,

      but there could be demands that are not satisfied.

      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

      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

      constraints have to be satisfied with equality, i.e. all demands

      have to be satisfied and all supplies have to be used.

      have to be satisfied and all supplies have to be used.

      If you need the opposite inequalities in the supply/demand constraints

      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

      (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),

      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

      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

      the direction of the arcs and taking the negative of the supply values

     /// The constructor of the class.

     /// The constructor of the class.

     ///

     ///

     /// \param graph The digraph the algorithm runs on.

     /// \param graph The digraph the algorithm runs on.

     /// \param lower The lower bounds for the flow values on the arcs.

     /// \param lower The lower bounds for the flow values on the arcs.

     /// on the arcs.

     /// on the arcs.

     /// \param supply The signed supply values of the nodes.

     /// \param supply The signed supply values of the nodes.

     Circulation(const Digraph &graph, const LowerMap &lower,

     Circulation(const Digraph &graph, const LowerMap &lower,

                 const UpperMap &upper, const SupplyMap &supply)

                 const UpperMap &upper, const SupplyMap &supply)

       : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),

       : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),