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