1.1 --- a/doc/groups.dox Sun Oct 04 10:15:32 2009 +0200
1.2 +++ b/doc/groups.dox Wed Dec 09 11:14:06 2009 +0100
1.3 @@ -280,6 +280,28 @@
1.4 */
1.5
1.6 /**
1.7 +@defgroup geomdat Geometric Data Structures
1.8 +@ingroup auxdat
1.9 +\brief Geometric data structures implemented in LEMON.
1.10 +
1.11 +This group contains geometric data structures implemented in LEMON.
1.12 +
1.13 + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
1.14 + vector with the usual operations.
1.15 + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
1.16 + rectangular bounding box of a set of \ref lemon::dim2::Point
1.17 + "dim2::Point"'s.
1.18 +*/
1.19 +
1.20 +/**
1.21 +@defgroup matrices Matrices
1.22 +@ingroup auxdat
1.23 +\brief Two dimensional data storages implemented in LEMON.
1.24 +
1.25 +This group contains two dimensional data storages implemented in LEMON.
1.26 +*/
1.27 +
1.28 +/**
1.29 @defgroup algs Algorithms
1.30 \brief This group contains the several algorithms
1.31 implemented in LEMON.
1.32 @@ -294,7 +316,8 @@
1.33 \brief Common graph search algorithms.
1.34
1.35 This group contains the common graph search algorithms, namely
1.36 -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
1.37 +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
1.38 +\ref clrs01algorithms.
1.39 */
1.40
1.41 /**
1.42 @@ -302,7 +325,8 @@
1.43 @ingroup algs
1.44 \brief Algorithms for finding shortest paths.
1.45
1.46 -This group contains the algorithms for finding shortest paths in digraphs.
1.47 +This group contains the algorithms for finding shortest paths in digraphs
1.48 +\ref clrs01algorithms.
1.49
1.50 - \ref Dijkstra algorithm for finding shortest paths from a source node
1.51 when all arc lengths are non-negative.
1.52 @@ -319,12 +343,21 @@
1.53 */
1.54
1.55 /**
1.56 +@defgroup spantree Minimum Spanning Tree Algorithms
1.57 +@ingroup algs
1.58 +\brief Algorithms for finding minimum cost spanning trees and arborescences.
1.59 +
1.60 +This group contains the algorithms for finding minimum cost spanning
1.61 +trees and arborescences \ref clrs01algorithms.
1.62 +*/
1.63 +
1.64 +/**
1.65 @defgroup max_flow Maximum Flow Algorithms
1.66 @ingroup algs
1.67 \brief Algorithms for finding maximum flows.
1.68
1.69 This group contains the algorithms for finding maximum flows and
1.70 -feasible circulations.
1.71 +feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
1.72
1.73 The \e maximum \e flow \e problem is to find a flow of maximum value between
1.74 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.75 @@ -339,12 +372,16 @@
1.76 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
1.77
1.78 LEMON contains several algorithms for solving maximum flow problems:
1.79 -- \ref EdmondsKarp Edmonds-Karp algorithm.
1.80 -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
1.81 -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
1.82 -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
1.83 +- \ref EdmondsKarp Edmonds-Karp algorithm
1.84 + \ref edmondskarp72theoretical.
1.85 +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
1.86 + \ref goldberg88newapproach.
1.87 +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
1.88 + \ref dinic70algorithm, \ref sleator83dynamic.
1.89 +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
1.90 + \ref goldberg88newapproach, \ref sleator83dynamic.
1.91
1.92 -In most cases the \ref Preflow "Preflow" algorithm provides the
1.93 +In most cases the \ref Preflow algorithm provides the
1.94 fastest method for computing a maximum flow. All implementations
1.95 also provide functions to query the minimum cut, which is the dual
1.96 problem of maximum flow.
1.97 @@ -362,18 +399,22 @@
1.98 \brief Algorithms for finding minimum cost flows and circulations.
1.99
1.100 This group contains the algorithms for finding minimum cost flows and
1.101 -circulations. For more information about this problem and its dual
1.102 -solution see \ref min_cost_flow "Minimum Cost Flow Problem".
1.103 +circulations \ref amo93networkflows. For more information about this
1.104 +problem and its dual solution, see \ref min_cost_flow
1.105 +"Minimum Cost Flow Problem".
1.106
1.107 LEMON contains several algorithms for this problem.
1.108 - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.109 - pivot strategies.
1.110 + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
1.111 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.112 - cost scaling.
1.113 + cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
1.114 + \ref bunnagel98efficient.
1.115 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
1.116 - capacity scaling.
1.117 - - \ref CancelAndTighten The Cancel and Tighten algorithm.
1.118 - - \ref CycleCanceling Cycle-Canceling algorithms.
1.119 + capacity scaling \ref edmondskarp72theoretical.
1.120 + - \ref CancelAndTighten The Cancel and Tighten algorithm
1.121 + \ref goldberg89cyclecanceling.
1.122 + - \ref CycleCanceling Cycle-Canceling algorithms
1.123 + \ref klein67primal, \ref goldberg89cyclecanceling.
1.124
1.125 In general NetworkSimplex is the most efficient implementation,
1.126 but in special cases other algorithms could be faster.
1.127 @@ -396,7 +437,7 @@
1.128 cut is the \f$X\f$ solution of the next optimization problem:
1.129
1.130 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
1.131 - \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
1.132 + \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
1.133
1.134 LEMON contains several algorithms related to minimum cut problems:
1.135
1.136 @@ -412,27 +453,40 @@
1.137 */
1.138
1.139 /**
1.140 -@defgroup graph_properties Connectivity and Other Graph Properties
1.141 +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
1.142 @ingroup algs
1.143 -\brief Algorithms for discovering the graph properties
1.144 +\brief Algorithms for finding minimum mean cycles.
1.145
1.146 -This group contains the algorithms for discovering the graph properties
1.147 -like connectivity, bipartiteness, euler property, simplicity etc.
1.148 +This group contains the algorithms for finding minimum mean cycles
1.149 +\ref clrs01algorithms, \ref amo93networkflows.
1.150
1.151 -\image html edge_biconnected_components.png
1.152 -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.153 -*/
1.154 +The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.155 +of minimum mean length (cost) in a digraph.
1.156 +The mean length of a cycle is the average length of its arcs, i.e. the
1.157 +ratio between the total length of the cycle and the number of arcs on it.
1.158
1.159 -/**
1.160 -@defgroup planar Planarity Embedding and Drawing
1.161 -@ingroup algs
1.162 -\brief Algorithms for planarity checking, embedding and drawing
1.163 +This problem has an important connection to \e conservative \e length
1.164 +\e functions, too. A length function on the arcs of a digraph is called
1.165 +conservative if and only if there is no directed cycle of negative total
1.166 +length. For an arbitrary length function, the negative of the minimum
1.167 +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
1.168 +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
1.169 +function.
1.170
1.171 -This group contains the algorithms for planarity checking,
1.172 -embedding and drawing.
1.173 +LEMON contains three algorithms for solving the minimum mean cycle problem:
1.174 +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
1.175 + \ref dasdan98minmeancycle.
1.176 +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
1.177 + version of Karp's algorithm \ref dasdan98minmeancycle.
1.178 +- \ref Howard "Howard"'s policy iteration algorithm
1.179 + \ref dasdan98minmeancycle.
1.180
1.181 -\image html planar.png
1.182 -\image latex planar.eps "Plane graph" width=\textwidth
1.183 +In practice, the Howard algorithm proved to be by far the most efficient
1.184 +one, though the best known theoretical bound on its running time is
1.185 +exponential.
1.186 +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
1.187 +O(n<sup>2</sup>+e), but the latter one is typically faster due to the
1.188 +applied early termination scheme.
1.189 */
1.190
1.191 /**
1.192 @@ -476,12 +530,36 @@
1.193 */
1.194
1.195 /**
1.196 -@defgroup spantree Minimum Spanning Tree Algorithms
1.197 +@defgroup graph_properties Connectivity and Other Graph Properties
1.198 @ingroup algs
1.199 -\brief Algorithms for finding minimum cost spanning trees and arborescences.
1.200 +\brief Algorithms for discovering the graph properties
1.201
1.202 -This group contains the algorithms for finding minimum cost spanning
1.203 -trees and arborescences.
1.204 +This group contains the algorithms for discovering the graph properties
1.205 +like connectivity, bipartiteness, euler property, simplicity etc.
1.206 +
1.207 +\image html connected_components.png
1.208 +\image latex connected_components.eps "Connected components" width=\textwidth
1.209 +*/
1.210 +
1.211 +/**
1.212 +@defgroup planar Planarity Embedding and Drawing
1.213 +@ingroup algs
1.214 +\brief Algorithms for planarity checking, embedding and drawing
1.215 +
1.216 +This group contains the algorithms for planarity checking,
1.217 +embedding and drawing.
1.218 +
1.219 +\image html planar.png
1.220 +\image latex planar.eps "Plane graph" width=\textwidth
1.221 +*/
1.222 +
1.223 +/**
1.224 +@defgroup approx Approximation Algorithms
1.225 +@ingroup algs
1.226 +\brief Approximation algorithms.
1.227 +
1.228 +This group contains the approximation and heuristic algorithms
1.229 +implemented in LEMON.
1.230 */
1.231
1.232 /**
1.233 @@ -494,15 +572,6 @@
1.234 */
1.235
1.236 /**
1.237 -@defgroup approx Approximation Algorithms
1.238 -@ingroup algs
1.239 -\brief Approximation algorithms.
1.240 -
1.241 -This group contains the approximation and heuristic algorithms
1.242 -implemented in LEMON.
1.243 -*/
1.244 -
1.245 -/**
1.246 @defgroup gen_opt_group General Optimization Tools
1.247 \brief This group contains some general optimization frameworks
1.248 implemented in LEMON.
1.249 @@ -512,13 +581,16 @@
1.250 */
1.251
1.252 /**
1.253 -@defgroup lp_group Lp and Mip Solvers
1.254 +@defgroup lp_group LP and MIP Solvers
1.255 @ingroup gen_opt_group
1.256 -\brief Lp and Mip solver interfaces for LEMON.
1.257 +\brief LP and MIP solver interfaces for LEMON.
1.258
1.259 -This group contains Lp and Mip solver interfaces for LEMON. The
1.260 -various LP solvers could be used in the same manner with this
1.261 -interface.
1.262 +This group contains LP and MIP solver interfaces for LEMON.
1.263 +Various LP solvers could be used in the same manner with this
1.264 +high-level interface.
1.265 +
1.266 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.267 +\ref cplex, \ref soplex.
1.268 */
1.269
1.270 /**
1.271 @@ -608,7 +680,7 @@
1.272 */
1.273
1.274 /**
1.275 -@defgroup dimacs_group DIMACS format
1.276 +@defgroup dimacs_group DIMACS Format
1.277 @ingroup io_group
1.278 \brief Read and write files in DIMACS format
1.279
1.280 @@ -657,8 +729,8 @@
1.281 @ingroup concept
1.282 \brief Skeleton and concept checking classes for graph structures
1.283
1.284 -This group contains the skeletons and concept checking classes of LEMON's
1.285 -graph structures and helper classes used to implement these.
1.286 +This group contains the skeletons and concept checking classes of
1.287 +graph structures.
1.288 */
1.289
1.290 /**
1.291 @@ -670,6 +742,15 @@
1.292 */
1.293
1.294 /**
1.295 +@defgroup tools Standalone Utility Applications
1.296 +
1.297 +Some utility applications are listed here.
1.298 +
1.299 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.300 +them, as well.
1.301 +*/
1.302 +
1.303 +/**
1.304 \anchor demoprograms
1.305
1.306 @defgroup demos Demo Programs
1.307 @@ -681,13 +762,4 @@
1.308 <tt>make check</tt> commands.
1.309 */
1.310
1.311 -/**
1.312 -@defgroup tools Standalone Utility Applications
1.313 -
1.314 -Some utility applications are listed here.
1.315 -
1.316 -The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.317 -them, as well.
1.318 -*/
1.319 -
1.320 }