1.1 --- a/doc/groups.dox Tue Dec 20 17:44:38 2011 +0100
1.2 +++ b/doc/groups.dox Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -226,14 +226,6 @@
1.13 */
1.14
1.15 /**
1.16 -@defgroup matrices Matrices
1.17 -@ingroup datas
1.18 -\brief Two dimensional data storages implemented in LEMON.
1.19 -
1.20 -This group contains two dimensional data storages implemented in LEMON.
1.21 -*/
1.22 -
1.23 -/**
1.24 @defgroup paths Path Structures
1.25 @ingroup datas
1.26 \brief %Path structures implemented in LEMON.
1.27 @@ -246,7 +238,36 @@
1.28 efficient to have e.g. the Dijkstra algorithm to store its result in
1.29 any kind of path structure.
1.30
1.31 -\sa lemon::concepts::Path
1.32 +\sa \ref concepts::Path "Path concept"
1.33 +*/
1.34 +
1.35 +/**
1.36 +@defgroup heaps Heap Structures
1.37 +@ingroup datas
1.38 +\brief %Heap structures implemented in LEMON.
1.39 +
1.40 +This group contains the heap structures implemented in LEMON.
1.41 +
1.42 +LEMON provides several heap classes. They are efficient implementations
1.43 +of the abstract data type \e priority \e queue. They store items with
1.44 +specified values called \e priorities in such a way that finding and
1.45 +removing the item with minimum priority are efficient.
1.46 +The basic operations are adding and erasing items, changing the priority
1.47 +of an item, etc.
1.48 +
1.49 +Heaps are crucial in several algorithms, such as Dijkstra and Prim.
1.50 +The heap implementations have the same interface, thus any of them can be
1.51 +used easily in such algorithms.
1.52 +
1.53 +\sa \ref concepts::Heap "Heap concept"
1.54 +*/
1.55 +
1.56 +/**
1.57 +@defgroup matrices Matrices
1.58 +@ingroup datas
1.59 +\brief Two dimensional data storages implemented in LEMON.
1.60 +
1.61 +This group contains two dimensional data storages implemented in LEMON.
1.62 */
1.63
1.64 /**
1.65 @@ -259,6 +280,28 @@
1.66 */
1.67
1.68 /**
1.69 +@defgroup geomdat Geometric Data Structures
1.70 +@ingroup auxdat
1.71 +\brief Geometric data structures implemented in LEMON.
1.72 +
1.73 +This group contains geometric data structures implemented in LEMON.
1.74 +
1.75 + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
1.76 + vector with the usual operations.
1.77 + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
1.78 + rectangular bounding box of a set of \ref lemon::dim2::Point
1.79 + "dim2::Point"'s.
1.80 +*/
1.81 +
1.82 +/**
1.83 +@defgroup matrices Matrices
1.84 +@ingroup auxdat
1.85 +\brief Two dimensional data storages implemented in LEMON.
1.86 +
1.87 +This group contains two dimensional data storages implemented in LEMON.
1.88 +*/
1.89 +
1.90 +/**
1.91 @defgroup algs Algorithms
1.92 \brief This group contains the several algorithms
1.93 implemented in LEMON.
1.94 @@ -273,7 +316,8 @@
1.95 \brief Common graph search algorithms.
1.96
1.97 This group contains the common graph search algorithms, namely
1.98 -\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
1.99 +\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
1.100 +\ref clrs01algorithms.
1.101 */
1.102
1.103 /**
1.104 @@ -281,7 +325,8 @@
1.105 @ingroup algs
1.106 \brief Algorithms for finding shortest paths.
1.107
1.108 -This group contains the algorithms for finding shortest paths in digraphs.
1.109 +This group contains the algorithms for finding shortest paths in digraphs
1.110 +\ref clrs01algorithms.
1.111
1.112 - \ref Dijkstra algorithm for finding shortest paths from a source node
1.113 when all arc lengths are non-negative.
1.114 @@ -298,12 +343,21 @@
1.115 */
1.116
1.117 /**
1.118 +@defgroup spantree Minimum Spanning Tree Algorithms
1.119 +@ingroup algs
1.120 +\brief Algorithms for finding minimum cost spanning trees and arborescences.
1.121 +
1.122 +This group contains the algorithms for finding minimum cost spanning
1.123 +trees and arborescences \ref clrs01algorithms.
1.124 +*/
1.125 +
1.126 +/**
1.127 @defgroup max_flow Maximum Flow Algorithms
1.128 @ingroup algs
1.129 \brief Algorithms for finding maximum flows.
1.130
1.131 This group contains the algorithms for finding maximum flows and
1.132 -feasible circulations.
1.133 +feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
1.134
1.135 The \e maximum \e flow \e problem is to find a flow of maximum value between
1.136 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
1.137 @@ -318,17 +372,21 @@
1.138 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
1.139
1.140 LEMON contains several algorithms for solving maximum flow problems:
1.141 -- \ref EdmondsKarp Edmonds-Karp algorithm.
1.142 -- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
1.143 -- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
1.144 -- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
1.145 +- \ref EdmondsKarp Edmonds-Karp algorithm
1.146 + \ref edmondskarp72theoretical.
1.147 +- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
1.148 + \ref goldberg88newapproach.
1.149 +- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
1.150 + \ref dinic70algorithm, \ref sleator83dynamic.
1.151 +- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
1.152 + \ref goldberg88newapproach, \ref sleator83dynamic.
1.153
1.154 -In most cases the \ref Preflow "Preflow" algorithm provides the
1.155 +In most cases the \ref Preflow algorithm provides the
1.156 fastest method for computing a maximum flow. All implementations
1.157 also provide functions to query the minimum cut, which is the dual
1.158 problem of maximum flow.
1.159
1.160 -\ref Circulation is a preflow push-relabel algorithm implemented directly
1.161 +\ref Circulation is a preflow push-relabel algorithm implemented directly
1.162 for finding feasible circulations, which is a somewhat different problem,
1.163 but it is strongly related to maximum flow.
1.164 For more information, see \ref Circulation.
1.165 @@ -341,18 +399,20 @@
1.166 \brief Algorithms for finding minimum cost flows and circulations.
1.167
1.168 This group contains the algorithms for finding minimum cost flows and
1.169 -circulations. For more information about this problem and its dual
1.170 -solution see \ref min_cost_flow "Minimum Cost Flow Problem".
1.171 +circulations \ref amo93networkflows. For more information about this
1.172 +problem and its dual solution, see \ref min_cost_flow
1.173 +"Minimum Cost Flow Problem".
1.174
1.175 LEMON contains several algorithms for this problem.
1.176 - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.177 - pivot strategies.
1.178 - - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.179 - cost scaling.
1.180 - - \ref CapacityScaling Successive Shortest %Path algorithm with optional
1.181 - capacity scaling.
1.182 - - \ref CancelAndTighten The Cancel and Tighten algorithm.
1.183 - - \ref CycleCanceling Cycle-Canceling algorithms.
1.184 + pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
1.185 + - \ref CostScaling Cost Scaling algorithm based on push/augment and
1.186 + relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
1.187 + \ref bunnagel98efficient.
1.188 + - \ref CapacityScaling Capacity Scaling algorithm based on the successive
1.189 + shortest path method \ref edmondskarp72theoretical.
1.190 + - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
1.191 + strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
1.192
1.193 In general NetworkSimplex is the most efficient implementation,
1.194 but in special cases other algorithms could be faster.
1.195 @@ -375,7 +435,7 @@
1.196 cut is the \f$X\f$ solution of the next optimization problem:
1.197
1.198 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
1.199 - \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
1.200 + \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
1.201
1.202 LEMON contains several algorithms related to minimum cut problems:
1.203
1.204 @@ -391,27 +451,40 @@
1.205 */
1.206
1.207 /**
1.208 -@defgroup graph_properties Connectivity and Other Graph Properties
1.209 +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
1.210 @ingroup algs
1.211 -\brief Algorithms for discovering the graph properties
1.212 +\brief Algorithms for finding minimum mean cycles.
1.213
1.214 -This group contains the algorithms for discovering the graph properties
1.215 -like connectivity, bipartiteness, euler property, simplicity etc.
1.216 +This group contains the algorithms for finding minimum mean cycles
1.217 +\ref clrs01algorithms, \ref amo93networkflows.
1.218
1.219 -\image html edge_biconnected_components.png
1.220 -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
1.221 -*/
1.222 +The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.223 +of minimum mean length (cost) in a digraph.
1.224 +The mean length of a cycle is the average length of its arcs, i.e. the
1.225 +ratio between the total length of the cycle and the number of arcs on it.
1.226
1.227 -/**
1.228 -@defgroup planar Planarity Embedding and Drawing
1.229 -@ingroup algs
1.230 -\brief Algorithms for planarity checking, embedding and drawing
1.231 +This problem has an important connection to \e conservative \e length
1.232 +\e functions, too. A length function on the arcs of a digraph is called
1.233 +conservative if and only if there is no directed cycle of negative total
1.234 +length. For an arbitrary length function, the negative of the minimum
1.235 +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
1.236 +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
1.237 +function.
1.238
1.239 -This group contains the algorithms for planarity checking,
1.240 -embedding and drawing.
1.241 +LEMON contains three algorithms for solving the minimum mean cycle problem:
1.242 +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
1.243 + \ref dasdan98minmeancycle.
1.244 +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
1.245 + version of Karp's algorithm \ref dasdan98minmeancycle.
1.246 +- \ref Howard "Howard"'s policy iteration algorithm
1.247 + \ref dasdan98minmeancycle.
1.248
1.249 -\image html planar.png
1.250 -\image latex planar.eps "Plane graph" width=\textwidth
1.251 +In practice, the Howard algorithm proved to be by far the most efficient
1.252 +one, though the best known theoretical bound on its running time is
1.253 +exponential.
1.254 +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
1.255 +O(n<sup>2</sup>+e), but the latter one is typically faster due to the
1.256 +applied early termination scheme.
1.257 */
1.258
1.259 /**
1.260 @@ -449,18 +522,49 @@
1.261 - \ref MaxWeightedPerfectMatching
1.262 Edmond's blossom shrinking algorithm for calculating maximum weighted
1.263 perfect matching in general graphs.
1.264 +- \ref MaxFractionalMatching Push-relabel algorithm for calculating
1.265 + maximum cardinality fractional matching in general graphs.
1.266 +- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
1.267 + maximum weighted fractional matching in general graphs.
1.268 +- \ref MaxWeightedPerfectFractionalMatching
1.269 + Augmenting path algorithm for calculating maximum weighted
1.270 + perfect fractional matching in general graphs.
1.271
1.272 -\image html bipartite_matching.png
1.273 -\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
1.274 +\image html matching.png
1.275 +\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
1.276 */
1.277
1.278 /**
1.279 -@defgroup spantree Minimum Spanning Tree Algorithms
1.280 +@defgroup graph_properties Connectivity and Other Graph Properties
1.281 @ingroup algs
1.282 -\brief Algorithms for finding minimum cost spanning trees and arborescences.
1.283 +\brief Algorithms for discovering the graph properties
1.284
1.285 -This group contains the algorithms for finding minimum cost spanning
1.286 -trees and arborescences.
1.287 +This group contains the algorithms for discovering the graph properties
1.288 +like connectivity, bipartiteness, euler property, simplicity etc.
1.289 +
1.290 +\image html connected_components.png
1.291 +\image latex connected_components.eps "Connected components" width=\textwidth
1.292 +*/
1.293 +
1.294 +/**
1.295 +@defgroup planar Planarity Embedding and Drawing
1.296 +@ingroup algs
1.297 +\brief Algorithms for planarity checking, embedding and drawing
1.298 +
1.299 +This group contains the algorithms for planarity checking,
1.300 +embedding and drawing.
1.301 +
1.302 +\image html planar.png
1.303 +\image latex planar.eps "Plane graph" width=\textwidth
1.304 +*/
1.305 +
1.306 +/**
1.307 +@defgroup approx Approximation Algorithms
1.308 +@ingroup algs
1.309 +\brief Approximation algorithms.
1.310 +
1.311 +This group contains the approximation and heuristic algorithms
1.312 +implemented in LEMON.
1.313 */
1.314
1.315 /**
1.316 @@ -473,15 +577,6 @@
1.317 */
1.318
1.319 /**
1.320 -@defgroup approx Approximation Algorithms
1.321 -@ingroup algs
1.322 -\brief Approximation algorithms.
1.323 -
1.324 -This group contains the approximation and heuristic algorithms
1.325 -implemented in LEMON.
1.326 -*/
1.327 -
1.328 -/**
1.329 @defgroup gen_opt_group General Optimization Tools
1.330 \brief This group contains some general optimization frameworks
1.331 implemented in LEMON.
1.332 @@ -491,13 +586,16 @@
1.333 */
1.334
1.335 /**
1.336 -@defgroup lp_group Lp and Mip Solvers
1.337 +@defgroup lp_group LP and MIP Solvers
1.338 @ingroup gen_opt_group
1.339 -\brief Lp and Mip solver interfaces for LEMON.
1.340 +\brief LP and MIP solver interfaces for LEMON.
1.341
1.342 -This group contains Lp and Mip solver interfaces for LEMON. The
1.343 -various LP solvers could be used in the same manner with this
1.344 -interface.
1.345 +This group contains LP and MIP solver interfaces for LEMON.
1.346 +Various LP solvers could be used in the same manner with this
1.347 +high-level interface.
1.348 +
1.349 +The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
1.350 +\ref cplex, \ref soplex.
1.351 */
1.352
1.353 /**
1.354 @@ -587,7 +685,7 @@
1.355 */
1.356
1.357 /**
1.358 -@defgroup dimacs_group DIMACS format
1.359 +@defgroup dimacs_group DIMACS Format
1.360 @ingroup io_group
1.361 \brief Read and write files in DIMACS format
1.362
1.363 @@ -636,8 +734,8 @@
1.364 @ingroup concept
1.365 \brief Skeleton and concept checking classes for graph structures
1.366
1.367 -This group contains the skeletons and concept checking classes of LEMON's
1.368 -graph structures and helper classes used to implement these.
1.369 +This group contains the skeletons and concept checking classes of
1.370 +graph structures.
1.371 */
1.372
1.373 /**
1.374 @@ -649,6 +747,15 @@
1.375 */
1.376
1.377 /**
1.378 +@defgroup tools Standalone Utility Applications
1.379 +
1.380 +Some utility applications are listed here.
1.381 +
1.382 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.383 +them, as well.
1.384 +*/
1.385 +
1.386 +/**
1.387 \anchor demoprograms
1.388
1.389 @defgroup demos Demo Programs
1.390 @@ -660,13 +767,4 @@
1.391 <tt>make check</tt> commands.
1.392 */
1.393
1.394 -/**
1.395 -@defgroup tools Standalone Utility Applications
1.396 -
1.397 -Some utility applications are listed here.
1.398 -
1.399 -The standard compilation procedure (<tt>./configure;make</tt>) will compile
1.400 -them, as well.
1.401 -*/
1.402 -
1.403 }