1.1 --- a/doc/groups.dox Thu Nov 05 10:01:02 2009 +0100
1.2 +++ b/doc/groups.dox Thu Nov 05 10:23:16 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 @@ -391,27 +453,40 @@
1.190 */
1.191
1.192 /**
1.193 -@defgroup graph_properties Connectivity and Other Graph Properties
1.194 +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
1.195 @ingroup algs
1.196 -\brief Algorithms for discovering the graph properties
1.197 +\brief Algorithms for finding minimum mean cycles.
1.198
1.199 -This group contains the algorithms for discovering the graph properties
1.200 -like connectivity, bipartiteness, euler property, simplicity etc.
1.201 +This group contains the algorithms for finding minimum mean cycles
1.202 +\ref clrs01algorithms, \ref amo93networkflows.
1.203
1.204 -\image html edge_biconnected_components.png
1.205 -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.206 -*/
1.207 +The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.208 +of minimum mean length (cost) in a digraph.
1.209 +The mean length of a cycle is the average length of its arcs, i.e. the
1.210 +ratio between the total length of the cycle and the number of arcs on it.
1.211
1.212 -/**
1.213 -@defgroup planar Planarity Embedding and Drawing
1.214 -@ingroup algs
1.215 -\brief Algorithms for planarity checking, embedding and drawing
1.216 +This problem has an important connection to \e conservative \e length
1.217 +\e functions, too. A length function on the arcs of a digraph is called
1.218 +conservative if and only if there is no directed cycle of negative total
1.219 +length. For an arbitrary length function, the negative of the minimum
1.220 +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
1.221 +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
1.222 +function.
1.223
1.224 -This group contains the algorithms for planarity checking,
1.225 -embedding and drawing.
1.226 +LEMON contains three algorithms for solving the minimum mean cycle problem:
1.227 +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
1.228 + \ref dasdan98minmeancycle.
1.229 +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
1.230 + version of Karp's algorithm \ref dasdan98minmeancycle.
1.231 +- \ref Howard "Howard"'s policy iteration algorithm
1.232 + \ref dasdan98minmeancycle.
1.233
1.234 -\image html planar.png
1.235 -\image latex planar.eps "Plane graph" width=\textwidth
1.236 +In practice, the Howard algorithm proved to be by far the most efficient
1.237 +one, though the best known theoretical bound on its running time is
1.238 +exponential.
1.239 +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
1.240 +O(n<sup>2</sup>+e), but the latter one is typically faster due to the
1.241 +applied early termination scheme.
1.242 */
1.243
1.244 /**
1.245 @@ -455,12 +530,36 @@
1.246 */
1.247
1.248 /**
1.249 -@defgroup spantree Minimum Spanning Tree Algorithms
1.250 +@defgroup graph_properties Connectivity and Other Graph Properties
1.251 @ingroup algs
1.252 -\brief Algorithms for finding minimum cost spanning trees and arborescences.
1.253 +\brief Algorithms for discovering the graph properties
1.254
1.255 -This group contains the algorithms for finding minimum cost spanning
1.256 -trees and arborescences.
1.257 +This group contains the algorithms for discovering the graph properties
1.258 +like connectivity, bipartiteness, euler property, simplicity etc.
1.259 +
1.260 +\image html connected_components.png
1.261 +\image latex connected_components.eps "Connected components" width=\textwidth
1.262 +*/
1.263 +
1.264 +/**
1.265 +@defgroup planar Planarity Embedding and Drawing
1.266 +@ingroup algs
1.267 +\brief Algorithms for planarity checking, embedding and drawing
1.268 +
1.269 +This group contains the algorithms for planarity checking,
1.270 +embedding and drawing.
1.271 +
1.272 +\image html planar.png
1.273 +\image latex planar.eps "Plane graph" width=\textwidth
1.274 +*/
1.275 +
1.276 +/**
1.277 +@defgroup approx Approximation Algorithms
1.278 +@ingroup algs
1.279 +\brief Approximation algorithms.
1.280 +
1.281 +This group contains the approximation and heuristic algorithms
1.282 +implemented in LEMON.
1.283 */
1.284
1.285 /**
1.286 @@ -473,15 +572,6 @@
1.287 */
1.288
1.289 /**
1.290 -@defgroup approx Approximation Algorithms
1.291 -@ingroup algs
1.292 -\brief Approximation algorithms.
1.293 -
1.294 -This group contains the approximation and heuristic algorithms
1.295 -implemented in LEMON.
1.296 -*/
1.297 -
1.298 -/**
1.299 @defgroup gen_opt_group General Optimization Tools
1.300 \brief This group contains some general optimization frameworks
1.301 implemented in LEMON.
1.302 @@ -491,13 +581,16 @@
1.303 */
1.304
1.305 /**
1.306 -@defgroup lp_group Lp and Mip Solvers
1.307 +@defgroup lp_group LP and MIP Solvers
1.308 @ingroup gen_opt_group
1.309 -\brief Lp and Mip solver interfaces for LEMON.
1.310 +\brief LP and MIP solver interfaces for LEMON.
1.311
1.312 -This group contains Lp and Mip solver interfaces for LEMON. The
1.313 -various LP solvers could be used in the same manner with this
1.314 -interface.
1.315 +This group contains LP and MIP solver interfaces for LEMON.
1.316 +Various LP solvers could be used in the same manner with this
1.317 +high-level interface.
1.318 +
1.319 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.320 +\ref cplex, \ref soplex.
1.321 */
1.322
1.323 /**
1.324 @@ -587,7 +680,7 @@
1.325 */
1.326
1.327 /**
1.328 -@defgroup dimacs_group DIMACS format
1.329 +@defgroup dimacs_group DIMACS Format
1.330 @ingroup io_group
1.331 \brief Read and write files in DIMACS format
1.332
1.333 @@ -636,8 +729,8 @@
1.334 @ingroup concept
1.335 \brief Skeleton and concept checking classes for graph structures
1.336
1.337 -This group contains the skeletons and concept checking classes of LEMON's
1.338 -graph structures and helper classes used to implement these.
1.339 +This group contains the skeletons and concept checking classes of
1.340 +graph structures.
1.341 */
1.342
1.343 /**
1.344 @@ -649,6 +742,15 @@
1.345 */
1.346
1.347 /**
1.348 +@defgroup tools Standalone Utility Applications
1.349 +
1.350 +Some utility applications are listed here.
1.351 +
1.352 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.353 +them, as well.
1.354 +*/
1.355 +
1.356 +/**
1.357 \anchor demoprograms
1.358
1.359 @defgroup demos Demo Programs
1.360 @@ -660,13 +762,4 @@
1.361 <tt>make check</tt> commands.
1.362 */
1.363
1.364 -/**
1.365 -@defgroup tools Standalone Utility Applications
1.366 -
1.367 -Some utility applications are listed here.
1.368 -
1.369 -The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.370 -them, as well.
1.371 -*/
1.372 -
1.373 }