COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r817 r815  
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
     
    239247any kind of path structure.
    240248
    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 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used 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 
    270 This group contains two dimensional data storages implemented in LEMON.
     249\sa lemon::concepts::Path
    271250*/
    272251
     
    281260
    282261/**
    283 @defgroup geomdat Geometric Data Structures
    284 @ingroup auxdat
    285 \brief Geometric data structures implemented in LEMON.
    286 
    287 This 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 
    301 This group contains two dimensional data storages implemented in LEMON.
    302 */
    303 
    304 /**
    305262@defgroup algs Algorithms
    306263\brief This group contains the several algorithms
     
    317274
    318275This group contains the common graph search algorithms, namely
    319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    320 \ref clrs01algorithms.
     276\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    321277*/
    322278
     
    326282\brief Algorithms for finding shortest paths.
    327283
    328 This group contains the algorithms for finding shortest paths in digraphs
    329 \ref clrs01algorithms.
     284This group contains the algorithms for finding shortest paths in digraphs.
    330285
    331286 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    344299
    345300/**
    346 @defgroup spantree Minimum Spanning Tree Algorithms
    347 @ingroup algs
    348 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    349 
    350 This group contains the algorithms for finding minimum cost spanning
    351 trees and arborescences \ref clrs01algorithms.
    352 */
    353 
    354 /**
    355301@defgroup max_flow Maximum Flow Algorithms
    356302@ingroup algs
     
    358304
    359305This group contains the algorithms for finding maximum flows and
    360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     306feasible circulations.
    361307
    362308The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    373319
    374320LEMON contains several algorithms for solving maximum flow problems:
    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 
    384 In most cases the \ref Preflow algorithm provides the
     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
     326In most cases the \ref Preflow "Preflow" algorithm provides the
    385327fastest method for computing a maximum flow. All implementations
    386328also provide functions to query the minimum cut, which is the dual
     
    400342
    401343This group contains the algorithms for finding minimum cost flows and
    402 circulations \ref amo93networkflows. For more information about this
    403 problem and its dual solution, see \ref min_cost_flow
    404 "Minimum Cost Flow Problem".
     344circulations. For more information about this problem and its dual
     345solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    405346
    406347LEMON contains several algorithms for this problem.
    407348 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     349   pivot strategies.
    409350 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
    411    \ref bunnagel98efficient.
     351   cost scaling.
    412352 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    413    capacity scaling \ref edmondskarp72theoretical.
    414  - \ref CancelAndTighten The Cancel and Tighten algorithm
    415    \ref goldberg89cyclecanceling.
    416  - \ref CycleCanceling Cycle-Canceling algorithms
    417    \ref klein67primal, \ref goldberg89cyclecanceling.
     353   capacity scaling.
     354 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     355 - \ref CycleCanceling Cycle-Canceling algorithms.
    418356
    419357In general NetworkSimplex is the most efficient implementation,
     
    438376
    439377\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    440     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
     378    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    441379
    442380LEMON contains several algorithms related to minimum cut problems:
     
    485423O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    486424applied early termination scheme.
     425*/
     426
     427/**
     428@defgroup graph_properties Connectivity and Other Graph Properties
     429@ingroup algs
     430\brief Algorithms for discovering the graph properties
     431
     432This group contains the algorithms for discovering the graph properties
     433like connectivity, bipartiteness, euler property, simplicity etc.
     434
     435\image html edge_biconnected_components.png
     436\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     437*/
     438
     439/**
     440@defgroup planar Planarity Embedding and Drawing
     441@ingroup algs
     442\brief Algorithms for planarity checking, embedding and drawing
     443
     444This group contains the algorithms for planarity checking,
     445embedding and drawing.
     446
     447\image html planar.png
     448\image latex planar.eps "Plane graph" width=\textwidth
    487449*/
    488450
     
    528490
    529491/**
    530 @defgroup graph_properties Connectivity and Other Graph Properties
    531 @ingroup algs
    532 \brief Algorithms for discovering the graph properties
    533 
    534 This group contains the algorithms for discovering the graph properties
    535 like 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 Planarity Embedding and Drawing
    543 @ingroup algs
    544 \brief Algorithms for planarity checking, embedding and drawing
    545 
    546 This group contains the algorithms for planarity checking,
    547 embedding and drawing.
    548 
    549 \image html planar.png
    550 \image latex planar.eps "Plane graph" width=\textwidth
     492@defgroup spantree Minimum Spanning Tree Algorithms
     493@ingroup algs
     494\brief Algorithms for finding minimum cost spanning trees and arborescences.
     495
     496This group contains the algorithms for finding minimum cost spanning
     497trees and arborescences.
     498*/
     499
     500/**
     501@defgroup auxalg Auxiliary Algorithms
     502@ingroup algs
     503\brief Auxiliary algorithms implemented in LEMON.
     504
     505This group contains some algorithms implemented in LEMON
     506in order to make it easier to implement complex algorithms.
    551507*/
    552508
     
    558514This group contains the approximation and heuristic algorithms
    559515implemented in LEMON.
    560 */
    561 
    562 /**
    563 @defgroup auxalg Auxiliary Algorithms
    564 @ingroup algs
    565 \brief Auxiliary algorithms implemented in LEMON.
    566 
    567 This group contains some algorithms implemented in LEMON
    568 in order to make it easier to implement complex algorithms.
    569516*/
    570517
     
    579526
    580527/**
    581 @defgroup lp_group LP and MIP Solvers
     528@defgroup lp_group Lp and Mip Solvers
    582529@ingroup gen_opt_group
    583 \brief LP and MIP solver interfaces for LEMON.
    584 
    585 This group contains LP and MIP solver interfaces for LEMON.
    586 Various LP solvers could be used in the same manner with this
    587 high-level interface.
    588 
    589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    590 \ref cplex, \ref soplex.
     530\brief Lp and Mip solver interfaces for LEMON.
     531
     532This group contains Lp and Mip solver interfaces for LEMON. The
     533various LP solvers could be used in the same manner with this
     534interface.
    591535*/
    592536
     
    678622
    679623/**
    680 @defgroup dimacs_group DIMACS Format
     624@defgroup dimacs_group DIMACS format
    681625@ingroup io_group
    682626\brief Read and write files in DIMACS format
     
    727671\brief Skeleton and concept checking classes for graph structures
    728672
    729 This group contains the skeletons and concept checking classes of
    730 graph structures.
     673This group contains the skeletons and concept checking classes of LEMON's
     674graph structures and helper classes used to implement these.
    731675*/
    732676
     
    740684
    741685/**
     686\anchor demoprograms
     687
     688@defgroup demos Demo Programs
     689
     690Some demo programs are listed here. Their full source codes can be found in
     691the \c demo subdirectory of the source tree.
     692
     693In order to compile them, use the <tt>make demo</tt> or the
     694<tt>make check</tt> commands.
     695*/
     696
     697/**
    742698@defgroup tools Standalone Utility Applications
    743699
     
    748704*/
    749705
    750 /**
    751 \anchor demoprograms
    752 
    753 @defgroup demos Demo Programs
    754 
    755 Some demo programs are listed here. Their full source codes can be found in
    756 the \c demo subdirectory of the source tree.
    757 
    758 In order to compile them, use the <tt>make demo</tt> or the
    759 <tt>make check</tt> commands.
    760 */
    761 
    762706}
Note: See TracChangeset for help on using the changeset viewer.