COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r710 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    247239any kind of path structure.
    248240
    249 \sa lemon::concepts::Path
     241\sa \ref concepts::Path "Path concept"
     242*/
     243
     244/**
     245@defgroup heaps Heap Structures
     246@ingroup datas
     247\brief %Heap structures implemented in LEMON.
     248
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
     263*/
     264
     265/**
     266@defgroup matrices Matrices
     267@ingroup datas
     268\brief Two dimensional data storages implemented in LEMON.
     269
     270This group contains two dimensional data storages implemented in LEMON.
    250271*/
    251272
     
    260281
    261282/**
     283@defgroup geomdat Geometric Data Structures
     284@ingroup auxdat
     285\brief Geometric data structures implemented in LEMON.
     286
     287This group contains geometric data structures implemented in LEMON.
     288
     289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     290   vector with the usual operations.
     291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     292   rectangular bounding box of a set of \ref lemon::dim2::Point
     293   "dim2::Point"'s.
     294*/
     295
     296/**
     297@defgroup matrices Matrices
     298@ingroup auxdat
     299\brief Two dimensional data storages implemented in LEMON.
     300
     301This group contains two dimensional data storages implemented in LEMON.
     302*/
     303
     304/**
    262305@defgroup algs Algorithms
    263306\brief This group contains the several algorithms
     
    274317
    275318This group contains the common graph search algorithms, namely
    276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\ref clrs01algorithms.
    277321*/
    278322
     
    282326\brief Algorithms for finding shortest paths.
    283327
    284 This group contains the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
    285330
    286331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    299344
    300345/**
     346@defgroup spantree Minimum Spanning Tree Algorithms
     347@ingroup algs
     348\brief Algorithms for finding minimum cost spanning trees and arborescences.
     349
     350This group contains the algorithms for finding minimum cost spanning
     351trees and arborescences \ref clrs01algorithms.
     352*/
     353
     354/**
    301355@defgroup max_flow Maximum Flow Algorithms
    302356@ingroup algs
     
    304358
    305359This group contains the algorithms for finding maximum flows and
    306 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    307361
    308362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    319373
    320374LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
     375- \ref EdmondsKarp Edmonds-Karp algorithm
     376  \ref edmondskarp72theoretical.
     377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     378  \ref goldberg88newapproach.
     379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     380  \ref dinic70algorithm, \ref sleator83dynamic.
     381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     382  \ref goldberg88newapproach, \ref sleator83dynamic.
     383
     384In most cases the \ref Preflow algorithm provides the
    327385fastest method for computing a maximum flow. All implementations
    328386also provide functions to query the minimum cut, which is the dual
    329387problem of maximum flow.
    330388
    331 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     389\ref Circulation is a preflow push-relabel algorithm implemented directly
    332390for finding feasible circulations, which is a somewhat different problem,
    333391but it is strongly related to maximum flow.
     
    342400
    343401This group contains the algorithms for finding minimum cost flows and
    344 circulations. For more information about this problem and its dual
    345 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
    346405
    347406LEMON contains several algorithms for this problem.
    348407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     410   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
     412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     413   shortest path method \ref edmondskarp72theoretical.
     414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     415   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    356416
    357417In general NetworkSimplex is the most efficient implementation,
     
    376436
    377437\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    378     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     438    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379439
    380440LEMON contains several algorithms related to minimum cut problems:
     
    392452
    393453/**
    394 @defgroup graph_properties Connectivity and Other Graph Properties
    395 @ingroup algs
    396 \brief Algorithms for discovering the graph properties
    397 
    398 This group contains the algorithms for discovering the graph properties
    399 like connectivity, bipartiteness, euler property, simplicity etc.
    400 
    401 \image html edge_biconnected_components.png
    402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    403 */
    404 
    405 /**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
     454@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     455@ingroup algs
     456\brief Algorithms for finding minimum mean cycles.
     457
     458This group contains the algorithms for finding minimum mean cycles
     459\ref clrs01algorithms, \ref amo93networkflows.
     460
     461The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     462of minimum mean length (cost) in a digraph.
     463The mean length of a cycle is the average length of its arcs, i.e. the
     464ratio between the total length of the cycle and the number of arcs on it.
     465
     466This problem has an important connection to \e conservative \e length
     467\e functions, too. A length function on the arcs of a digraph is called
     468conservative if and only if there is no directed cycle of negative total
     469length. For an arbitrary length function, the negative of the minimum
     470cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     471arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     472function.
     473
     474LEMON contains three algorithms for solving the minimum mean cycle problem:
     475- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     476  \ref dasdan98minmeancycle.
     477- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     478  version of Karp's algorithm \ref dasdan98minmeancycle.
     479- \ref Howard "Howard"'s policy iteration algorithm
     480  \ref dasdan98minmeancycle.
     481
     482In practice, the Howard algorithm proved to be by far the most efficient
     483one, though the best known theoretical bound on its running time is
     484exponential.
     485Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     486O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     487applied early termination scheme.
    415488*/
    416489
     
    450523  Edmond's blossom shrinking algorithm for calculating maximum weighted
    451524  perfect matching in general graphs.
    452 
    453 \image html bipartite_matching.png
    454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    455 */
    456 
    457 /**
    458 @defgroup spantree Minimum Spanning Tree Algorithms
    459 @ingroup algs
    460 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    461 
    462 This group contains the algorithms for finding minimum cost spanning
    463 trees and arborescences.
     525- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     526  maximum cardinality fractional matching in general graphs.
     527- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     528  maximum weighted fractional matching in general graphs.
     529- \ref MaxWeightedPerfectFractionalMatching
     530  Augmenting path algorithm for calculating maximum weighted
     531  perfect fractional matching in general graphs.
     532
     533\image html matching.png
     534\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     535*/
     536
     537/**
     538@defgroup graph_properties Connectivity and Other Graph Properties
     539@ingroup algs
     540\brief Algorithms for discovering the graph properties
     541
     542This group contains the algorithms for discovering the graph properties
     543like connectivity, bipartiteness, euler property, simplicity etc.
     544
     545\image html connected_components.png
     546\image latex connected_components.eps "Connected components" width=\textwidth
     547*/
     548
     549/**
     550@defgroup planar Planarity Embedding and Drawing
     551@ingroup algs
     552\brief Algorithms for planarity checking, embedding and drawing
     553
     554This group contains the algorithms for planarity checking,
     555embedding and drawing.
     556
     557\image html planar.png
     558\image latex planar.eps "Plane graph" width=\textwidth
     559*/
     560
     561/**
     562@defgroup approx Approximation Algorithms
     563@ingroup algs
     564\brief Approximation algorithms.
     565
     566This group contains the approximation and heuristic algorithms
     567implemented in LEMON.
    464568*/
    465569
     
    471575This group contains some algorithms implemented in LEMON
    472576in order to make it easier to implement complex algorithms.
    473 */
    474 
    475 /**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482577*/
    483578
     
    492587
    493588/**
    494 @defgroup lp_group Lp and Mip Solvers
     589@defgroup lp_group LP and MIP Solvers
    495590@ingroup gen_opt_group
    496 \brief Lp and Mip solver interfaces for LEMON.
    497 
    498 This group contains Lp and Mip solver interfaces for LEMON. The
    499 various LP solvers could be used in the same manner with this
    500 interface.
     591\brief LP and MIP solver interfaces for LEMON.
     592
     593This group contains LP and MIP solver interfaces for LEMON.
     594Various LP solvers could be used in the same manner with this
     595high-level interface.
     596
     597The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     598\ref cplex, \ref soplex.
    501599*/
    502600
     
    588686
    589687/**
    590 @defgroup dimacs_group DIMACS format
     688@defgroup dimacs_group DIMACS Format
    591689@ingroup io_group
    592690\brief Read and write files in DIMACS format
     
    637735\brief Skeleton and concept checking classes for graph structures
    638736
    639 This group contains the skeletons and concept checking classes of LEMON's
    640 graph structures and helper classes used to implement these.
     737This group contains the skeletons and concept checking classes of
     738graph structures.
    641739*/
    642740
     
    650748
    651749/**
     750@defgroup tools Standalone Utility Applications
     751
     752Some utility applications are listed here.
     753
     754The standard compilation procedure (<tt>./configure;make</tt>) will compile
     755them, as well.
     756*/
     757
     758/**
    652759\anchor demoprograms
    653760
     
    661768*/
    662769
    663 /**
    664 @defgroup tools Standalone Utility Applications
    665 
    666 Some utility applications are listed here.
    667 
    668 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    669 them, as well.
    670 */
    671 
    672770}
Note: See TracChangeset for help on using the changeset viewer.