lemon/circulation.h
changeset 955 7f6eeffe3cd1
parent 825 75e6020b19b1
child 998 7fdaa05a69a1
equal deleted inserted replaced
17:cbd5b181a165 18:03b137457c2c
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    57     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    57     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    58     typedef UM UpperMap;
    58     typedef UM UpperMap;
    59 
    59 
    60     /// \brief The type of supply map.
    60     /// \brief The type of supply map.
    61     ///
    61     ///
    62     /// The type of the map that stores the signed supply values of the 
    62     /// The type of the map that stores the signed supply values of the
    63     /// nodes. 
    63     /// nodes.
    64     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    64     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    65     typedef SM SupplyMap;
    65     typedef SM SupplyMap;
    66 
    66 
    67     /// \brief The type of the flow and supply values.
    67     /// \brief The type of the flow and supply values.
    68     typedef typename SupplyMap::Value Value;
    68     typedef typename SupplyMap::Value Value;
   139      solution of the following problem.
   139      solution of the following problem.
   140 
   140 
   141      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
   141      \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
   142      \geq sup(u) \quad \forall u\in V, \f]
   142      \geq sup(u) \quad \forall u\in V, \f]
   143      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
   143      \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
   144      
   144 
   145      The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
   145      The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
   146      zero or negative in order to have a feasible solution (since the sum
   146      zero or negative in order to have a feasible solution (since the sum
   147      of the expressions on the left-hand side of the inequalities is zero).
   147      of the expressions on the left-hand side of the inequalities is zero).
   148      It means that the total demand must be greater or equal to the total
   148      It means that the total demand must be greater or equal to the total
   149      supply and all the supplies have to be carried out from the supply nodes,
   149      supply and all the supplies have to be carried out from the supply nodes,
   150      but there could be demands that are not satisfied.
   150      but there could be demands that are not satisfied.
   151      If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
   151      If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
   152      constraints have to be satisfied with equality, i.e. all demands
   152      constraints have to be satisfied with equality, i.e. all demands
   153      have to be satisfied and all supplies have to be used.
   153      have to be satisfied and all supplies have to be used.
   154      
   154 
   155      If you need the opposite inequalities in the supply/demand constraints
   155      If you need the opposite inequalities in the supply/demand constraints
   156      (i.e. the total demand is less than the total supply and all the demands
   156      (i.e. the total demand is less than the total supply and all the demands
   157      have to be satisfied while there could be supplies that are not used),
   157      have to be satisfied while there could be supplies that are not used),
   158      then you could easily transform the problem to the above form by reversing
   158      then you could easily transform the problem to the above form by reversing
   159      the direction of the arcs and taking the negative of the supply values
   159      the direction of the arcs and taking the negative of the supply values
   335 
   335 
   336     /// The constructor of the class.
   336     /// The constructor of the class.
   337     ///
   337     ///
   338     /// \param graph The digraph the algorithm runs on.
   338     /// \param graph The digraph the algorithm runs on.
   339     /// \param lower The lower bounds for the flow values on the arcs.
   339     /// \param lower The lower bounds for the flow values on the arcs.
   340     /// \param upper The upper bounds (capacities) for the flow values 
   340     /// \param upper The upper bounds (capacities) for the flow values
   341     /// on the arcs.
   341     /// on the arcs.
   342     /// \param supply The signed supply values of the nodes.
   342     /// \param supply The signed supply values of the nodes.
   343     Circulation(const Digraph &graph, const LowerMap &lower,
   343     Circulation(const Digraph &graph, const LowerMap &lower,
   344                 const UpperMap &upper, const SupplyMap &supply)
   344                 const UpperMap &upper, const SupplyMap &supply)
   345       : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
   345       : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),