RhodeCode

  ///

  /// \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.

            typename UM, typename SM>

    /// \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;

    typedef typename SupplyMap::Value Flow;

    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"

    /// concept.

    typedef typename Digraph::template ArcMap<Flow> FlowMap;

    /// \param digraph The digraph for which we would like to define

    /// \param digraph The digraph for which we would like to define

    typedef lemon::Tolerance<Flow> Tolerance;

     This class implements a push-relabel algorithm for the \e network

     \e circulation problem.

     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.

     \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 LM The type of the lower bound map. The default

     \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

          typename SM,

          typename SM = typename GR::template NodeMap<typename UM::Value>,

          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >

    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;

    const LowerMap *_lo;

    const UpperMap *_up;

    const SupplyMap *_supply;

    typedef typename Digraph::template NodeMap<Flow> ExcessMap;

      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,

    /// Constructor.

    ///

    /// \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) {}

    /// Sets the lower bound map.

    /// Sets the lower bound map.

    Circulation& lowerMap(const LowerMap& map) {

    /// Sets the upper bound (capacity) map.

    /// Sets the upper bound (capacity) map.

    Circulation& upperMap(const LowerMap& map) {

    /// Sets the supply map.

    /// Sets the supply map.

    Circulation& supplyMap(const SupplyMap& map) {

      _supply = ↦

        _excess->set(n, (*_supply)[n]);

        _excess->set(n, (*_supply)[n]);

          Flow fc = -(*_excess)[_g.target(e)];

        Flow exc=(*_excess)[act];

          Flow fc=(*_up)[e]-(*_flow)[e];

          Flow fc=(*_flow)[e]-(*_lo)[e];

    Flow flow(const Arc& arc) const {

       \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]

          Flow dif=-(*_supply)[n];

      Flow delta=0;

          delta-=(*_supply)[n];

    typedef typename CapacityMap::Value Flow;

    typedef typename Digraph::template ArcMap<Flow> FlowMap;

    /// \param digraph The digraph for which we would like to define

    /// \param digraph The digraph for which we would like to define

    typedef lemon::Tolerance<Flow> Tolerance;

    typedef typename Traits::Flow Flow;

    typedef typename Digraph::template NodeMap<Flow> ExcessMap;

        Flow excess = 0;

        Flow rem = (*_capacity)[e] - (*_flow)[e];

        Flow rem = (*_flow)[e];

          Flow excess = (*_excess)[n];

            Flow rem = (*_capacity)[e] - (*_flow)[e];

            Flow rem = (*_flow)[e];

          Flow excess = (*_excess)[n];

            Flow rem = (*_capacity)[e] - (*_flow)[e];

            Flow rem = (*_flow)[e];

        Flow excess = (*_excess)[n];

          Flow rem = (*_capacity)[e] - (*_flow)[e];

          Flow rem = (*_flow)[e];

    Flow flowValue() const {

    Flow flow(const Arc& arc) const {

  typedef concepts::ReadMap<Node,VType> SupplyMap;

  SupplyMap supply;

  Circulation<Digraph, CapMap, CapMap, SupplyMap>

    ::Create circ_test(g,lcap,ucap,supply);

  circ_test.lowerMap(lcap);

  circ_test.upperMap(ucap);

  circ_test.supplyMap(supply);