COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [600:0ba8dfce7259:611:85cb3aa71cce] in lemon-1.2


Ignore:
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r590 r611  
    318318The \e maximum \e flow \e problem is to find a flow of maximum value between
    319319a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    320 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     320digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    321321\f$s, t \in V\f$ source and target nodes.
    322 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     322A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
    323323following optimization problem.
    324324
    325 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    326 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    327     \qquad \forall v\in V\setminus\{s,t\} \f]
    328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
     325\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     326\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     327    \quad \forall u\in V\setminus\{s,t\} \f]
     328\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    329329
    330330LEMON contains several algorithms for solving maximum flow problems:
    … …  
    351351The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    352352minimum total cost from a set of supply nodes to a set of demand nodes
    353 in a network with capacity constraints and arc costs.
     353in a network with capacity constraints (lower and upper bounds)
     354and arc costs.
    354355Formally, let \f$G=(V,A)\f$ be a digraph,
    355356\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    356 upper bounds for the flow values on the arcs,
     357upper bounds for the flow values on the arcs, for which
     358\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
    357359\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    358 on the arcs, and
    359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    360 of the nodes.
    361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    362 the following optimization problem.
    363 
    364 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    366     supply(v) \qquad \forall v\in V \f]
    367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    368 
    369 LEMON contains several algorithms for solving minimum cost flow problems:
    370  - \ref CycleCanceling Cycle-canceling algorithms.
    371  - \ref CapacityScaling Successive shortest path algorithm with optional
     360on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
     361signed supply values of the nodes.
     362If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
     363supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
     364\f$-sup(u)\f$ demand.
     365A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
     366of the following optimization problem.
     367
     368\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
     369\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
     370    sup(u) \quad \forall u\in V \f]
     371\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
     372
     373The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
     374zero or negative in order to have a feasible solution (since the sum
     375of the expressions on the left-hand side of the inequalities is zero).
     376It means that the total demand must be greater or equal to the total
     377supply and all the supplies have to be carried out from the supply nodes,
     378but there could be demands that are not satisfied.
     379If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
     380constraints have to be satisfied with equality, i.e. all demands
     381have to be satisfied and all supplies have to be used.
     382
     383If you need the opposite inequalities in the supply/demand constraints
     384(i.e. the total demand is less than the total supply and all the demands
     385have to be satisfied while there could be supplies that are not used),
     386then you could easily transform the problem to the above form by reversing
     387the direction of the arcs and taking the negative of the supply values
     388(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     389However \ref NetworkSimplex algorithm also supports this form directly
     390for the sake of convenience.
     391
     392A feasible solution for this problem can be found using \ref Circulation.
     393
     394Note that the above formulation is actually more general than the usual
     395definition of the minimum cost flow problem, in which strict equalities
     396are required in the supply/demand contraints, i.e.
     397
     398\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
     399    sup(u) \quad \forall u\in V. \f]
     400
     401However if the sum of the supply values is zero, then these two problems
     402are equivalent. So if you need the equality form, you have to ensure this
     403additional contraint for the algorithms.
     404
     405The dual solution of the minimum cost flow problem is represented by node
     406potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
     407An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
     408is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
     409node potentials the following \e complementary \e slackness optimality
     410conditions hold.
     411
     412 - For all \f$uv\in A\f$ arcs:
     413   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
     414   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
     415   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
     416 - For all \f$u\in V\f$:
     417   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
     418     then \f$\pi(u)=0\f$.
     419 
     420Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
     421\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
     422\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
     423
     424All algorithms provide dual solution (node potentials) as well
     425if an optimal flow is found.
     426
     427LEMON contains several algorithms for solving minimum cost flow problems.
     428 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     429   pivot strategies.
     430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     431   cost scaling.
     432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    372433   capacity scaling.
    373  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    374    cost scaling.
    375  - \ref NetworkSimplex Primal network simplex algorithm with various
    376    pivot strategies.
     434 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     435 - \ref CycleCanceling Cycle-Canceling algorithms.
     436
     437Most of these implementations support the general inequality form of the
     438minimum cost flow problem, but CancelAndTighten and CycleCanceling
     439only support the equality form due to the primal method they use.
     440
     441In general NetworkSimplex is the most efficient implementation,
     442but in special cases other algorithms could be faster.
     443For example, if the total supply and/or capacities are rather small,
     444CapacityScaling is usually the fastest algorithm (without effective scaling).
    377445*/
    378446

  • lemon/Makefile.am

    r594 r611  
    9494        lemon/min_cost_arborescence.h \
    9595        lemon/nauty_reader.h \
     96        lemon/network_simplex.h \
    9697        lemon/path.h \
    9798        lemon/preflow.h \

  • lemon/circulation.h

    r581 r611  
    3232  ///
    3333  /// Default traits class of Circulation class.
    34   /// \tparam GR Digraph type.
    35   /// \tparam LM Lower bound capacity map type.
    36   /// \tparam UM Upper bound capacity map type.
    37   /// \tparam DM Delta map type.
     34  ///
     35  /// \tparam GR Type of the digraph the algorithm runs on.
     36  /// \tparam LM The type of the lower bound map.
     37  /// \tparam UM The type of the upper bound (capacity) map.
     38  /// \tparam SM The type of the supply map.
    3839  template <typename GR, typename LM,
    39             typename UM, typename DM>
     40            typename UM, typename SM>
    4041  struct CirculationDefaultTraits {
    4142
    … …  
    4344    typedef GR Digraph;
    4445
    45     /// \brief The type of the map that stores the circulation lower
    46     /// bound.
    47     ///
    48     /// The type of the map that stores the circulation lower bound.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef LM LCapMap;
    51 
    52     /// \brief The type of the map that stores the circulation upper
    53     /// bound.
    54     ///
    55     /// The type of the map that stores the circulation upper bound.
    56     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    57     typedef UM UCapMap;
    58 
    59     /// \brief The type of the map that stores the lower bound for
    60     /// the supply of the nodes.
    61     ///
    62     /// The type of the map that stores the lower bound for the supply
    63     /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
     46    /// \brief The type of the lower bound map.
     47    ///
     48    /// The type of the map that stores the lower bounds on the arcs.
     49    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     50    typedef LM LowerMap;
     51
     52    /// \brief The type of the upper bound (capacity) map.
     53    ///
     54    /// The type of the map that stores the upper bounds (capacities)
     55    /// on the arcs.
     56    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     57    typedef UM UpperMap;
     58
     59    /// \brief The type of supply map.
     60    ///
     61    /// The type of the map that stores the signed supply values of the
     62    /// nodes.
     63    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     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"
    6473    /// concept.
    65     typedef DM DeltaMap;
    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;
     74    typedef typename Digraph::template ArcMap<Flow> FlowMap;
    7575
    7676    /// \brief Instantiates a FlowMap.
    7777    ///
    7878    /// 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
    8080    /// the flow map.
    8181    static FlowMap* createFlowMap(const Digraph& digraph) {
    … …  
    9494    ///
    9595    /// 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
    9797    /// the elevator.
    9898    /// \param max_level The maximum level of the elevator.
    … …  
    104104    ///
    105105    /// The tolerance used by the algorithm to handle inexact computation.
    106     typedef lemon::Tolerance<Value> Tolerance;
     106    typedef lemon::Tolerance<Flow> Tolerance;
    107107
    108108  };
    … …  
    112112
    113113     \ingroup max_flow
    114      This class implements a push-relabel algorithm for the network
    115      circulation problem.
     114     This class implements a push-relabel algorithm for the \e network
     115     \e circulation problem.
    116116     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
    118      are given for the supply values of the nodes.
     117     are given for the flow values on the arcs and lower bounds are
     118     given for the difference between the outgoing and incoming flow
     119     at the nodes.
    119120
    120121     The exact formulation of this problem is the following.
    121122     Let \f$G=(V,A)\f$ be a digraph,
    122      \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
    123      \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
    124      \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
    125      \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
    126      \geq delta(v) \quad \forall v\in V, \f]
    127      \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
    128      \note \f$delta(v)\f$ specifies a lower bound for the supply of node
    129      \f$v\f$. It can be either positive or negative, however note that
    130      \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
    131      have a feasible solution.
    132 
    133      \note A special case of this problem is when
    134      \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
    135      will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
    136      Thus a feasible solution for the
    137      \ref min_cost_flow "minimum cost flow" problem can be calculated
    138      in this way.
     123     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
     124     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
     125     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
     126     denotes the signed supply values of the nodes.
     127     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
     128     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
     129     \f$-sup(u)\f$ demand.
     130     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
     131     solution of the following problem.
     132
     133     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
     134     \geq sup(u) \quad \forall u\in V, \f]
     135     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
     136     
     137     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
     138     zero or negative in order to have a feasible solution (since the sum
     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".
    139156
    140157     \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
    142159     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    143      \tparam UM The type of the upper bound capacity map. The default
    144      map type is \c LM.
    145      \tparam DM The type of the map that stores the lower bound
    146      for the supply of the nodes. The default map type is
     160     \tparam UM The type of the upper bound (capacity) map.
     161     The default map type is \c LM.
     162     \tparam SM The type of the supply map. The default map type is
    147163     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    148164  */
    … …  
    151167          typename LM,
    152168          typename UM,
    153           typename DM,
     169          typename SM,
    154170          typename TR >
    155171#else
    … …  
    157173          typename LM = typename GR::template ArcMap<int>,
    158174          typename UM = LM,
    159           typename DM = typename GR::template NodeMap<typename UM::Value>,
    160           typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
     175          typename SM = typename GR::template NodeMap<typename UM::Value>,
     176          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
    161177#endif
    162178  class Circulation {
    … …  
    168184    typedef typename Traits::Digraph Digraph;
    169185    ///The type of the flow values.
    170     typedef typename Traits::Value Value;
    171 
    172     /// The type of the lower bound capacity map.
    173     typedef typename Traits::LCapMap LCapMap;
    174     /// The type of the upper bound capacity map.
    175     typedef typename Traits::UCapMap UCapMap;
    176     /// \brief The type of the map that stores the lower bound for
    177     /// the supply of the nodes.
    178     typedef typename Traits::DeltaMap DeltaMap;
     186    typedef typename Traits::Flow Flow;
     187
     188    ///The type of the lower bound map.
     189    typedef typename Traits::LowerMap LowerMap;
     190    ///The type of the upper bound (capacity) map.
     191    typedef typename Traits::UpperMap UpperMap;
     192    ///The type of the supply map.
     193    typedef typename Traits::SupplyMap SupplyMap;
    179194    ///The type of the flow map.
    180195    typedef typename Traits::FlowMap FlowMap;
    … …  
    192207    int _node_num;
    193208
    194     const LCapMap *_lo;
    195     const UCapMap *_up;
    196     const DeltaMap *_delta;
     209    const LowerMap *_lo;
     210    const UpperMap *_up;
     211    const SupplyMap *_supply;
    197212
    198213    FlowMap *_flow;
    … …  
    202217    bool _local_level;
    203218
    204     typedef typename Digraph::template NodeMap<Value> ExcessMap;
     219    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
    205220    ExcessMap* _excess;
    206221
    … …  
    232247    template <typename T>
    233248    struct SetFlowMap
    234       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     249      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    235250                           SetFlowMapTraits<T> > {
    236       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     251      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    237252                          SetFlowMapTraits<T> > Create;
    238253    };
    … …  
    258273    template <typename T>
    259274    struct SetElevator
    260       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     275      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    261276                           SetElevatorTraits<T> > {
    262       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     277      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    263278                          SetElevatorTraits<T> > Create;
    264279    };
    … …  
    286301    template <typename T>
    287302    struct SetStandardElevator
    288       : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     303      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    289304                       SetStandardElevatorTraits<T> > {
    290       typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
     305      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    291306                      SetStandardElevatorTraits<T> > Create;
    292307    };
    … …  
    300315  public:
    301316
     317    /// Constructor.
     318
    302319    /// The constructor of the class.
    303 
    304     /// The constructor of the class.
    305     /// \param g The digraph the algorithm runs on.
    306     /// \param lo The lower bound capacity of the arcs.
    307     /// \param up The upper bound capacity of the arcs.
    308     /// \param delta The lower bound for the supply of the nodes.
    309     Circulation(const Digraph &g,const LCapMap &lo,
    310                 const UCapMap &up,const DeltaMap &delta)
    311       : _g(g), _node_num(),
    312         _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
    313         _level(0), _local_level(false), _excess(0), _el() {}
     320    ///
     321    /// \param graph The digraph the algorithm runs on.
     322    /// \param lower The lower bounds for the flow values on the arcs.
     323    /// \param upper The upper bounds (capacities) for the flow values
     324    /// on the arcs.
     325    /// \param supply The signed supply values of the nodes.
     326    Circulation(const Digraph &graph, const LowerMap &lower,
     327                const UpperMap &upper, const SupplyMap &supply)
     328      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
     329        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),
     330        _excess(NULL) {}
    314331
    315332    /// Destructor.
    … …  
    351368  public:
    352369
    353     /// Sets the lower bound capacity map.
    354 
    355     /// Sets the lower bound capacity map.
     370    /// Sets the lower bound map.
     371
     372    /// Sets the lower bound map.
    356373    /// \return <tt>(*this)</tt>
    357     Circulation& lowerCapMap(const LCapMap& map) {
     374    Circulation& lowerMap(const LowerMap& map) {
    358375      _lo = &map;
    359376      return *this;
    360377    }
    361378
    362     /// Sets the upper bound capacity map.
    363 
    364     /// Sets the upper bound capacity map.
     379    /// Sets the upper bound (capacity) map.
     380
     381    /// Sets the upper bound (capacity) map.
    365382    /// \return <tt>(*this)</tt>
    366     Circulation& upperCapMap(const LCapMap& map) {
     383    Circulation& upperMap(const LowerMap& map) {
    367384      _up = &map;
    368385      return *this;
    369386    }
    370387
    371     /// Sets the lower bound map for the supply of the nodes.
    372 
    373     /// Sets the lower bound map for the supply of the nodes.
     388    /// Sets the supply map.
     389
     390    /// Sets the supply map.
    374391    /// \return <tt>(*this)</tt>
    375     Circulation& deltaMap(const DeltaMap& map) {
    376       _delta = &map;
     392    Circulation& supplyMap(const SupplyMap& map) {
     393      _supply = &map;
    377394      return *this;
    378395    }
    … …  
    454471
    455472      for(NodeIt n(_g);n!=INVALID;++n) {
    456         (*_excess)[n] = (*_delta)[n];
     473        (*_excess)[n] = (*_supply)[n];
    457474      }
    458475
    … …  
    483500
    484501      for(NodeIt n(_g);n!=INVALID;++n) {
    485         (*_excess)[n] = (*_delta)[n];
     502        (*_excess)[n] = (*_supply)[n];
    486503      }
    487504
    … …  
    496513          (*_excess)[_g.source(e)] -= (*_lo)[e];
    497514        } else {
    498           Value fc = -(*_excess)[_g.target(e)];
     515          Flow fc = -(*_excess)[_g.target(e)];
    499516          _flow->set(e, fc);
    500517          (*_excess)[_g.target(e)] = 0;
    … …  
    529546        int actlevel=(*_level)[act];
    530547        int mlevel=_node_num;
    531         Value exc=(*_excess)[act];
     548        Flow exc=(*_excess)[act];
    532549
    533550        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    534551          Node v = _g.target(e);
    535           Value fc=(*_up)[e]-(*_flow)[e];
     552          Flow fc=(*_up)[e]-(*_flow)[e];
    536553          if(!_tol.positive(fc)) continue;
    537554          if((*_level)[v]<actlevel) {
    … …  
    557574        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    558575          Node v = _g.source(e);
    559           Value fc=(*_flow)[e]-(*_lo)[e];
     576          Flow fc=(*_flow)[e]-(*_lo)[e];
    560577          if(!_tol.positive(fc)) continue;
    561578          if((*_level)[v]<actlevel) {
    … …  
    633650    /// \pre Either \ref run() or \ref init() must be called before
    634651    /// using this function.
    635     Value flow(const Arc& arc) const {
     652    Flow flow(const Arc& arc) const {
    636653      return (*_flow)[arc];
    637654    }
    … …  
    652669       Barrier is a set \e B of nodes for which
    653670
    654        \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
    655            \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
     671       \f[ \sum_{uv\in A: u\in B} upper(uv) -
     672           \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f]
    656673
    657674       holds. The existence of a set with this property prooves that a
    … …  
    716733      for(NodeIt n(_g);n!=INVALID;++n)
    717734        {
    718           Value dif=-(*_delta)[n];
     735          Flow dif=-(*_supply)[n];
    719736          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    720737          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
    … …  
    731748    bool checkBarrier() const
    732749    {
    733       Value delta=0;
     750      Flow delta=0;
    734751      for(NodeIt n(_g);n!=INVALID;++n)
    735752        if(barrier(n))
    736           delta-=(*_delta)[n];
     753          delta-=(*_supply)[n];
    737754      for(ArcIt e(_g);e!=INVALID;++e)
    738755        {

  • lemon/preflow.h

    r581 r611  
    4747
    4848    /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Value;
     49    typedef typename CapacityMap::Value Flow;
    5050
    5151    /// \brief The type of the map that stores the flow values.
    … …  
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55     typedef typename Digraph::template ArcMap<Value> FlowMap;
     55    typedef typename Digraph::template ArcMap<Flow> FlowMap;
    5656
    5757    /// \brief Instantiates a FlowMap.
    5858    ///
    5959    /// This function instantiates a \ref FlowMap.
    60     /// \param digraph The digraph, to which we would like to define
     60    /// \param digraph The digraph for which we would like to define
    6161    /// the flow map.
    6262    static FlowMap* createFlowMap(const Digraph& digraph) {
    … …  
    7575    ///
    7676    /// This function instantiates an \ref Elevator.
    77     /// \param digraph The digraph, to which we would like to define
     77    /// \param digraph The digraph for which we would like to define
    7878    /// the elevator.
    7979    /// \param max_level The maximum level of the elevator.
    … …  
    8585    ///
    8686    /// The tolerance used by the algorithm to handle inexact computation.
    87     typedef lemon::Tolerance<Value> Tolerance;
     87    typedef lemon::Tolerance<Flow> Tolerance;
    8888
    8989  };
    … …  
    126126    typedef typename Traits::CapacityMap CapacityMap;
    127127    ///The type of the flow values.
    128     typedef typename Traits::Value Value;
     128    typedef typename Traits::Flow Flow;
    129129
    130130    ///The type of the flow map.
    … …  
    152152    bool _local_level;
    153153
    154     typedef typename Digraph::template NodeMap<Value> ExcessMap;
     154    typedef typename Digraph::template NodeMap<Flow> ExcessMap;
    155155    ExcessMap* _excess;
    156156
    … …  
    471471
    472472      for (NodeIt n(_graph); n != INVALID; ++n) {
    473         Value excess = 0;
     473        Flow excess = 0;
    474474        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    475475          excess += (*_flow)[e];
    … …  
    520520
    521521      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
    522         Value rem = (*_capacity)[e] - (*_flow)[e];
     522        Flow rem = (*_capacity)[e] - (*_flow)[e];
    523523        if (_tolerance.positive(rem)) {
    524524          Node u = _graph.target(e);
    … …  
    532532      }
    533533      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
    534         Value rem = (*_flow)[e];
     534        Flow rem = (*_flow)[e];
    535535        if (_tolerance.positive(rem)) {
    536536          Node v = _graph.source(e);
    … …  
    565565
    566566        while (num > 0 && n != INVALID) {
    567           Value excess = (*_excess)[n];
     567          Flow excess = (*_excess)[n];
    568568          int new_level = _level->maxLevel();
    569569
    570570          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    571             Value rem = (*_capacity)[e] - (*_flow)[e];
     571            Flow rem = (*_capacity)[e] - (*_flow)[e];
    572572            if (!_tolerance.positive(rem)) continue;
    573573            Node v = _graph.target(e);
    … …  
    592592
    593593          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    594             Value rem = (*_flow)[e];
     594            Flow rem = (*_flow)[e];
    595595            if (!_tolerance.positive(rem)) continue;
    596596            Node v = _graph.source(e);
    … …  
    638638        num = _node_num * 20;
    639639        while (num > 0 && n != INVALID) {
    640           Value excess = (*_excess)[n];
     640          Flow excess = (*_excess)[n];
    641641          int new_level = _level->maxLevel();
    642642
    643643          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    644             Value rem = (*_capacity)[e] - (*_flow)[e];
     644            Flow rem = (*_capacity)[e] - (*_flow)[e];
    645645            if (!_tolerance.positive(rem)) continue;
    646646            Node v = _graph.target(e);
    … …  
    665665
    666666          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    667             Value rem = (*_flow)[e];
     667            Flow rem = (*_flow)[e];
    668668            if (!_tolerance.positive(rem)) continue;
    669669            Node v = _graph.source(e);
    … …  
    779779      Node n;
    780780      while ((n = _level->highestActive()) != INVALID) {
    781         Value excess = (*_excess)[n];
     781        Flow excess = (*_excess)[n];
    782782        int level = _level->highestActiveLevel();
    783783        int new_level = _level->maxLevel();
    784784
    785785        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    786           Value rem = (*_capacity)[e] - (*_flow)[e];
     786          Flow rem = (*_capacity)[e] - (*_flow)[e];
    787787          if (!_tolerance.positive(rem)) continue;
    788788          Node v = _graph.target(e);
    … …  
    807807
    808808        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    809           Value rem = (*_flow)[e];
     809          Flow rem = (*_flow)[e];
    810810          if (!_tolerance.positive(rem)) continue;
    811811          Node v = _graph.source(e);
    … …  
    898898    /// \pre Either \ref run() or \ref init() must be called before
    899899    /// using this function.
    900     Value flowValue() const {
     900    Flow flowValue() const {
    901901      return (*_excess)[_target];
    902902    }
    … …  
    909909    /// \pre Either \ref run() or \ref init() must be called before
    910910    /// using this function.
    911     Value flow(const Arc& arc) const {
     911    Flow flow(const Arc& arc) const {
    912912      return (*_flow)[arc];
    913913    }

  • test/CMakeLists.txt

    r594 r611  
    3232  matching_test
    3333  min_cost_arborescence_test
     34  min_cost_flow_test
    3435  path_test
    3536  preflow_test

  • test/Makefile.am

    r594 r611  
    2828        test/matching_test \
    2929        test/min_cost_arborescence_test \
     30        test/min_cost_flow_test \
    3031        test/path_test \
    3132        test/preflow_test \
    … …  
    7374test_matching_test_SOURCES = test/matching_test.cc
    7475test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
     76test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
    7577test_path_test_SOURCES = test/path_test.cc
    7678test_preflow_test_SOURCES = test/preflow_test.cc

  • test/circulation_test.cc

    r585 r611  
    5858  typedef Digraph::Arc Arc;
    5959  typedef concepts::ReadMap<Arc,VType> CapMap;
    60   typedef concepts::ReadMap<Node,VType> DeltaMap;
     60  typedef concepts::ReadMap<Node,VType> SupplyMap;
    6161  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
    6262  typedef concepts::WriteMap<Node,bool> BarrierMap;
    … …  
    6969  Arc a;
    7070  CapMap lcap, ucap;
    71   DeltaMap delta;
     71  SupplyMap supply;
    7272  FlowMap flow;
    7373  BarrierMap bar;
    … …  
    7575  bool b;
    7676
    77   typedef Circulation<Digraph, CapMap, CapMap, DeltaMap>
     77  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
    7878            ::SetFlowMap<FlowMap>
    7979            ::SetElevator<Elev>
    8080            ::SetStandardElevator<LinkedElev>
    8181            ::Create CirculationType;
    82   CirculationType circ_test(g, lcap, ucap, delta);
     82  CirculationType circ_test(g, lcap, ucap, supply);
    8383  const CirculationType& const_circ_test = circ_test;
    8484   
    8585  circ_test
    86     .lowerCapMap(lcap)
    87     .upperCapMap(ucap)
    88     .deltaMap(delta)
     86    .lowerMap(lcap)
     87    .upperMap(ucap)
     88    .supplyMap(supply)
    8989    .flowMap(flow);
    9090

  • tools/dimacs-solver.cc

    r594 r611  
    4444#include <lemon/preflow.h>
    4545#include <lemon/matching.h>
     46#include <lemon/network_simplex.h>
    4647
    4748using namespace lemon;
    … …  
    9192}
    9293
     94template<class Value>
     95void solve_min(ArgParser &ap, std::istream &is, std::ostream &,
     96               DimacsDescriptor &desc)
     97{
     98  bool report = !ap.given("q");
     99  Digraph g;
     100  Digraph::ArcMap<Value> lower(g), cap(g), cost(g);
     101  Digraph::NodeMap<Value> sup(g);
     102  Timer ti;
     103  ti.restart();
     104  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
     105  if (report) std::cerr << "Read the file: " << ti << '\n';
     106  ti.restart();
     107  NetworkSimplex<Digraph, Value> ns(g);
     108  ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
     109  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
     110  ti.restart();
     111  ns.run();
     112  if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n';
     113  if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n';
     114}
     115
    93116void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    94117              DimacsDescriptor &desc)
    … …  
    129152    {
    130153    case DimacsDescriptor::MIN:
    131       std::cerr <<
    132         "\n\n Sorry, the min. cost flow solver is not yet available.\n";
     154      solve_min<Value>(ap,is,os,desc);
    133155      break;
    134156    case DimacsDescriptor::MAX:
Note: See TracChangeset for help on using the changeset viewer.