COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 611:85cb3aa71cce in lemon-main


Ignore:
Timestamp:
04/21/09 16:18:54 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
612:0c8e5c688440, 613:b1811c363299, 619:ec817dfc2cb7
Parents:
600:0ba8dfce7259 (diff), 610:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge and fix

Files:
16 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

  • doc/groups.dox

    r609 r611  
    2121/**
    2222@defgroup datas Data Structures
    23 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2424*/
    2525
    … …  
    143143\brief Graph types between real graphs and graph adaptors.
    144144
    145 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    146146These classes wrap graphs to give new functionality as the adaptors do it.
    147147On the other hand they are not light-weight structures as the adaptors.
    … …  
    153153\brief Map structures implemented in LEMON.
    154154
    155 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    156156
    157157LEMON provides several special purpose maps and map adaptors that e.g. combine
    … …  
    166166\brief Special graph-related maps.
    167167
    168 This group describes maps that are specifically designed to assign
     168This group contains maps that are specifically designed to assign
    169169values to the nodes and arcs/edges of graphs.
    170170
    … …  
    178178\brief Tools to create new maps from existing ones
    179179
    180 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    181181maps from other maps.
    182182
    … …  
    241241\brief Two dimensional data storages implemented in LEMON.
    242242
    243 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    244244*/
    245245
    … …  
    249249\brief %Path structures implemented in LEMON.
    250250
    251 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    252252
    253253LEMON provides flexible data structures to work with paths.
    … …  
    265265\brief Auxiliary data structures implemented in LEMON.
    266266
    267 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    268268order to make it easier to implement combinatorial algorithms.
    269269*/
    … …  
    271271/**
    272272@defgroup algs Algorithms
    273 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    274274implemented in LEMON.
    275275
    276 This group describes the several algorithms
     276This group contains the several algorithms
    277277implemented in LEMON.
    278278*/
    … …  
    283283\brief Common graph search algorithms.
    284284
    285 This group describes the common graph search algorithms, namely
     285This group contains the common graph search algorithms, namely
    286286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    287287*/
    … …  
    292292\brief Algorithms for finding shortest paths.
    293293
    294 This group describes the algorithms for finding shortest paths in digraphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
    295295
    296296 - \ref Dijkstra algorithm for finding shortest paths from a source node
    … …  
    313313\brief Algorithms for finding maximum flows.
    314314
    315 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    316316feasible circulations.
    317317
    … …  
    451451\brief Algorithms for finding minimum cut in graphs.
    452452
    453 This group describes the algorithms for finding minimum cut in graphs.
     453This group contains the algorithms for finding minimum cut in graphs.
    454454
    455455The \e minimum \e cut \e problem is to find a non-empty and non-complete
    … …  
    468468- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    469469  calculating minimum cut in undirected graphs.
    470 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     470- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    471471  all-pairs minimum cut in undirected graphs.
    472472
    … …  
    476476
    477477/**
    478 @defgroup graph_prop Connectivity and Other Graph Properties
     478@defgroup graph_properties Connectivity and Other Graph Properties
    479479@ingroup algs
    480480\brief Algorithms for discovering the graph properties
    481481
    482 This group describes the algorithms for discovering the graph properties
     482This group contains the algorithms for discovering the graph properties
    483483like connectivity, bipartiteness, euler property, simplicity etc.
    484484
    … …  
    492492\brief Algorithms for planarity checking, embedding and drawing
    493493
    494 This group describes the algorithms for planarity checking,
     494This group contains the algorithms for planarity checking,
    495495embedding and drawing.
    496496
    … …  
    504504\brief Algorithms for finding matchings in graphs and bipartite graphs.
    505505
    506 This group contains algorithm objects and functions to calculate
     506This group contains the algorithms for calculating
    507507matchings in graphs and bipartite graphs. The general matching problem is
    508 finding a subset of the arcs which does not shares common endpoints.
     508finding a subset of the edges for which each node has at most one incident
     509edge.
    509510
    510511There are several different algorithms for calculate matchings in
    … …  
    543544\brief Algorithms for finding a minimum cost spanning tree in a graph.
    544545
    545 This group describes the algorithms for finding a minimum cost spanning
     546This group contains the algorithms for finding a minimum cost spanning
    546547tree in a graph.
    547548*/
    … …  
    552553\brief Auxiliary algorithms implemented in LEMON.
    553554
    554 This group describes some algorithms implemented in LEMON
     555This group contains some algorithms implemented in LEMON
    555556in order to make it easier to implement complex algorithms.
    556557*/
    … …  
    561562\brief Approximation algorithms.
    562563
    563 This group describes the approximation and heuristic algorithms
     564This group contains the approximation and heuristic algorithms
    564565implemented in LEMON.
    565566*/
    … …  
    567568/**
    568569@defgroup gen_opt_group General Optimization Tools
    569 \brief This group describes some general optimization frameworks
     570\brief This group contains some general optimization frameworks
    570571implemented in LEMON.
    571572
    572 This group describes some general optimization frameworks
     573This group contains some general optimization frameworks
    573574implemented in LEMON.
    574575*/
    … …  
    579580\brief Lp and Mip solver interfaces for LEMON.
    580581
    581 This group describes Lp and Mip solver interfaces for LEMON. The
     582This group contains Lp and Mip solver interfaces for LEMON. The
    582583various LP solvers could be used in the same manner with this
    583584interface.
    … …  
    598599\brief Metaheuristics for LEMON library.
    599600
    600 This group describes some metaheuristic optimization tools.
     601This group contains some metaheuristic optimization tools.
    601602*/
    602603
    … …  
    613614\brief Simple basic graph utilities.
    614615
    615 This group describes some simple basic graph utilities.
     616This group contains some simple basic graph utilities.
    616617*/
    617618
    … …  
    621622\brief Tools for development, debugging and testing.
    622623
    623 This group describes several useful tools for development,
     624This group contains several useful tools for development,
    624625debugging and testing.
    625626*/
    … …  
    630631\brief Simple tools for measuring the performance of algorithms.
    631632
    632 This group describes simple tools for measuring the performance
     633This group contains simple tools for measuring the performance
    633634of algorithms.
    634635*/
    … …  
    639640\brief Exceptions defined in LEMON.
    640641
    641 This group describes the exceptions defined in LEMON.
     642This group contains the exceptions defined in LEMON.
    642643*/
    643644
    … …  
    646647\brief Graph Input-Output methods
    647648
    648 This group describes the tools for importing and exporting graphs
     649This group contains the tools for importing and exporting graphs
    649650and graph related data. Now it supports the \ref lgf-format
    650651"LEMON Graph Format", the \c DIMACS format and the encapsulated
    … …  
    657658\brief Reading and writing LEMON Graph Format.
    658659
    659 This group describes methods for reading and writing
     660This group contains methods for reading and writing
    660661\ref lgf-format "LEMON Graph Format".
    661662*/
    … …  
    666667\brief General \c EPS drawer and graph exporter
    667668
    668 This group describes general \c EPS drawing methods and special
     669This group contains general \c EPS drawing methods and special
    669670graph exporting tools.
    670671*/
    … …  
    690691\brief Skeleton classes and concept checking classes
    691692
    692 This group describes the data/algorithm skeletons and concept checking
     693This group contains the data/algorithm skeletons and concept checking
    693694classes implemented in LEMON.
    694695
    … …  
    720721\brief Skeleton and concept checking classes for graph structures
    721722
    722 This group describes the skeletons and concept checking classes of LEMON's
     723This group contains the skeletons and concept checking classes of LEMON's
    723724graph structures and helper classes used to implement these.
    724725*/
    … …  
    729730\brief Skeleton and concept checking classes for maps
    730731
    731 This group describes the skeletons and concept checking classes of maps.
     732This group contains the skeletons and concept checking classes of maps.
    732733*/
    733734
    … …  
    740741the \c demo subdirectory of the source tree.
    741742
    742 It order to compile them, use <tt>--enable-demo</tt> configure option when
    743 build the library.
     743In order to compile them, use the <tt>make demo</tt> or the
     744<tt>make check</tt> commands.
    744745*/
    745746

  • 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/Makefile.am

    r601 r611  
    1313        lemon/lp_base.cc \
    1414        lemon/lp_skeleton.cc \
    15         lemon/random.cc \
     15        lemon/random.cc \
    1616        lemon/bits/windows.cc
    1717
    1818
    1919lemon_libemon_la_CXXFLAGS = \
     20        $(AM_CXXFLAGS) \
    2021        $(GLPK_CFLAGS) \
    2122        $(CPLEX_CFLAGS) \
    2223        $(SOPLEX_CXXFLAGS) \
    23         $(CLP_CXXFLAGS)
     24        $(CLP_CXXFLAGS) \
     25        $(CBC_CXXFLAGS)
    2426
    2527lemon_libemon_la_LDFLAGS = \
    … …  
    2729        $(CPLEX_LIBS) \
    2830        $(SOPLEX_LIBS) \
    29         $(CLP_LIBS)
     31        $(CLP_LIBS) \
     32        $(CBC_LIBS)
    3033
    3134if HAVE_GLPK
    … …  
    4346if HAVE_CLP
    4447lemon_libemon_la_SOURCES += lemon/clp.cc
     48endif
     49
     50if HAVE_CBC
     51lemon_libemon_la_SOURCES += lemon/cbc.cc
    4552endif
    4653
    … …  
    6976        lemon/full_graph.h \
    7077        lemon/glpk.h \
     78        lemon/gomory_hu.h \
    7179        lemon/graph_to_eps.h \
    7280        lemon/grid_graph.h \
    … …  
    8290        lemon/list_graph.h \
    8391        lemon/maps.h \
     92        lemon/matching.h \
    8493        lemon/math.h \
    85         lemon/max_matching.h \
    8694        lemon/min_cost_arborescence.h \
    8795        lemon/nauty_reader.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/circulation.h

    r610 r611  
    231231    ///@{
    232232
    233     template <typename _FlowMap>
     233    template <typename T>
    234234    struct SetFlowMapTraits : public Traits {
    235       typedef _FlowMap FlowMap;
     235      typedef T FlowMap;
    236236      static FlowMap *createFlowMap(const Digraph&) {
    237237        LEMON_ASSERT(false, "FlowMap is not initialized");
    … …  
    245245    /// \ref named-templ-param "Named parameter" for setting FlowMap
    246246    /// type.
    247     template <typename _FlowMap>
     247    template <typename T>
    248248    struct SetFlowMap
    249249      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    250                            SetFlowMapTraits<_FlowMap> > {
     250                           SetFlowMapTraits<T> > {
    251251      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    252                           SetFlowMapTraits<_FlowMap> > Create;
     252                          SetFlowMapTraits<T> > Create;
    253253    };
    254254
    255     template <typename _Elevator>
     255    template <typename T>
    256256    struct SetElevatorTraits : public Traits {
    257       typedef _Elevator Elevator;
     257      typedef T Elevator;
    258258      static Elevator *createElevator(const Digraph&, int) {
    259259        LEMON_ASSERT(false, "Elevator is not initialized");
    … …  
    271271    /// \ref run() or \ref init().
    272272    /// \sa SetStandardElevator
    273     template <typename _Elevator>
     273    template <typename T>
    274274    struct SetElevator
    275275      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    276                            SetElevatorTraits<_Elevator> > {
     276                           SetElevatorTraits<T> > {
    277277      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    278                           SetElevatorTraits<_Elevator> > Create;
     278                          SetElevatorTraits<T> > Create;
    279279    };
    280280
    281     template <typename _Elevator>
     281    template <typename T>
    282282    struct SetStandardElevatorTraits : public Traits {
    283       typedef _Elevator Elevator;
     283      typedef T Elevator;
    284284      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    285285        return new Elevator(digraph, max_level);
    … …  
    299299    /// before calling \ref run() or \ref init().
    300300    /// \sa SetElevator
    301     template <typename _Elevator>
     301    template <typename T>
    302302    struct SetStandardElevator
    303303      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    304                        SetStandardElevatorTraits<_Elevator> > {
     304                       SetStandardElevatorTraits<T> > {
    305305      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
    306                       SetStandardElevatorTraits<_Elevator> > Create;
     306                      SetStandardElevatorTraits<T> > Create;
    307307    };
    308308
    … …  
    471471
    472472      for(NodeIt n(_g);n!=INVALID;++n) {
    473         _excess->set(n, (*_supply)[n]);
     473        (*_excess)[n] = (*_supply)[n];
    474474      }
    475475
    476476      for (ArcIt e(_g);e!=INVALID;++e) {
    477477        _flow->set(e, (*_lo)[e]);
    478         _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
    479         _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
     478        (*_excess)[_g.target(e)] += (*_flow)[e];
     479        (*_excess)[_g.source(e)] -= (*_flow)[e];
    480480      }
    481481
    … …  
    500500
    501501      for(NodeIt n(_g);n!=INVALID;++n) {
    502         _excess->set(n, (*_supply)[n]);
     502        (*_excess)[n] = (*_supply)[n];
    503503      }
    504504
    … …  
    506506        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
    507507          _flow->set(e, (*_up)[e]);
    508           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
    509           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
     508          (*_excess)[_g.target(e)] += (*_up)[e];
     509          (*_excess)[_g.source(e)] -= (*_up)[e];
    510510        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
    511511          _flow->set(e, (*_lo)[e]);
    512           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
    513           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
     512          (*_excess)[_g.target(e)] += (*_lo)[e];
     513          (*_excess)[_g.source(e)] -= (*_lo)[e];
    514514        } else {
    515515          Flow fc = -(*_excess)[_g.target(e)];
    516516          _flow->set(e, fc);
    517           _excess->set(_g.target(e), 0);
    518           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
     517          (*_excess)[_g.target(e)] = 0;
     518          (*_excess)[_g.source(e)] -= fc;
    519519        }
    520520      }
    … …  
    555555            if(!_tol.less(fc, exc)) {
    556556              _flow->set(e, (*_flow)[e] + exc);
    557               _excess->set(v, (*_excess)[v] + exc);
     557              (*_excess)[v] += exc;
    558558              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    559559                _level->activate(v);
    560               _excess->set(act,0);
     560              (*_excess)[act] = 0;
    561561              _level->deactivate(act);
    562562              goto next_l;
    … …  
    564564            else {
    565565              _flow->set(e, (*_up)[e]);
    566               _excess->set(v, (*_excess)[v] + fc);
     566              (*_excess)[v] += fc;
    567567              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    568568                _level->activate(v);
    … …  
    579579            if(!_tol.less(fc, exc)) {
    580580              _flow->set(e, (*_flow)[e] - exc);
    581               _excess->set(v, (*_excess)[v] + exc);
     581              (*_excess)[v] += exc;
    582582              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    583583                _level->activate(v);
    584               _excess->set(act,0);
     584              (*_excess)[act] = 0;
    585585              _level->deactivate(act);
    586586              goto next_l;
    … …  
    588588            else {
    589589              _flow->set(e, (*_lo)[e]);
    590               _excess->set(v, (*_excess)[v] + fc);
     590              (*_excess)[v] += fc;
    591591              if(!_level->active(v) && _tol.positive((*_excess)[v]))
    592592                _level->activate(v);
    … …  
    597597        }
    598598
    599         _excess->set(act, exc);
     599        (*_excess)[act] = exc;
    600600        if(!_tol.positive(exc)) _level->deactivate(act);
    601601        else if(mlevel==_node_num) {
    … …  
    700700    ///
    701701    /// \note This function calls \ref barrier() for each node,
    702     /// so it runs in \f$O(n)\f$ time.
     702    /// so it runs in O(n) time.
    703703    ///
    704704    /// \pre Either \ref run() or \ref init() must be called before

  • 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    }

  • lemon/preflow.h

    r610 r611  
    3333  /// Default traits class of Preflow class.
    3434  /// \tparam GR Digraph type.
    35   /// \tparam CM Capacity map type.
    36   template <typename GR, typename CM>
     35  /// \tparam CAP Capacity map type.
     36  template <typename GR, typename CAP>
    3737  struct PreflowDefaultTraits {
    3838
    … …  
    4444    /// The type of the map that stores the arc capacities.
    4545    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    46     typedef CM CapacityMap;
     46    typedef CAP CapacityMap;
    4747
    4848    /// \brief The type of the flow values.
    … …  
    9595  ///
    9696  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// \e push-relabel algorithm producing a flow of maximum value in a
    98   /// digraph. The preflow algorithms are the fastest known maximum
     97  /// \e push-relabel algorithm producing a \ref max_flow
     98  /// "flow of maximum value" in a digraph.
     99  /// The preflow algorithms are the fastest known maximum
    99100  /// flow algorithms. The current implementation use a mixture of the
    100101  /// \e "highest label" and the \e "bound decrease" heuristics.
    … …  
    106107  ///
    107108  /// \tparam GR The type of the digraph the algorithm runs on.
    108   /// \tparam CM The type of the capacity map. The default map
     109  /// \tparam CAP The type of the capacity map. The default map
    109110  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    110111#ifdef DOXYGEN
    111   template <typename GR, typename CM, typename TR>
     112  template <typename GR, typename CAP, typename TR>
    112113#else
    113114  template <typename GR,
    114             typename CM = typename GR::template ArcMap<int>,
    115             typename TR = PreflowDefaultTraits<GR, CM> >
     115            typename CAP = typename GR::template ArcMap<int>,
     116            typename TR = PreflowDefaultTraits<GR, CAP> >
    116117#endif
    117118  class Preflow {
    … …  
    195196    ///@{
    196197
    197     template <typename _FlowMap>
     198    template <typename T>
    198199    struct SetFlowMapTraits : public Traits {
    199       typedef _FlowMap FlowMap;
     200      typedef T FlowMap;
    200201      static FlowMap *createFlowMap(const Digraph&) {
    201202        LEMON_ASSERT(false, "FlowMap is not initialized");
    … …  
    209210    /// \ref named-templ-param "Named parameter" for setting FlowMap
    210211    /// type.
    211     template <typename _FlowMap>
     212    template <typename T>
    212213    struct SetFlowMap
    213       : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
     214      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
    214215      typedef Preflow<Digraph, CapacityMap,
    215                       SetFlowMapTraits<_FlowMap> > Create;
     216                      SetFlowMapTraits<T> > Create;
    216217    };
    217218
    218     template <typename _Elevator>
     219    template <typename T>
    219220    struct SetElevatorTraits : public Traits {
    220       typedef _Elevator Elevator;
     221      typedef T Elevator;
    221222      static Elevator *createElevator(const Digraph&, int) {
    222223        LEMON_ASSERT(false, "Elevator is not initialized");
    … …  
    234235    /// \ref run() or \ref init().
    235236    /// \sa SetStandardElevator
    236     template <typename _Elevator>
     237    template <typename T>
    237238    struct SetElevator
    238       : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
     239      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
    239240      typedef Preflow<Digraph, CapacityMap,
    240                       SetElevatorTraits<_Elevator> > Create;
     241                      SetElevatorTraits<T> > Create;
    241242    };
    242243
    243     template <typename _Elevator>
     244    template <typename T>
    244245    struct SetStandardElevatorTraits : public Traits {
    245       typedef _Elevator Elevator;
     246      typedef T Elevator;
    246247      static Elevator *createElevator(const Digraph& digraph, int max_level) {
    247248        return new Elevator(digraph, max_level);
    … …  
    261262    /// before calling \ref run() or \ref init().
    262263    /// \sa SetElevator
    263     template <typename _Elevator>
     264    template <typename T>
    264265    struct SetStandardElevator
    265266      : public Preflow<Digraph, CapacityMap,
    266                        SetStandardElevatorTraits<_Elevator> > {
     267                       SetStandardElevatorTraits<T> > {
    267268      typedef Preflow<Digraph, CapacityMap,
    268                       SetStandardElevatorTraits<_Elevator> > Create;
     269                      SetStandardElevatorTraits<T> > Create;
    269270    };
    270271
    … …  
    404405      _phase = true;
    405406      for (NodeIt n(_graph); n != INVALID; ++n) {
    406         _excess->set(n, 0);
     407        (*_excess)[n] = 0;
    407408      }
    408409
    … …  
    417418
    418419      std::vector<Node> queue;
    419       reached.set(_source, true);
     420      reached[_source] = true;
    420421
    421422      queue.push_back(_target);
    422       reached.set(_target, true);
     423      reached[_target] = true;
    423424      while (!queue.empty()) {
    424425        _level->initNewLevel();
    … …  
    429430            Node u = _graph.source(e);
    430431            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
    431               reached.set(u, true);
     432              reached[u] = true;
    432433              _level->initAddItem(u);
    433434              nqueue.push_back(u);
    … …  
    444445          if ((*_level)[u] == _level->maxLevel()) continue;
    445446          _flow->set(e, (*_capacity)[e]);
    446           _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
     447          (*_excess)[u] += (*_capacity)[e];
    447448          if (u != _target && !_level->active(u)) {
    448449            _level->activate(u);
    … …  
    478479        }
    479480        if (excess < 0 && n != _source) return false;
    480         _excess->set(n, excess);
     481        (*_excess)[n] = excess;
    481482      }
    482483
    … …  
    487488
    488489      std::vector<Node> queue;
    489       reached.set(_source, true);
     490      reached[_source] = true;
    490491
    491492      queue.push_back(_target);
    492       reached.set(_target, true);
     493      reached[_target] = true;
    493494      while (!queue.empty()) {
    494495        _level->initNewLevel();
    … …  
    500501            if (!reached[u] &&
    501502                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    502               reached.set(u, true);
     503              reached[u] = true;
    503504              _level->initAddItem(u);
    504505              nqueue.push_back(u);
    … …  
    508509            Node v = _graph.target(e);
    509510            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    510               reached.set(v, true);
     511              reached[v] = true;
    511512              _level->initAddItem(v);
    512513              nqueue.push_back(v);
    … …  
    524525          if ((*_level)[u] == _level->maxLevel()) continue;
    525526          _flow->set(e, (*_capacity)[e]);
    526           _excess->set(u, (*_excess)[u] + rem);
     527          (*_excess)[u] += rem;
    527528          if (u != _target && !_level->active(u)) {
    528529            _level->activate(u);
    … …  
    536537          if ((*_level)[v] == _level->maxLevel()) continue;
    537538          _flow->set(e, 0);
    538           _excess->set(v, (*_excess)[v] + rem);
     539          (*_excess)[v] += rem;
    539540          if (v != _target && !_level->active(v)) {
    540541            _level->activate(v);
    … …  
    577578              if (!_tolerance.less(rem, excess)) {
    578579                _flow->set(e, (*_flow)[e] + excess);
    579                 _excess->set(v, (*_excess)[v] + excess);
     580                (*_excess)[v] += excess;
    580581                excess = 0;
    581582                goto no_more_push_1;
    582583              } else {
    583584                excess -= rem;
    584                 _excess->set(v, (*_excess)[v] + rem);
     585                (*_excess)[v] += rem;
    585586                _flow->set(e, (*_capacity)[e]);
    586587              }
    … …  
    600601              if (!_tolerance.less(rem, excess)) {
    601602                _flow->set(e, (*_flow)[e] - excess);
    602                 _excess->set(v, (*_excess)[v] + excess);
     603                (*_excess)[v] += excess;
    603604                excess = 0;
    604605                goto no_more_push_1;
    605606              } else {
    606607                excess -= rem;
    607                 _excess->set(v, (*_excess)[v] + rem);
     608                (*_excess)[v] += rem;
    608609                _flow->set(e, 0);
    609610              }
    … …  
    615616        no_more_push_1:
    616617
    617           _excess->set(n, excess);
     618          (*_excess)[n] = excess;
    618619
    619620          if (excess != 0) {
    … …  
    650651              if (!_tolerance.less(rem, excess)) {
    651652                _flow->set(e, (*_flow)[e] + excess);
    652                 _excess->set(v, (*_excess)[v] + excess);
     653                (*_excess)[v] += excess;
    653654                excess = 0;
    654655                goto no_more_push_2;
    655656              } else {
    656657                excess -= rem;
    657                 _excess->set(v, (*_excess)[v] + rem);
     658                (*_excess)[v] += rem;
    658659                _flow->set(e, (*_capacity)[e]);
    659660              }
    … …  
    673674              if (!_tolerance.less(rem, excess)) {
    674675                _flow->set(e, (*_flow)[e] - excess);
    675                 _excess->set(v, (*_excess)[v] + excess);
     676                (*_excess)[v] += excess;
    676677                excess = 0;
    677678                goto no_more_push_2;
    678679              } else {
    679680                excess -= rem;
    680                 _excess->set(v, (*_excess)[v] + rem);
     681                (*_excess)[v] += rem;
    681682                _flow->set(e, 0);
    682683              }
    … …  
    688689        no_more_push_2:
    689690
    690           _excess->set(n, excess);
     691          (*_excess)[n] = excess;
    691692
    692693          if (excess != 0) {
    … …  
    731732      typename Digraph::template NodeMap<bool> reached(_graph);
    732733      for (NodeIt n(_graph); n != INVALID; ++n) {
    733         reached.set(n, (*_level)[n] < _level->maxLevel());
     734        reached[n] = (*_level)[n] < _level->maxLevel();
    734735      }
    735736
    … …  
    739740      std::vector<Node> queue;
    740741      queue.push_back(_source);
    741       reached.set(_source, true);
     742      reached[_source] = true;
    742743
    743744      while (!queue.empty()) {
    … …  
    749750            Node v = _graph.target(e);
    750751            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    751               reached.set(v, true);
     752              reached[v] = true;
    752753              _level->initAddItem(v);
    753754              nqueue.push_back(v);
    … …  
    758759            if (!reached[u] &&
    759760                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    760               reached.set(u, true);
     761              reached[u] = true;
    761762              _level->initAddItem(u);
    762763              nqueue.push_back(u);
    … …  
    792793            if (!_tolerance.less(rem, excess)) {
    793794              _flow->set(e, (*_flow)[e] + excess);
    794               _excess->set(v, (*_excess)[v] + excess);
     795              (*_excess)[v] += excess;
    795796              excess = 0;
    796797              goto no_more_push;
    797798            } else {
    798799              excess -= rem;
    799               _excess->set(v, (*_excess)[v] + rem);
     800              (*_excess)[v] += rem;
    800801              _flow->set(e, (*_capacity)[e]);
    801802            }
    … …  
    815816            if (!_tolerance.less(rem, excess)) {
    816817              _flow->set(e, (*_flow)[e] - excess);
    817               _excess->set(v, (*_excess)[v] + excess);
     818              (*_excess)[v] += excess;
    818819              excess = 0;
    819820              goto no_more_push;
    820821            } else {
    821822              excess -= rem;
    822               _excess->set(v, (*_excess)[v] + rem);
     823              (*_excess)[v] += rem;
    823824              _flow->set(e, 0);
    824825            }
    … …  
    830831      no_more_push:
    831832
    832         _excess->set(n, excess);
     833        (*_excess)[n] = excess;
    833834
    834835        if (excess != 0) {
    … …  
    947948    ///
    948949    /// \note This function calls \ref minCut() for each node, so it runs in
    949     /// \f$O(n)\f$ time.
     950    /// O(n) time.
    950951    ///
    951952    /// \pre Either \ref run() or \ref init() must be called before

  • 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/CMakeLists.txt

    r601 r611  
    11INCLUDE_DIRECTORIES(
    2   ${CMAKE_SOURCE_DIR}
    3   ${CMAKE_BINARY_DIR}
     2  ${PROJECT_SOURCE_DIR}
     3  ${PROJECT_BINARY_DIR}
    44)
    55
    … …  
    88ENDIF(HAVE_GLPK)
    99
    10 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
     10LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
    1111
    1212SET(TESTS
    … …  
    2222  error_test
    2323  euler_test
     24  gomory_hu_test
    2425  graph_copy_test
    2526  graph_test
    … …  
    2930  kruskal_test
    3031  maps_test
    31   max_matching_test
     32  matching_test
    3233  min_cost_arborescence_test
    3334  min_cost_flow_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/Makefile.am

    r601 r611  
    1818        test/error_test \
    1919        test/euler_test \
     20        test/gomory_hu_test \
    2021        test/graph_copy_test \
    2122        test/graph_test \
    … …  
    2526        test/kruskal_test \
    2627        test/maps_test \
    27         test/max_matching_test \
     28        test/matching_test \
    2829        test/min_cost_arborescence_test \
    2930        test/min_cost_flow_test \
    … …  
    3738        test/time_measure_test \
    3839        test/unionfind_test
     40
     41test_test_tools_pass_DEPENDENCIES = demo
    3942
    4043if HAVE_LP
    … …  
    5962test_error_test_SOURCES = test/error_test.cc
    6063test_euler_test_SOURCES = test/euler_test.cc
     64test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
    6165test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    6266test_graph_test_SOURCES = test/graph_test.cc
    … …  
    6872test_maps_test_SOURCES = test/maps_test.cc
    6973test_mip_test_SOURCES = test/mip_test.cc
    70 test_max_matching_test_SOURCES = test/max_matching_test.cc
     74test_matching_test_SOURCES = test/matching_test.cc
    7175test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    7276test_min_cost_flow_test_SOURCES = test/min_cost_flow_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

  • test/circulation_test.cc

    r610 r611  
    7272  FlowMap flow;
    7373  BarrierMap bar;
     74  VType v;
     75  bool b;
    7476
    75   Circulation<Digraph, CapMap, CapMap, SupplyMap>
    76     ::SetFlowMap<FlowMap>
    77     ::SetElevator<Elev>
    78     ::SetStandardElevator<LinkedElev>
    79     ::Create circ_test(g,lcap,ucap,supply);
    80 
    81   circ_test.lowerMap(lcap);
    82   circ_test.upperMap(ucap);
    83   circ_test.supplyMap(supply);
    84   flow = circ_test.flowMap();
    85   circ_test.flowMap(flow);
     77  typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>
     78            ::SetFlowMap<FlowMap>
     79            ::SetElevator<Elev>
     80            ::SetStandardElevator<LinkedElev>
     81            ::Create CirculationType;
     82  CirculationType circ_test(g, lcap, ucap, supply);
     83  const CirculationType& const_circ_test = circ_test;
     84   
     85  circ_test
     86    .lowerMap(lcap)
     87    .upperMap(ucap)
     88    .supplyMap(supply)
     89    .flowMap(flow);
    8690
    8791  circ_test.init();
    … …  
    9094  circ_test.run();
    9195
    92   circ_test.barrier(n);
    93   circ_test.barrierMap(bar);
    94   circ_test.flow(a);
     96  v = const_circ_test.flow(a);
     97  const FlowMap& fm = const_circ_test.flowMap();
     98  b = const_circ_test.barrier(n);
     99  const_circ_test.barrierMap(bar);
     100 
     101  ignore_unused_variable_warning(fm);
    95102}
    96103

  • 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:

  • tools/dimacs-solver.cc

    r605 r611  
    2424///
    2525/// See
    26 /// \verbatim
    27 ///  dimacs-solver --help
    28 /// \endverbatim
     26/// \code
     27///   dimacs-solver --help
     28/// \endcode
    2929/// for more info on usage.
    30 ///
    3130
    3231#include <iostream>
    … …  
    4443#include <lemon/dijkstra.h>
    4544#include <lemon/preflow.h>
    46 #include <lemon/max_matching.h>
     45#include <lemon/matching.h>
    4746#include <lemon/network_simplex.h>
    4847
    … …  
    7473template<class Value>
    7574void solve_max(ArgParser &ap, std::istream &is, std::ostream &,
    76               DimacsDescriptor &desc)
     75               Value infty, DimacsDescriptor &desc)
    7776{
    7877  bool report = !ap.given("q");
    … …  
    8281  Timer ti;
    8382  ti.restart();
    84   readDimacsMax(is, g, cap, s, t, desc);
     83  readDimacsMax(is, g, cap, s, t, infty, desc);
    8584  if(report) std::cerr << "Read the file: " << ti << '\n';
    8685  ti.restart();
    … …  
    103102  Timer ti;
    104103  ti.restart();
    105   readDimacsMin(is, g, lower, cap, cost, sup, desc);
     104  readDimacsMin(is, g, lower, cap, cost, sup, 0, desc);
    106105  if (report) std::cerr << "Read the file: " << ti << '\n';
    107106  ti.restart();
    … …  
    139138           DimacsDescriptor &desc)
    140139{
     140  std::stringstream iss(static_cast<std::string>(ap["infcap"]));
     141  Value infty;
     142  iss >> infty;
     143  if(iss.fail())
     144    {
     145      std::cerr << "Cannot interpret '"
     146                << static_cast<std::string>(ap["infcap"]) << "' as infinite"
     147                << std::endl;
     148      exit(1);
     149    }
     150 
    141151  switch(desc.type)
    142152    {
    … …  
    145155      break;
    146156    case DimacsDescriptor::MAX:
    147       solve_max<Value>(ap,is,os,desc);
     157      solve_max<Value>(ap,is,os,infty,desc);
    148158      break;
    149159    case DimacsDescriptor::SP:
    … …  
    182192    .optionGroup("datatype","ldouble")
    183193    .onlyOneGroup("datatype")
     194    .stringOption("infcap","Value used for 'very high' capacities","0")
    184195    .run();
    185196
Note: See TracChangeset for help on using the changeset viewer.