COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r710 r1023  
    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"
    250263*/
    251264
     
    260273
    261274/**
     275@defgroup geomdat Geometric Data Structures
     276@ingroup auxdat
     277\brief Geometric data structures implemented in LEMON.
     278
     279This group contains geometric data structures implemented in LEMON.
     280
     281 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     282   vector with the usual operations.
     283 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     284   rectangular bounding box of a set of \ref lemon::dim2::Point
     285   "dim2::Point"'s.
     286*/
     287
     288/**
     289@defgroup matrices Matrices
     290@ingroup auxdat
     291\brief Two dimensional data storages implemented in LEMON.
     292
     293This group contains two dimensional data storages implemented in LEMON.
     294*/
     295
     296/**
    262297@defgroup algs Algorithms
    263298\brief This group contains the several algorithms
     
    274309
    275310This group contains the common graph search algorithms, namely
    276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     311\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     312\ref clrs01algorithms.
    277313*/
    278314
     
    282318\brief Algorithms for finding shortest paths.
    283319
    284 This group contains the algorithms for finding shortest paths in digraphs.
     320This group contains the algorithms for finding shortest paths in digraphs
     321\ref clrs01algorithms.
    285322
    286323 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    299336
    300337/**
     338@defgroup spantree Minimum Spanning Tree Algorithms
     339@ingroup algs
     340\brief Algorithms for finding minimum cost spanning trees and arborescences.
     341
     342This group contains the algorithms for finding minimum cost spanning
     343trees and arborescences \ref clrs01algorithms.
     344*/
     345
     346/**
    301347@defgroup max_flow Maximum Flow Algorithms
    302348@ingroup algs
     
    304350
    305351This group contains the algorithms for finding maximum flows and
    306 feasible circulations.
     352feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    307353
    308354The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    319365
    320366LEMON 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
     367- \ref EdmondsKarp Edmonds-Karp algorithm
     368  \ref edmondskarp72theoretical.
     369- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     370  \ref goldberg88newapproach.
     371- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     372  \ref dinic70algorithm, \ref sleator83dynamic.
     373- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     374  \ref goldberg88newapproach, \ref sleator83dynamic.
     375
     376In most cases the \ref Preflow algorithm provides the
    327377fastest method for computing a maximum flow. All implementations
    328378also provide functions to query the minimum cut, which is the dual
    329379problem of maximum flow.
    330380
    331 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     381\ref Circulation is a preflow push-relabel algorithm implemented directly
    332382for finding feasible circulations, which is a somewhat different problem,
    333383but it is strongly related to maximum flow.
     
    342392
    343393This 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".
     394circulations \ref amo93networkflows. For more information about this
     395problem and its dual solution, see \ref min_cost_flow
     396"Minimum Cost Flow Problem".
    346397
    347398LEMON contains several algorithms for this problem.
    348399 - \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.
    356 
    357 In general NetworkSimplex is the most efficient implementation,
    358 but in special cases other algorithms could be faster.
     400   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     401 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     402   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     403   \ref bunnagel98efficient.
     404 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     405   shortest path method \ref edmondskarp72theoretical.
     406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     408
     409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     410implementations, but the other two algorithms could be faster in special cases.
    359411For example, if the total supply and/or capacities are rather small,
    360 CapacityScaling is usually the fastest algorithm (without effective scaling).
     412\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
    361413*/
    362414
     
    376428
    377429\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]
     430    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379431
    380432LEMON contains several algorithms related to minimum cut problems:
     
    392444
    393445/**
    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
     446@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     447@ingroup algs
     448\brief Algorithms for finding minimum mean cycles.
     449
     450This group contains the algorithms for finding minimum mean cycles
     451\ref clrs01algorithms, \ref amo93networkflows.
     452
     453The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     454of minimum mean length (cost) in a digraph.
     455The mean length of a cycle is the average length of its arcs, i.e. the
     456ratio between the total length of the cycle and the number of arcs on it.
     457
     458This problem has an important connection to \e conservative \e length
     459\e functions, too. A length function on the arcs of a digraph is called
     460conservative if and only if there is no directed cycle of negative total
     461length. For an arbitrary length function, the negative of the minimum
     462cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     463arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     464function.
     465
     466LEMON contains three algorithms for solving the minimum mean cycle problem:
     467- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
     468  \ref dasdan98minmeancycle.
     469- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
     470  version of Karp's algorithm \ref dasdan98minmeancycle.
     471- \ref HowardMmc Howard's policy iteration algorithm
     472  \ref dasdan98minmeancycle.
     473
     474In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     475most efficient one, though the best known theoretical bound on its running
     476time is exponential.
     477Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     478run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     479typically faster due to the applied early termination scheme.
    415480*/
    416481
     
    450515  Edmond's blossom shrinking algorithm for calculating maximum weighted
    451516  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.
     517- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     518  maximum cardinality fractional matching in general graphs.
     519- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     520  maximum weighted fractional matching in general graphs.
     521- \ref MaxWeightedPerfectFractionalMatching
     522  Augmenting path algorithm for calculating maximum weighted
     523  perfect fractional matching in general graphs.
     524
     525\image html matching.png
     526\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     527*/
     528
     529/**
     530@defgroup graph_properties Connectivity and Other Graph Properties
     531@ingroup algs
     532\brief Algorithms for discovering the graph properties
     533
     534This group contains the algorithms for discovering the graph properties
     535like connectivity, bipartiteness, euler property, simplicity etc.
     536
     537\image html connected_components.png
     538\image latex connected_components.eps "Connected components" width=\textwidth
     539*/
     540
     541/**
     542@defgroup planar Planar Embedding and Drawing
     543@ingroup algs
     544\brief Algorithms for planarity checking, embedding and drawing
     545
     546This group contains the algorithms for planarity checking,
     547embedding and drawing.
     548
     549\image html planar.png
     550\image latex planar.eps "Plane graph" width=\textwidth
     551*/
     552
     553/**
     554@defgroup approx_algs Approximation Algorithms
     555@ingroup algs
     556\brief Approximation algorithms.
     557
     558This group contains the approximation and heuristic algorithms
     559implemented in LEMON.
     560
     561<b>Maximum Clique Problem</b>
     562  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
     563    Grosso, Locatelli, and Pullan.
    464564*/
    465565
     
    471571This group contains some algorithms implemented in LEMON
    472572in 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.
    482573*/
    483574
     
    492583
    493584/**
    494 @defgroup lp_group Lp and Mip Solvers
     585@defgroup lp_group LP and MIP Solvers
    495586@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.
     587\brief LP and MIP solver interfaces for LEMON.
     588
     589This group contains LP and MIP solver interfaces for LEMON.
     590Various LP solvers could be used in the same manner with this
     591high-level interface.
     592
     593The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     594\ref cplex, \ref soplex.
    501595*/
    502596
     
    588682
    589683/**
    590 @defgroup dimacs_group DIMACS format
     684@defgroup dimacs_group DIMACS Format
    591685@ingroup io_group
    592686\brief Read and write files in DIMACS format
     
    637731\brief Skeleton and concept checking classes for graph structures
    638732
    639 This group contains the skeletons and concept checking classes of LEMON's
    640 graph structures and helper classes used to implement these.
     733This group contains the skeletons and concept checking classes of
     734graph structures.
    641735*/
    642736
     
    650744
    651745/**
     746@defgroup tools Standalone Utility Applications
     747
     748Some utility applications are listed here.
     749
     750The standard compilation procedure (<tt>./configure;make</tt>) will compile
     751them, as well.
     752*/
     753
     754/**
    652755\anchor demoprograms
    653756
     
    661764*/
    662765
    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 
    672766}
Note: See TracChangeset for help on using the changeset viewer.