COIN-OR::LEMON - Graph Library

Changeset 422:a578265aa8a6 in lemon


Ignore:
Timestamp:
11/30/08 21:53:24 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements in groups.dox (#188)

  • Unify the notations used for formulas.
  • Add 'namespace lemon {...}' to simplify the references.
  • Improved doc for algorithm groups.
  • Extend the doc of the "shortest path" and "minimum cost flow" modules.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r403 r422  
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
     
    8991
    9092This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     93values to the nodes and arcs/edges of graphs.
     94
     95If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     96\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    9297*/
    9398
     
    100105maps from other maps.
    101106
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     107Most of them are \ref concepts::ReadMap "read-only maps".
    103108They can make arithmetic and logical operations between one or two maps
    104109(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    202207\brief Common graph search algorithms.
    203208
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     209This group describes the common graph search algorithms, namely
     210\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206211*/
    207212
     
    211216\brief Algorithms for finding shortest paths.
    212217
    213 This group describes the algorithms for finding shortest paths in graphs.
     218This group describes the algorithms for finding shortest paths in digraphs.
     219
     220 - \ref Dijkstra algorithm for finding shortest paths from a source node
     221   when all arc lengths are non-negative.
     222 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     223   from a source node when arc lenghts can be either positive or negative,
     224   but the digraph should not contain directed cycles with negative total
     225   length.
     226 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     227   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     228   lenghts can be either positive or negative, but the digraph should
     229   not contain directed cycles with negative total length.
     230 - \ref Suurballe A successive shortest path algorithm for finding
     231   arc-disjoint paths between two nodes having minimum total length.
    214232*/
    215233
     
    222240feasible circulations.
    223241
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     242The \e maximum \e flow \e problem is to find a flow of maximum value between
     243a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     244digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     245\f$s, t \in V\f$ source and target nodes.
     246A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
     247following optimization problem.
     248
     249\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
     250\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
     251    \qquad \forall v\in V\setminus\{s,t\} \f]
     252\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
    234253
    235254LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
     255- \ref EdmondsKarp Edmonds-Karp algorithm.
     256- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     257- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     258- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     259
     260In most cases the \ref Preflow "Preflow" algorithm provides the
     261fastest method for computing a maximum flow. All implementations
     262provides functions to also query the minimum cut, which is the dual
     263problem of the maximum flow.
    245264*/
    246265
     
    253272This group describes the algorithms for finding minimum cost flows and
    254273circulations.
     274
     275The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     276minimum total cost from a set of supply nodes to a set of demand nodes
     277in a network with capacity constraints and arc costs.
     278Formally, let \f$G=(V,A)\f$ be a digraph,
     279\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     280upper bounds for the flow values on the arcs,
     281\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     282on the arcs, and
     283\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
     284of the nodes.
     285A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
     286the following optimization problem.
     287
     288\f[ \min\sum_{a\in A} f(a) cost(a) \f]
     289\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
     290    supply(v) \qquad \forall v\in V \f]
     291\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
     292
     293LEMON contains several algorithms for solving minimum cost flow problems:
     294 - \ref CycleCanceling Cycle-canceling algorithms.
     295 - \ref CapacityScaling Successive shortest path algorithm with optional
     296   capacity scaling.
     297 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
     298   cost scaling.
     299 - \ref NetworkSimplex Primal network simplex algorithm with various
     300   pivot strategies.
    255301*/
    256302
     
    263309This group describes the algorithms for finding minimum cut in graphs.
    264310
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     311The \e minimum \e cut \e problem is to find a non-empty and non-complete
     312\f$X\f$ subset of the nodes with minimum overall capacity on
     313outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     314\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269315cut is the \f$X\f$ solution of the next optimization problem:
    270316
    271317\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     318    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273319
    274320LEMON contains several algorithms related to minimum cut problems:
    275321
    276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    277   in directed graphs
    278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    279   calculate minimum cut in undirected graphs
    280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    281   pairs minimum cut in undirected graphs
     322- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     323  in directed graphs.
     324- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     325  calculating minimum cut in undirected graphs.
     326- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
     327  all-pairs minimum cut in undirected graphs.
    282328
    283329If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
     330see the \ref max_flow "maximum flow problem".
    285331*/
    286332
     
    321367graphs.  The matching problems in bipartite graphs are generally
    322368easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     369can be finding maximum cardinality, maximum weight or minimum cost
    324370matching. The search can be constrained to find perfect or
    325371maximum cardinality matching.
    326372
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
     373The matching algorithms implemented in LEMON:
     374- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     375  for calculating maximum cardinality matching in bipartite graphs.
     376- \ref PrBipartiteMatching Push-relabel algorithm
     377  for calculating maximum cardinality matching in bipartite graphs.
     378- \ref MaxWeightedBipartiteMatching
     379  Successive shortest path algorithm for calculating maximum weighted
     380  matching and maximum weighted bipartite matching in bipartite graphs.
     381- \ref MinCostMaxBipartiteMatching
     382  Successive shortest path algorithm for calculating minimum cost maximum
     383  matching in bipartite graphs.
     384- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     385  maximum cardinality matching in general graphs.
     386- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     387  maximum weighted matching in general graphs.
     388- \ref MaxWeightedPerfectMatching
     389  Edmond's blossom shrinking algorithm for calculating maximum weighted
     390  perfect matching in general graphs.
    347391
    348392\image html bipartite_matching.png
     
    356400
    357401This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     402tree in a graph.
    359403*/
    360404
     
    547591\anchor demoprograms
    548592
    549 @defgroup demos Demo programs
     593@defgroup demos Demo Programs
    550594
    551595Some demo programs are listed here. Their full source codes can be found in
     
    557601
    558602/**
    559 @defgroup tools Standalone utility applications
     603@defgroup tools Standalone Utility Applications
    560604
    561605Some utility applications are listed here.
     
    565609*/
    566610
     611}
Note: See TracChangeset for help on using the changeset viewer.