COIN-OR::LEMON - Graph Library

Changeset 50:a34c58ff6e40 in lemon


Ignore:
Timestamp:
01/08/08 04:26:27 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improved groups.dox.
Added missing brief descriptions.
Changed descriptions to be unifom.
Some minor fixes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r41 r50  
    1919/**
    2020@defgroup datas Data Structures
    21 This group describes the several graph structures implemented in LEMON.
     21This group describes the several data structures implemented in LEMON.
    2222*/
    2323
     
    5151LEMON also provides a variety of graphs for these requirements called
    5252\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    53 in conjunction with other graph representation.
     53in conjunction with other graph representations.
    5454
    5555You are free to use the graph structure that fit your requirements
     
    5959
    6060/**
    61 @defgroup semi_adaptors Semi-Adaptors Classes for Graphs
     61@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    6262@ingroup graphs
    6363\brief Graph types between real graphs and graph adaptors.
    6464
    65 Graph types between real graphs and graph adaptors. These classes wrap
    66 graphs to give new functionality as the adaptors do it. On the other
    67 hand they are not light-weight structures as the adaptors.
     65This group describes some graph types between real graphs and graph adaptors.
     66These classes wrap graphs to give new functionality as the adaptors do it.
     67On the other hand they are not light-weight structures as the adaptors.
    6868*/
    6969
     
    7171@defgroup maps Maps
    7272@ingroup datas
    73 \brief Some special purpose map to make life easier.
    74 
    75 LEMON provides several special maps that e.g. combine
     73\brief Map structures implemented in LEMON.
     74
     75This group describes the map structures implemented in LEMON.
     76
     77LEMON provides several special purpose maps that e.g. combine
    7678new maps from existing ones.
    7779*/
     
    8284\brief Special Graph-Related Maps.
    8385
    84 These maps are specifically designed to assign values to the nodes and edges of
    85 graphs.
     86This group describes maps that are specifically designed to assign
     87values to the nodes and edges of graphs.
    8688*/
    8789
     
    9294\brief Tools to create new maps from existing ones
    9395
    94 Map adaptors are used to create "implicit" maps from other maps.
     96This group describes map adaptors that are used to create "implicit"
     97maps from other maps.
    9598
    9699Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
     
    99102of different Value type.
    100103
    101 The typical usage of this classes is the passing implicit maps to
     104The typical usage of this classes is passing implicit maps to
    102105algorithms.  If a function type algorithm is called then the function
    103106type map adaptors can be used comfortable. For example let's see the
     
    128131The usage with class type algorithms is little bit harder. In this
    129132case the function type map adaptors can not be used, because the
    130 function map adaptors give back temporarly objects.
     133function map adaptors give back temporary objects.
    131134\code
    132135  Graph graph;
     
    154157@defgroup matrices Matrices
    155158@ingroup datas
    156 \brief Two dimensional data storages.
    157 
    158 Two dimensional data storages.
     159\brief Two dimensional data storages implemented in LEMON.
     160
     161This group describes two dimensional data storages implemented in LEMON.
    159162*/
    160163
     
    164167\brief Path structures implemented in LEMON.
    165168
    166 LEMON provides flexible data structures
    167 to work with paths.
    168 
    169 All of them have similar interfaces, and it can be copied easily with
    170 assignment operator and copy constructor. This make it easy and
     169This group describes the path structures implemented in LEMON.
     170
     171LEMON provides flexible data structures to work with paths.
     172All of them have similar interfaces and they can be copied easily with
     173assignment operators and copy constructors. This makes it easy and
    171174efficient to have e.g. the Dijkstra algorithm to store its result in
    172175any kind of path structure.
     
    179182@defgroup auxdat Auxiliary Data Structures
    180183@ingroup datas
    181 \brief Some data structures implemented in LEMON.
    182 
    183 This group describes the data structures implemented in LEMON in
     184\brief Auxiliary data structures implemented in LEMON.
     185
     186This group describes some data structures implemented in LEMON in
    184187order to make it easier to implement combinatorial algorithms.
    185188*/
     
    198201@defgroup search Graph Search
    199202@ingroup algs
    200 \brief This group contains the common graph
    201 search algorithms.
    202 
    203 This group contains the common graph
    204 search algorithms like Bfs and Dfs.
     203\brief Common graph search algorithms.
     204
     205This group describes the common graph search algorithms like
     206Breadth-first search (Bfs) and Depth-first search (Dfs).
    205207*/
    206208
     
    208210@defgroup shortest_path Shortest Path algorithms
    209211@ingroup algs
    210 \brief This group describes the algorithms
    211 for finding shortest paths.
    212 
    213 This group describes the algorithms for finding shortest paths in
    214 graphs.
    215 
     212\brief Algorithms for finding shortest paths.
     213
     214This group describes the algorithms for finding shortest paths in graphs.
    216215*/
    217216
     
    219218@defgroup max_flow Maximum Flow algorithms
    220219@ingroup algs
    221 \brief This group describes the algorithms for finding maximum flows.
     220\brief Algorithms for finding maximum flows.
    222221
    223222This group describes the algorithms for finding maximum flows and
    224223feasible circulations.
    225224
    226 The maximum flow problem is to find a flow between a single-source and
    227 single-target that is maximum. Formally, there is \f$G=(V,A)\f$
     225The maximum flow problem is to find a flow between a single source and
     226a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    228227directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    229228function and given \f$s, t \in V\f$ source and target node. The
    230 maximum flow is the solution of the next optimization problem:
     229maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    231230
    232231\f[ 0 \le f_a \le c_a \f]
    233 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f]
     232\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]
    234233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    235234
    236 The lemon contains several algorithms for solve maximum flow problems:
     235LEMON contains several algorithms for solving maximum flow problems:
    237236- \ref lemon::EdmondsKarp "Edmonds-Karp"
    238237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
    239 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree"
     238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    240239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    241240
    242 In most cases the \ref lemon::Preflow "preflow" algorithm provides the
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    243242fastest method to compute the maximum flow. All impelementations
    244 provides functions for query the minimum cut, which is the dual linear
    245 programming probelm of the maximum flow.
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
    246245
    247246*/
     
    251250@ingroup algs
    252251
    253 \brief This group describes the algorithms
    254 for finding minimum cost flows and circulations.
     252\brief Algorithms for finding minimum cost flows and circulations.
    255253
    256254This group describes the algorithms for finding minimum cost flows and
     
    262260@ingroup algs
    263261
    264 \brief This group describes the algorithms for finding minimum cut in
    265 graphs.
     262\brief Algorithms for finding minimum cut in graphs.
    266263
    267264This group describes the algorithms for finding minimum cut in graphs.
     
    271268outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    272269\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    273 cut is the solution of the next optimization problem:
     270cut is the \f$X\f$ solution of the next optimization problem:
    274271
    275272\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    276273
    277 The lemon contains several algorithms related to minimum cut problems:
    278 
    279 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut
     274LEMON contains several algorithms related to minimum cut problems:
     275
     276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    280277  in directed graphs 
    281 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    282279  calculate minimum cut in undirected graphs
    283 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all
     280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    284281  pairs minimum cut in undirected graphs
    285282
     
    292289@defgroup graph_prop Connectivity and other graph properties
    293290@ingroup algs
    294 \brief This group describes the algorithms
    295 for discover the graph properties
    296 
    297 This group describes the algorithms for discover the graph properties
    298 like connectivity, bipartiteness, euler property, simplicity, etc...
     291\brief Algorithms for discovering the graph properties
     292
     293This group describes the algorithms for discovering the graph properties
     294like connectivity, bipartiteness, euler property, simplicity etc.
    299295
    300296\image html edge_biconnected_components.png
     
    305301@defgroup planar Planarity embedding and drawing
    306302@ingroup algs
    307 \brief This group contains algorithms for planarity embedding and drawing
    308 
    309 This group contains algorithms for planarity checking, embedding and drawing.
     303\brief Algorithms for planarity checking, embedding and drawing
     304
     305This group describes the algorithms for planarity checking, embedding and drawing.
    310306
    311307\image html planar.png
     
    316312@defgroup matching Matching algorithms
    317313@ingroup algs
    318 \brief This group describes the algorithms
    319 for find matchings in graphs and bipartite graphs.
    320 
    321 This group provides some algorithm objects and function to calculate
     314\brief Algorithms for finding matchings in graphs and bipartite graphs.
     315
     316This group contains algorithm objects and functions to calculate
    322317matchings in graphs and bipartite graphs. The general matching problem is
    323318finding a subset of the edges which does not shares common endpoints.
     
    359354@defgroup spantree Minimum Spanning Tree algorithms
    360355@ingroup algs
    361 \brief This group contains the algorithms for finding a minimum cost spanning
     356\brief Algorithms for finding a minimum cost spanning tree in a graph.
     357
     358This group describes the algorithms for finding a minimum cost spanning
    362359tree in a graph
    363 
    364 This group contains the algorithms for finding a minimum cost spanning
    365 tree in a graph
    366360*/
    367361
     
    370364@defgroup auxalg Auxiliary algorithms
    371365@ingroup algs
    372 \brief Some algorithms implemented in LEMON.
    373 
    374 This group describes the algorithms in LEMON in order to make
    375 it easier to implement complex algorithms.
     366\brief Auxiliary algorithms implemented in LEMON.
     367
     368This group describes some algorithms implemented in LEMON
     369in order to make it easier to implement complex algorithms.
    376370*/
    377371
    378372/**
    379373@defgroup approx Approximation algorithms
    380 \brief Approximation algorithms
    381 
    382 Approximation and heuristic algorithms
     374\brief Approximation algorithms.
     375
     376This group describes the approximation and heuristic algorithms
     377implemented in LEMON.
    383378*/
    384379
     
    407402@defgroup lp_utils Tools for Lp and Mip solvers
    408403@ingroup lp_group
    409 \brief This group adds some helper tools to the Lp and Mip solvers
    410 implemented in LEMON.
     404\brief Helper tools to the Lp and Mip solvers.
    411405
    412406This group adds some helper tools to general optimization framework
     
    419413\brief Metaheuristics for LEMON library.
    420414
    421 This group contains some metaheuristic optimization tools.
     415This group describes some metaheuristic optimization tools.
    422416*/
    423417
    424418/**
    425419@defgroup utils Tools and Utilities
    426 \brief Tools and Utilities for Programming in LEMON
    427 
    428 Tools and Utilities for Programming in LEMON
     420\brief Tools and utilities for programming in LEMON
     421
     422Tools and utilities for programming in LEMON.
    429423*/
    430424
     
    432426@defgroup gutils Basic Graph Utilities
    433427@ingroup utils
    434 \brief This group describes some simple basic graph utilities.
     428\brief Simple basic graph utilities.
    435429
    436430This group describes some simple basic graph utilities.
     
    440434@defgroup misc Miscellaneous Tools
    441435@ingroup utils
    442 Here you can find several useful tools for development,
     436\brief Tools for development, debugging and testing.
     437
     438This group describes several useful tools for development,
    443439debugging and testing.
    444440*/
    445 
    446441
    447442/**
    448443@defgroup timecount Time measuring and Counting
    449444@ingroup misc
    450 Here you can find simple tools for measuring the performance
     445\brief Simple tools for measuring the performance of algorithms.
     446
     447This group describes simple tools for measuring the performance
    451448of algorithms.
    452449*/
     
    455452@defgroup graphbits Tools for Graph Implementation
    456453@ingroup utils
    457 \brief Tools to Make It Easier to Make Graphs.
    458 
    459 This group describes the tools that makes it easier to make graphs and
     454\brief Tools to make it easier to create graphs.
     455
     456This group describes the tools that makes it easier to create graphs and
    460457the maps that dynamically update with the graph changes.
    461458*/
     
    464461@defgroup exceptions Exceptions
    465462@ingroup utils
    466 This group contains the exceptions thrown by LEMON library
     463\brief Exceptions defined in LEMON.
     464
     465This group describes the exceptions defined in LEMON.
    467466*/
    468467
    469468/**
    470469@defgroup io_group Input-Output
    471 \brief Several Graph Input-Output methods
    472 
    473 Here you can find tools for importing and exporting graphs
     470\brief Graph Input-Output methods
     471
     472This group describes the tools for importing and exporting graphs
    474473and graph related data. Now it supports the LEMON format, the
    475 \c DIMACS format and the encapsulated postscript format.
     474\c DIMACS format and the encapsulated postscript (EPS) format.
    476475*/
    477476
     
    481480\brief Reading and writing LEMON format
    482481
    483 Methods for reading and writing LEMON format. More about this
    484 format you can find on the \ref graph-io-page "Graph Input-Output"
     482This group describes methods for reading and writing LEMON format.
     483You can find more about this format on the \ref graph-io-page "Graph Input-Output"
    485484tutorial pages.
    486485*/
     
    491490\brief Section readers and writers for lemon Input-Output.
    492491
    493 Here you can find which section readers and writers can attach to
    494 the LemonReader and LemonWriter.
     492This group describes section readers and writers that can be attached to
     493\ref LemonReader and \ref LemonWriter.
    495494*/
    496495
     
    510509\brief General \c EPS drawer and graph exporter
    511510
    512 This group contains general \c EPS drawing methods and special
     511This group describes general \c EPS drawing methods and special
    513512graph exporting tools.
    514513*/
     
    538537
    539538- The concept descriptor classes also provide a <em>checker class</em>
    540   that makes it possible check whether a certain implementation of a
     539  that makes it possible to check whether a certain implementation of a
    541540  concept indeed provides all the required features.
    542541
     
    551550\brief Skeleton and concept checking classes for graph structures
    552551
    553 This group contains the skeletons and concept checking classes of LEMON's
     552This group describes the skeletons and concept checking classes of LEMON's
    554553graph structures and helper classes used to implement these.
    555554*/
     
    557556/* --- Unused group
    558557@defgroup experimental Experimental Structures and Algorithms
    559 This group contains some Experimental structures and algorithms.
     558This group describes some Experimental structures and algorithms.
    560559The stuff here is subject to change.
    561560*/
     
    571570It order to compile them, use <tt>--enable-demo</tt> configure option when
    572571build the library.
    573 
    574572*/
    575573
     
    581579The standard compilation procedure (<tt>./configure;make</tt>) will compile
    582580them, as well.
    583 
    584 */
    585 
     581*/
     582
Note: See TracChangeset for help on using the changeset viewer.