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 / [611:85cb3aa71cce:600:0ba8dfce7259] in lemon-main


Ignore:
Files:
2 deleted
8 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r611 r590  
    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_{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]
     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]
    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 (lower and upper bounds)
    354 and arc costs.
     353in a network with capacity constraints and arc costs.
    355354Formally, let \f$G=(V,A)\f$ be a digraph,
    356355\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    357 upper 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$.
     356upper bounds for the flow values on the arcs,
    359357\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
    361 signed supply values of the nodes.
    362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    364 \f$-sup(u)\f$ demand.
    365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
    366 of 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 
    373 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    374 zero or negative in order to have a feasible solution (since the sum
    375 of the expressions on the left-hand side of the inequalities is zero).
    376 It means that the total demand must be greater or equal to the total
    377 supply and all the supplies have to be carried out from the supply nodes,
    378 but there could be demands that are not satisfied.
    379 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
    380 constraints have to be satisfied with equality, i.e. all demands
    381 have to be satisfied and all supplies have to be used.
    382 
    383 If 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
    385 have to be satisfied while there could be supplies that are not used),
    386 then you could easily transform the problem to the above form by reversing
    387 the direction of the arcs and taking the negative of the supply values
    388 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    389 However \ref NetworkSimplex algorithm also supports this form directly
    390 for the sake of convenience.
    391 
    392 A feasible solution for this problem can be found using \ref Circulation.
    393 
    394 Note that the above formulation is actually more general than the usual
    395 definition of the minimum cost flow problem, in which strict equalities
    396 are 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 
    401 However if the sum of the supply values is zero, then these two problems
    402 are equivalent. So if you need the equality form, you have to ensure this
    403 additional contraint for the algorithms.
    404 
    405 The dual solution of the minimum cost flow problem is represented by node
    406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
    407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
    408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
    409 node potentials the following \e complementary \e slackness optimality
    410 conditions 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  
    420 Here \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 
    424 All algorithms provide dual solution (node potentials) as well
    425 if an optimal flow is found.
    426 
    427 LEMON contains several algorithms for solving minimum cost flow problems.
    428  - \ref NetworkSimplex Primal Network Simplex algorithm with various
     358on the arcs, and
     359\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     360of the nodes.
     361A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     362the 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
     369LEMON contains several algorithms for solving minimum cost flow problems:
     370 - \ref CycleCanceling Cycle-canceling algorithms.
     371 - \ref CapacityScaling Successive shortest path algorithm with optional
     372   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
    429376   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
    433    capacity scaling.
    434  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    435  - \ref CycleCanceling Cycle-Canceling algorithms.
    436 
    437 Most of these implementations support the general inequality form of the
    438 minimum cost flow problem, but CancelAndTighten and CycleCanceling
    439 only support the equality form due to the primal method they use.
    440 
    441 In general NetworkSimplex is the most efficient implementation,
    442 but in special cases other algorithms could be faster.
    443 For example, if the total supply and/or capacities are rather small,
    444 CapacityScaling is usually the fastest algorithm (without effective scaling).
    445377*/
    446378

  • lemon/Makefile.am

    r611 r594  
    9494        lemon/min_cost_arborescence.h \
    9595        lemon/nauty_reader.h \
    96         lemon/network_simplex.h \
    9796        lemon/path.h \
    9897        lemon/preflow.h \

  • lemon/circulation.h

    r611 r581  
    3232  ///
    3333  /// Default traits class of Circulation class.
    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.
     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.
    3938  template <typename GR, typename LM,
    40             typename UM, typename SM>
     39            typename UM, typename DM>
    4140  struct CirculationDefaultTraits {
    4241
    … …  
    4443    typedef GR Digraph;
    4544
    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;
     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"
     64    /// concept.
     65    typedef DM DeltaMap;
    6566
    6667    /// \brief The type of the flow values.
    67     typedef typename SupplyMap::Value Flow;
     68    typedef typename DeltaMap::Value Value;
    6869
    6970    /// \brief The type of the map that stores the flow values.
    7071    ///
    7172    /// The type of the map that stores the flow values.
    72     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    73     /// concept.
    74     typedef typename Digraph::template ArcMap<Flow> FlowMap;
     73    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     74    typedef typename Digraph::template ArcMap<Value> FlowMap;
    7575
    7676    /// \brief Instantiates a FlowMap.
    7777    ///
    7878    /// This function instantiates a \ref FlowMap.
    79     /// \param digraph The digraph for which we would like to define
     79    /// \param digraph The digraph, to 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 for which we would like to define
     96    /// \param digraph The digraph, to 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<Flow> Tolerance;
     106    typedef lemon::Tolerance<Value> Tolerance;
    107107
    108108  };
    … …  
    112112
    113113     \ingroup max_flow
    114      This class implements a push-relabel algorithm for the \e network
    115      \e circulation problem.
     114     This class implements a push-relabel algorithm for the network
     115     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 are
    118      given for the difference between the outgoing and incoming flow
    119      at the nodes.
     117     are given for the flow values on the arcs and lower bounds
     118     are given for the supply values of the nodes.
    120119
    121120     The exact formulation of this problem is the following.
    122121     Let \f$G=(V,A)\f$ be a digraph,
    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".
     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.
    156139
    157140     \tparam GR The type of the digraph the algorithm runs on.
    158      \tparam LM The type of the lower bound map. The default
     141     \tparam LM The type of the lower bound capacity map. The default
    159142     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    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
     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
    163147     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    164148  */
    … …  
    167151          typename LM,
    168152          typename UM,
    169           typename SM,
     153          typename DM,
    170154          typename TR >
    171155#else
    … …  
    173157          typename LM = typename GR::template ArcMap<int>,
    174158          typename UM = LM,
    175           typename SM = typename GR::template NodeMap<typename UM::Value>,
    176           typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
     159          typename DM = typename GR::template NodeMap<typename UM::Value>,
     160          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
    177161#endif
    178162  class Circulation {
    … …  
    184168    typedef typename Traits::Digraph Digraph;
    185169    ///The type of the flow values.
    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;
     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;
    194179    ///The type of the flow map.
    195180    typedef typename Traits::FlowMap FlowMap;
    … …  
    207192    int _node_num;
    208193
    209     const LowerMap *_lo;
    210     const UpperMap *_up;
    211     const SupplyMap *_supply;
     194    const LCapMap *_lo;
     195    const UCapMap *_up;
     196    const DeltaMap *_delta;
    212197
    213198    FlowMap *_flow;
    … …  
    217202    bool _local_level;
    218203
    219     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     204    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    220205    ExcessMap* _excess;
    221206
    … …  
    247232    template <typename T>
    248233    struct SetFlowMap
    249       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     234      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    250235                           SetFlowMapTraits<T> > {
    251       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     236      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    252237                          SetFlowMapTraits<T> > Create;
    253238    };
    … …  
    273258    template <typename T>
    274259    struct SetElevator
    275       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     260      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    276261                           SetElevatorTraits<T> > {
    277       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     262      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    278263                          SetElevatorTraits<T> > Create;
    279264    };
    … …  
    301286    template <typename T>
    302287    struct SetStandardElevator
    303       : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     288      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    304289                       SetStandardElevatorTraits<T> > {
    305       typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
     290      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    306291                      SetStandardElevatorTraits<T> > Create;
    307292    };
    … …  
    315300  public:
    316301
    317     /// Constructor.
    318 
    319302    /// The constructor of the class.
    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) {}
     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() {}
    331314
    332315    /// Destructor.
    … …  
    368351  public:
    369352
    370     /// Sets the lower bound map.
    371 
    372     /// Sets the lower bound map.
     353    /// Sets the lower bound capacity map.
     354
     355    /// Sets the lower bound capacity map.
    373356    /// \return <tt>(*this)</tt>
    374     Circulation& lowerMap(const LowerMap& map) {
     357    Circulation& lowerCapMap(const LCapMap& map) {
    375358      _lo = &map;
    376359      return *this;
    377360    }
    378361
    379     /// Sets the upper bound (capacity) map.
    380 
    381     /// Sets the upper bound (capacity) map.
     362    /// Sets the upper bound capacity map.
     363
     364    /// Sets the upper bound capacity map.
    382365    /// \return <tt>(*this)</tt>
    383     Circulation& upperMap(const LowerMap& map) {
     366    Circulation& upperCapMap(const LCapMap& map) {
    384367      _up = &map;
    385368      return *this;
    386369    }
    387370
    388     /// Sets the supply map.
    389 
    390     /// Sets the supply map.
     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.
    391374    /// \return <tt>(*this)</tt>
    392     Circulation& supplyMap(const SupplyMap& map) {
    393       _supply = &map;
     375    Circulation& deltaMap(const DeltaMap& map) {
     376      _delta = &map;
    394377      return *this;
    395378    }
    … …  
    471454
    472455      for(NodeIt n(_g);n!=INVALID;++n) {
    473         (*_excess)[n] = (*_supply)[n];
     456        (*_excess)[n] = (*_delta)[n];
    474457      }
    475458
    … …  
    500483
    501484      for(NodeIt n(_g);n!=INVALID;++n) {
    502         (*_excess)[n] = (*_supply)[n];
     485        (*_excess)[n] = (*_delta)[n];
    503486      }
    504487
    … …  
    513496          (*_excess)[_g.source(e)] -= (*_lo)[e];
    514497        } else {
    515           Flow fc = -(*_excess)[_g.target(e)];
     498          Value fc = -(*_excess)[_g.target(e)];
    516499          _flow->set(e, fc);
    517500          (*_excess)[_g.target(e)] = 0;
    … …  
    546529        int actlevel=(*_level)[act];
    547530        int mlevel=_node_num;
    548         Flow exc=(*_excess)[act];
     531        Value exc=(*_excess)[act];
    549532
    550533        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    551534          Node v = _g.target(e);
    552           Flow fc=(*_up)[e]-(*_flow)[e];
     535          Value fc=(*_up)[e]-(*_flow)[e];
    553536          if(!_tol.positive(fc)) continue;
    554537          if((*_level)[v]<actlevel) {
    … …  
    574557        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    575558          Node v = _g.source(e);
    576           Flow fc=(*_flow)[e]-(*_lo)[e];
     559          Value fc=(*_flow)[e]-(*_lo)[e];
    577560          if(!_tol.positive(fc)) continue;
    578561          if((*_level)[v]<actlevel) {
    … …  
    650633    /// \pre Either \ref run() or \ref init() must be called before
    651634    /// using this function.
    652     Flow flow(const Arc& arc) const {
     635    Value flow(const Arc& arc) const {
    653636      return (*_flow)[arc];
    654637    }
    … …  
    669652       Barrier is a set \e B of nodes for which
    670653
    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]
     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]
    673656
    674657       holds. The existence of a set with this property prooves that a
    … …  
    733716      for(NodeIt n(_g);n!=INVALID;++n)
    734717        {
    735           Flow dif=-(*_supply)[n];
     718          Value dif=-(*_delta)[n];
    736719          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    737720          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
    … …  
    748731    bool checkBarrier() const
    749732    {
    750       Flow delta=0;
     733      Value delta=0;
    751734      for(NodeIt n(_g);n!=INVALID;++n)
    752735        if(barrier(n))
    753           delta-=(*_supply)[n];
     736          delta-=(*_delta)[n];
    754737      for(ArcIt e(_g);e!=INVALID;++e)
    755738        {

  • lemon/preflow.h

    r611 r581  
    4747
    4848    /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Flow;
     49    typedef typename CapacityMap::Value Value;
    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<Flow> FlowMap;
     55    typedef typename Digraph::template ArcMap<Value> FlowMap;
    5656
    5757    /// \brief Instantiates a FlowMap.
    5858    ///
    5959    /// This function instantiates a \ref FlowMap.
    60     /// \param digraph The digraph for which we would like to define
     60    /// \param digraph The digraph, to 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 for which we would like to define
     77    /// \param digraph The digraph, to 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<Flow> Tolerance;
     87    typedef lemon::Tolerance<Value> Tolerance;
    8888
    8989  };
    … …  
    126126    typedef typename Traits::CapacityMap CapacityMap;
    127127    ///The type of the flow values.
    128     typedef typename Traits::Flow Flow;
     128    typedef typename Traits::Value Value;
    129129
    130130    ///The type of the flow map.
    … …  
    152152    bool _local_level;
    153153
    154     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     154    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    155155    ExcessMap* _excess;
    156156
    … …  
    471471
    472472      for (NodeIt n(_graph); n != INVALID; ++n) {
    473         Flow excess = 0;
     473        Value 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         Flow rem = (*_capacity)[e] - (*_flow)[e];
     522        Value 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         Flow rem = (*_flow)[e];
     534        Value rem = (*_flow)[e];
    535535        if (_tolerance.positive(rem)) {
    536536          Node v = _graph.source(e);
    … …  
    565565
    566566        while (num > 0 && n != INVALID) {
    567           Flow excess = (*_excess)[n];
     567          Value excess = (*_excess)[n];
    568568          int new_level = _level->maxLevel();
    569569
    570570          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    571             Flow rem = (*_capacity)[e] - (*_flow)[e];
     571            Value 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             Flow rem = (*_flow)[e];
     594            Value 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           Flow excess = (*_excess)[n];
     640          Value excess = (*_excess)[n];
    641641          int new_level = _level->maxLevel();
    642642
    643643          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    644             Flow rem = (*_capacity)[e] - (*_flow)[e];
     644            Value 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             Flow rem = (*_flow)[e];
     667            Value 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         Flow excess = (*_excess)[n];
     781        Value 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           Flow rem = (*_capacity)[e] - (*_flow)[e];
     786          Value 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           Flow rem = (*_flow)[e];
     809          Value 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     Flow flowValue() const {
     900    Value flowValue() const {
    901901      return (*_excess)[_target];
    902902    }
    … …  
    909909    /// \pre Either \ref run() or \ref init() must be called before
    910910    /// using this function.
    911     Flow flow(const Arc& arc) const {
     911    Value flow(const Arc& arc) const {
    912912      return (*_flow)[arc];
    913913    }

  • test/CMakeLists.txt

    r611 r594  
    3232  matching_test
    3333  min_cost_arborescence_test
    34   min_cost_flow_test
    3534  path_test
    3635  preflow_test

  • test/Makefile.am

    r611 r594  
    2828        test/matching_test \
    2929        test/min_cost_arborescence_test \
    30         test/min_cost_flow_test \
    3130        test/path_test \
    3231        test/preflow_test \
    … …  
    7473test_matching_test_SOURCES = test/matching_test.cc
    7574test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    76 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
    7775test_path_test_SOURCES = test/path_test.cc
    7876test_preflow_test_SOURCES = test/preflow_test.cc

  • test/circulation_test.cc

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

  • tools/dimacs-solver.cc

    r611 r594  
    4444#include <lemon/preflow.h>
    4545#include <lemon/matching.h>
    46 #include <lemon/network_simplex.h>
    4746
    4847using namespace lemon;
    … …  
    9291}
    9392
    94 template<class Value>
    95 void 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 
    11693void solve_mat(ArgParser &ap, std::istream &is, std::ostream &,
    11794              DimacsDescriptor &desc)
    … …  
    152129    {
    153130    case DimacsDescriptor::MIN:
    154       solve_min<Value>(ap,is,os,desc);
     131      std::cerr <<
     132        "\n\n Sorry, the min. cost flow solver is not yet available.\n";
    155133      break;
    156134    case DimacsDescriptor::MAX:
Note: See TracChangeset for help on using the changeset viewer.