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 }