doc/groups.dox
changeset 817 432c54cec63c
parent 815 0a42883c8221
parent 802 134852d7fb0a
child 818 8452ca46e29a
     1.1 --- a/doc/groups.dox	Tue Aug 18 10:08:28 2009 +0200
     1.2 +++ b/doc/groups.dox	Thu Nov 05 08:39:49 2009 +0100
     1.3 @@ -226,14 +226,6 @@
     1.4  */
     1.5  
     1.6  /**
     1.7 -@defgroup matrices Matrices
     1.8 -@ingroup datas
     1.9 -\brief Two dimensional data storages implemented in LEMON.
    1.10 -
    1.11 -This group contains two dimensional data storages implemented in LEMON.
    1.12 -*/
    1.13 -
    1.14 -/**
    1.15  @defgroup paths Path Structures
    1.16  @ingroup datas
    1.17  \brief %Path structures implemented in LEMON.
    1.18 @@ -246,7 +238,36 @@
    1.19  efficient to have e.g. the Dijkstra algorithm to store its result in
    1.20  any kind of path structure.
    1.21  
    1.22 -\sa lemon::concepts::Path
    1.23 +\sa \ref concepts::Path "Path concept"
    1.24 +*/
    1.25 +
    1.26 +/**
    1.27 +@defgroup heaps Heap Structures
    1.28 +@ingroup datas
    1.29 +\brief %Heap structures implemented in LEMON.
    1.30 +
    1.31 +This group contains the heap structures implemented in LEMON.
    1.32 +
    1.33 +LEMON provides several heap classes. They are efficient implementations
    1.34 +of the abstract data type \e priority \e queue. They store items with
    1.35 +specified values called \e priorities in such a way that finding and
    1.36 +removing the item with minimum priority are efficient.
    1.37 +The basic operations are adding and erasing items, changing the priority
    1.38 +of an item, etc.
    1.39 +
    1.40 +Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    1.41 +The heap implementations have the same interface, thus any of them can be
    1.42 +used easily in such algorithms.
    1.43 +
    1.44 +\sa \ref concepts::Heap "Heap concept"
    1.45 +*/
    1.46 +
    1.47 +/**
    1.48 +@defgroup matrices Matrices
    1.49 +@ingroup datas
    1.50 +\brief Two dimensional data storages implemented in LEMON.
    1.51 +
    1.52 +This group contains two dimensional data storages implemented in LEMON.
    1.53  */
    1.54  
    1.55  /**
    1.56 @@ -259,6 +280,28 @@
    1.57  */
    1.58  
    1.59  /**
    1.60 +@defgroup geomdat Geometric Data Structures
    1.61 +@ingroup auxdat
    1.62 +\brief Geometric data structures implemented in LEMON.
    1.63 +
    1.64 +This group contains geometric data structures implemented in LEMON.
    1.65 +
    1.66 + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
    1.67 +   vector with the usual operations.
    1.68 + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
    1.69 +   rectangular bounding box of a set of \ref lemon::dim2::Point
    1.70 +   "dim2::Point"'s.
    1.71 +*/
    1.72 +
    1.73 +/**
    1.74 +@defgroup matrices Matrices
    1.75 +@ingroup auxdat
    1.76 +\brief Two dimensional data storages implemented in LEMON.
    1.77 +
    1.78 +This group contains two dimensional data storages implemented in LEMON.
    1.79 +*/
    1.80 +
    1.81 +/**
    1.82  @defgroup algs Algorithms
    1.83  \brief This group contains the several algorithms
    1.84  implemented in LEMON.
    1.85 @@ -273,7 +316,8 @@
    1.86  \brief Common graph search algorithms.
    1.87  
    1.88  This group contains the common graph search algorithms, namely
    1.89 -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    1.90 +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    1.91 +\ref clrs01algorithms.
    1.92  */
    1.93  
    1.94  /**
    1.95 @@ -281,7 +325,8 @@
    1.96  @ingroup algs
    1.97  \brief Algorithms for finding shortest paths.
    1.98  
    1.99 -This group contains the algorithms for finding shortest paths in digraphs.
   1.100 +This group contains the algorithms for finding shortest paths in digraphs
   1.101 +\ref clrs01algorithms.
   1.102  
   1.103   - \ref Dijkstra algorithm for finding shortest paths from a source node
   1.104     when all arc lengths are non-negative.
   1.105 @@ -298,12 +343,21 @@
   1.106  */
   1.107  
   1.108  /**
   1.109 +@defgroup spantree Minimum Spanning Tree Algorithms
   1.110 +@ingroup algs
   1.111 +\brief Algorithms for finding minimum cost spanning trees and arborescences.
   1.112 +
   1.113 +This group contains the algorithms for finding minimum cost spanning
   1.114 +trees and arborescences \ref clrs01algorithms.
   1.115 +*/
   1.116 +
   1.117 +/**
   1.118  @defgroup max_flow Maximum Flow Algorithms
   1.119  @ingroup algs
   1.120  \brief Algorithms for finding maximum flows.
   1.121  
   1.122  This group contains the algorithms for finding maximum flows and
   1.123 -feasible circulations.
   1.124 +feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
   1.125  
   1.126  The \e maximum \e flow \e problem is to find a flow of maximum value between
   1.127  a single source and a single target. Formally, there is a \f$G=(V,A)\f$
   1.128 @@ -318,12 +372,16 @@
   1.129  \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
   1.130  
   1.131  LEMON contains several algorithms for solving maximum flow problems:
   1.132 -- \ref EdmondsKarp Edmonds-Karp algorithm.
   1.133 -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
   1.134 -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
   1.135 -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
   1.136 +- \ref EdmondsKarp Edmonds-Karp algorithm
   1.137 +  \ref edmondskarp72theoretical.
   1.138 +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
   1.139 +  \ref goldberg88newapproach.
   1.140 +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
   1.141 +  \ref dinic70algorithm, \ref sleator83dynamic.
   1.142 +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
   1.143 +  \ref goldberg88newapproach, \ref sleator83dynamic.
   1.144  
   1.145 -In most cases the \ref Preflow "Preflow" algorithm provides the
   1.146 +In most cases the \ref Preflow algorithm provides the
   1.147  fastest method for computing a maximum flow. All implementations
   1.148  also provide functions to query the minimum cut, which is the dual
   1.149  problem of maximum flow.
   1.150 @@ -341,18 +399,22 @@
   1.151  \brief Algorithms for finding minimum cost flows and circulations.
   1.152  
   1.153  This group contains the algorithms for finding minimum cost flows and
   1.154 -circulations. For more information about this problem and its dual
   1.155 -solution see \ref min_cost_flow "Minimum Cost Flow Problem".
   1.156 +circulations \ref amo93networkflows. For more information about this
   1.157 +problem and its dual solution, see \ref min_cost_flow
   1.158 +"Minimum Cost Flow Problem".
   1.159  
   1.160  LEMON contains several algorithms for this problem.
   1.161   - \ref NetworkSimplex Primal Network Simplex algorithm with various
   1.162 -   pivot strategies.
   1.163 +   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
   1.164   - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
   1.165 -   cost scaling.
   1.166 +   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
   1.167 +   \ref bunnagel98efficient.
   1.168   - \ref CapacityScaling Successive Shortest %Path algorithm with optional
   1.169 -   capacity scaling.
   1.170 - - \ref CancelAndTighten The Cancel and Tighten algorithm.
   1.171 - - \ref CycleCanceling Cycle-Canceling algorithms.
   1.172 +   capacity scaling \ref edmondskarp72theoretical.
   1.173 + - \ref CancelAndTighten The Cancel and Tighten algorithm
   1.174 +   \ref goldberg89cyclecanceling.
   1.175 + - \ref CycleCanceling Cycle-Canceling algorithms
   1.176 +   \ref klein67primal, \ref goldberg89cyclecanceling.
   1.177  
   1.178  In general NetworkSimplex is the most efficient implementation,
   1.179  but in special cases other algorithms could be faster.
   1.180 @@ -375,7 +437,7 @@
   1.181  cut is the \f$X\f$ solution of the next optimization problem:
   1.182  
   1.183  \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
   1.184 -    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
   1.185 +    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
   1.186  
   1.187  LEMON contains several algorithms related to minimum cut problems:
   1.188  
   1.189 @@ -425,30 +487,6 @@
   1.190  */
   1.191  
   1.192  /**
   1.193 -@defgroup graph_properties Connectivity and Other Graph Properties
   1.194 -@ingroup algs
   1.195 -\brief Algorithms for discovering the graph properties
   1.196 -
   1.197 -This group contains the algorithms for discovering the graph properties
   1.198 -like connectivity, bipartiteness, euler property, simplicity etc.
   1.199 -
   1.200 -\image html edge_biconnected_components.png
   1.201 -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   1.202 -*/
   1.203 -
   1.204 -/**
   1.205 -@defgroup planar Planarity Embedding and Drawing
   1.206 -@ingroup algs
   1.207 -\brief Algorithms for planarity checking, embedding and drawing
   1.208 -
   1.209 -This group contains the algorithms for planarity checking,
   1.210 -embedding and drawing.
   1.211 -
   1.212 -\image html planar.png
   1.213 -\image latex planar.eps "Plane graph" width=\textwidth
   1.214 -*/
   1.215 -
   1.216 -/**
   1.217  @defgroup matching Matching Algorithms
   1.218  @ingroup algs
   1.219  \brief Algorithms for finding matchings in graphs and bipartite graphs.
   1.220 @@ -489,12 +527,36 @@
   1.221  */
   1.222  
   1.223  /**
   1.224 -@defgroup spantree Minimum Spanning Tree Algorithms
   1.225 +@defgroup graph_properties Connectivity and Other Graph Properties
   1.226  @ingroup algs
   1.227 -\brief Algorithms for finding minimum cost spanning trees and arborescences.
   1.228 +\brief Algorithms for discovering the graph properties
   1.229  
   1.230 -This group contains the algorithms for finding minimum cost spanning
   1.231 -trees and arborescences.
   1.232 +This group contains the algorithms for discovering the graph properties
   1.233 +like connectivity, bipartiteness, euler property, simplicity etc.
   1.234 +
   1.235 +\image html connected_components.png
   1.236 +\image latex connected_components.eps "Connected components" width=\textwidth
   1.237 +*/
   1.238 +
   1.239 +/**
   1.240 +@defgroup planar Planarity Embedding and Drawing
   1.241 +@ingroup algs
   1.242 +\brief Algorithms for planarity checking, embedding and drawing
   1.243 +
   1.244 +This group contains the algorithms for planarity checking,
   1.245 +embedding and drawing.
   1.246 +
   1.247 +\image html planar.png
   1.248 +\image latex planar.eps "Plane graph" width=\textwidth
   1.249 +*/
   1.250 +
   1.251 +/**
   1.252 +@defgroup approx Approximation Algorithms
   1.253 +@ingroup algs
   1.254 +\brief Approximation algorithms.
   1.255 +
   1.256 +This group contains the approximation and heuristic algorithms
   1.257 +implemented in LEMON.
   1.258  */
   1.259  
   1.260  /**
   1.261 @@ -507,15 +569,6 @@
   1.262  */
   1.263  
   1.264  /**
   1.265 -@defgroup approx Approximation Algorithms
   1.266 -@ingroup algs
   1.267 -\brief Approximation algorithms.
   1.268 -
   1.269 -This group contains the approximation and heuristic algorithms
   1.270 -implemented in LEMON.
   1.271 -*/
   1.272 -
   1.273 -/**
   1.274  @defgroup gen_opt_group General Optimization Tools
   1.275  \brief This group contains some general optimization frameworks
   1.276  implemented in LEMON.
   1.277 @@ -525,13 +578,16 @@
   1.278  */
   1.279  
   1.280  /**
   1.281 -@defgroup lp_group Lp and Mip Solvers
   1.282 +@defgroup lp_group LP and MIP Solvers
   1.283  @ingroup gen_opt_group
   1.284 -\brief Lp and Mip solver interfaces for LEMON.
   1.285 +\brief LP and MIP solver interfaces for LEMON.
   1.286  
   1.287 -This group contains Lp and Mip solver interfaces for LEMON. The
   1.288 -various LP solvers could be used in the same manner with this
   1.289 -interface.
   1.290 +This group contains LP and MIP solver interfaces for LEMON.
   1.291 +Various LP solvers could be used in the same manner with this
   1.292 +high-level interface.
   1.293 +
   1.294 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
   1.295 +\ref cplex, \ref soplex.
   1.296  */
   1.297  
   1.298  /**
   1.299 @@ -621,7 +677,7 @@
   1.300  */
   1.301  
   1.302  /**
   1.303 -@defgroup dimacs_group DIMACS format
   1.304 +@defgroup dimacs_group DIMACS Format
   1.305  @ingroup io_group
   1.306  \brief Read and write files in DIMACS format
   1.307  
   1.308 @@ -670,8 +726,8 @@
   1.309  @ingroup concept
   1.310  \brief Skeleton and concept checking classes for graph structures
   1.311  
   1.312 -This group contains the skeletons and concept checking classes of LEMON's
   1.313 -graph structures and helper classes used to implement these.
   1.314 +This group contains the skeletons and concept checking classes of
   1.315 +graph structures.
   1.316  */
   1.317  
   1.318  /**
   1.319 @@ -683,6 +739,15 @@
   1.320  */
   1.321  
   1.322  /**
   1.323 +@defgroup tools Standalone Utility Applications
   1.324 +
   1.325 +Some utility applications are listed here.
   1.326 +
   1.327 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
   1.328 +them, as well.
   1.329 +*/
   1.330 +
   1.331 +/**
   1.332  \anchor demoprograms
   1.333  
   1.334  @defgroup demos Demo Programs
   1.335 @@ -694,13 +759,4 @@
   1.336  <tt>make check</tt> commands.
   1.337  */
   1.338  
   1.339 -/**
   1.340 -@defgroup tools Standalone Utility Applications
   1.341 -
   1.342 -Some utility applications are listed here.
   1.343 -
   1.344 -The standard compilation procedure (<tt>./configure;make</tt>) will compile
   1.345 -them, as well.
   1.346 -*/
   1.347 -
   1.348  }