Changes in doc/groups.dox [1023:e0cef67fe565:710:8b0df68370a4] in lemon

File:

• doc/groups.dox (modified) (19 diffs)

doc/groups.dox

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2009
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -227 +227 @@
 
 /**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
 @defgroup paths Path Structures
 @ingroup datas
@@ -239 +247 @@
 any kind of path structure.
 
-\sa \ref concepts::Path "Path concept"
-*/
-
-/**
-@defgroup heaps Heap Structures
-@ingroup datas
-\brief %Heap structures implemented in LEMON.
-
-This group contains the heap structures implemented in LEMON.
-
-LEMON provides several heap classes. They are efficient implementations
-of the abstract data type \e priority \e queue. They store items with
-specified values called \e priorities in such a way that finding and
-removing the item with minimum priority are efficient.
-The basic operations are adding and erasing items, changing the priority
-of an item, etc.
-
-Heaps are crucial in several algorithms, such as Dijkstra and Prim.
-The heap implementations have the same interface, thus any of them can be
-used easily in such algorithms.
-
-\sa \ref concepts::Heap "Heap concept"
+\sa lemon::concepts::Path
 */
 
@@ -273 +260 @@
 
 /**
-@defgroup geomdat Geometric Data Structures
-@ingroup auxdat
-\brief Geometric data structures implemented in LEMON.
-
-This group contains geometric data structures implemented in LEMON.
-
- - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
-   vector with the usual operations.
- - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
-   rectangular bounding box of a set of \ref lemon::dim2::Point
-   "dim2::Point"'s.
-*/
-
-/**
-@defgroup matrices Matrices
-@ingroup auxdat
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
 @defgroup algs Algorithms
 \brief This group contains the several algorithms
@@ -309 +274 @@
 
 This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
-\ref clrs01algorithms.
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 */
 
@@ -318 +282 @@
 \brief Algorithms for finding shortest paths.
 
-This group contains the algorithms for finding shortest paths in digraphs
-\ref clrs01algorithms.
+This group contains the algorithms for finding shortest paths in digraphs.
 
  - \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -336 +299 @@
 
 /**
-@defgroup spantree Minimum Spanning Tree Algorithms
-@ingroup algs
-\brief Algorithms for finding minimum cost spanning trees and arborescences.
-
-This group contains the algorithms for finding minimum cost spanning
-trees and arborescences \ref clrs01algorithms.
-*/
-
-/**
 @defgroup max_flow Maximum Flow Algorithms
 @ingroup algs
@@ -350 +304 @@
 
 This group contains the algorithms for finding maximum flows and
-feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
+feasible circulations.
 
 The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -365 +319 @@
 
 LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm
-  \ref edmondskarp72theoretical.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
-  \ref goldberg88newapproach.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
-  \ref dinic70algorithm, \ref sleator83dynamic.
-- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
-  \ref goldberg88newapproach, \ref sleator83dynamic.
-
-In most cases the \ref Preflow algorithm provides the
+- \ref EdmondsKarp Edmonds-Karp algorithm.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
+- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
+
+In most cases the \ref Preflow "Preflow" algorithm provides the
 fastest method for computing a maximum flow. All implementations
 also provide functions to query the minimum cut, which is the dual
 problem of maximum flow.
 
-\ref Circulation is a preflow push-relabel algorithm implemented directly
+\ref Circulation is a preflow push-relabel algorithm implemented directly 
 for finding feasible circulations, which is a somewhat different problem,
 but it is strongly related to maximum flow.
@@ -392 +342 @@
 
 This group contains the algorithms for finding minimum cost flows and
-circulations \ref amo93networkflows. For more information about this
-problem and its dual solution, see \ref min_cost_flow
-"Minimum Cost Flow Problem".
+circulations. For more information about this problem and its dual
+solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 
 LEMON contains several algorithms for this problem.
  - \ref NetworkSimplex Primal Network Simplex algorithm with various
-   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
- - \ref CostScaling Cost Scaling algorithm based on push/augment and
-   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
-   \ref bunnagel98efficient.
- - \ref CapacityScaling Capacity Scaling algorithm based on the successive
-   shortest path method \ref edmondskarp72theoretical.
- - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
-   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
-
-In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
-implementations, but the other two algorithms could be faster in special cases.
+   pivot strategies.
+ - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
+   cost scaling.
+ - \ref CapacityScaling Successive Shortest %Path algorithm with optional
+   capacity scaling.
+ - \ref CancelAndTighten The Cancel and Tighten algorithm.
+ - \ref CycleCanceling Cycle-Canceling algorithms.
+
+In general NetworkSimplex is the most efficient implementation,
+but in special cases other algorithms could be faster.
 For example, if the total supply and/or capacities are rather small,
-\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
+CapacityScaling is usually the fastest algorithm (without effective scaling).
 */
 
@@ -428 +376 @@
 
 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
-    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
+    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
 
 LEMON contains several algorithms related to minimum cut problems:
@@ -444 +392 @@
 
 /**
-@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
-@ingroup algs
-\brief Algorithms for finding minimum mean cycles.
-
-This group contains the algorithms for finding minimum mean cycles
-\ref clrs01algorithms, \ref amo93networkflows.
-
-The \e minimum \e mean \e cycle \e problem is to find a directed cycle
-of minimum mean length (cost) in a digraph.
-The mean length of a cycle is the average length of its arcs, i.e. the
-ratio between the total length of the cycle and the number of arcs on it.
-
-This problem has an important connection to \e conservative \e length
-\e functions, too. A length function on the arcs of a digraph is called
-conservative if and only if there is no directed cycle of negative total
-length. For an arbitrary length function, the negative of the minimum
-cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
-arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
-function.
-
-LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
-  \ref dasdan98minmeancycle.
-- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
-  version of Karp's algorithm \ref dasdan98minmeancycle.
-- \ref HowardMmc Howard's policy iteration algorithm
-  \ref dasdan98minmeancycle.
-
-In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
-most efficient one, though the best known theoretical bound on its running
-time is exponential.
-Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
-run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
-typically faster due to the applied early termination scheme.
+@defgroup graph_properties Connectivity and Other Graph Properties
+@ingroup algs
+\brief Algorithms for discovering the graph properties
+
+This group contains the algorithms for discovering the graph properties
+like connectivity, bipartiteness, euler property, simplicity etc.
+
+\image html edge_biconnected_components.png
+\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
+*/
+
+/**
+@defgroup planar Planarity Embedding and Drawing
+@ingroup algs
+\brief Algorithms for planarity checking, embedding and drawing
+
+This group contains the algorithms for planarity checking,
+embedding and drawing.
+
+\image html planar.png
+\image latex planar.eps "Plane graph" width=\textwidth
 */
 
@@ -515 +450 @@
   Edmond's blossom shrinking algorithm for calculating maximum weighted
   perfect matching in general graphs.
-- \ref MaxFractionalMatching Push-relabel algorithm for calculating
-  maximum cardinality fractional matching in general graphs.
-- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
-  maximum weighted fractional matching in general graphs.
-- \ref MaxWeightedPerfectFractionalMatching
-  Augmenting path algorithm for calculating maximum weighted
-  perfect fractional matching in general graphs.
-
-\image html matching.png
-\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
-*/
-
-/**
-@defgroup graph_properties Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
-
-\image html connected_components.png
-\image latex connected_components.eps "Connected components" width=\textwidth
-*/
-
-/**
-@defgroup planar Planar Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group contains the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
-*/
-
-/**
-@defgroup approx_algs Approximation Algorithms
+
+\image html bipartite_matching.png
+\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
+*/
+
+/**
+@defgroup spantree Minimum Spanning Tree Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences.
+*/
+
+/**
+@defgroup auxalg Auxiliary Algorithms
+@ingroup algs
+\brief Auxiliary algorithms implemented in LEMON.
+
+This group contains some algorithms implemented in LEMON
+in order to make it easier to implement complex algorithms.
+*/
+
+/**
+@defgroup approx Approximation Algorithms
 @ingroup algs
 \brief Approximation algorithms.
@@ -558 +480 @@
 This group contains the approximation and heuristic algorithms
 implemented in LEMON.
-
-<b>Maximum Clique Problem</b>
-  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
-    Grosso, Locatelli, and Pullan.
-*/
-
-/**
-@defgroup auxalg Auxiliary Algorithms
-@ingroup algs
-\brief Auxiliary algorithms implemented in LEMON.
-
-This group contains some algorithms implemented in LEMON
-in order to make it easier to implement complex algorithms.
 */
 
@@ -583 +492 @@
 
 /**
-@defgroup lp_group LP and MIP Solvers
+@defgroup lp_group Lp and Mip Solvers
 @ingroup gen_opt_group
-\brief LP and MIP solver interfaces for LEMON.
-
-This group contains LP and MIP solver interfaces for LEMON.
-Various LP solvers could be used in the same manner with this
-high-level interface.
-
-The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
-\ref cplex, \ref soplex.
+\brief Lp and Mip solver interfaces for LEMON.
+
+This group contains Lp and Mip solver interfaces for LEMON. The
+various LP solvers could be used in the same manner with this
+interface.
 */
 
@@ -682 +588 @@
 
 /**
-@defgroup dimacs_group DIMACS Format
+@defgroup dimacs_group DIMACS format
 @ingroup io_group
 \brief Read and write files in DIMACS format
@@ -731 +637 @@
 \brief Skeleton and concept checking classes for graph structures
 
-This group contains the skeletons and concept checking classes of
-graph structures.
+This group contains the skeletons and concept checking classes of LEMON's
+graph structures and helper classes used to implement these.
 */
 
@@ -744 +650 @@
 
 /**
+\anchor demoprograms
+
+@defgroup demos Demo Programs
+
+Some demo programs are listed here. Their full source codes can be found in
+the \c demo subdirectory of the source tree.
+
+In order to compile them, use the <tt>make demo</tt> or the
+<tt>make check</tt> commands.
+*/
+
+/**
 @defgroup tools Standalone Utility Applications
 
@@ -752 +670 @@
 */
 
-/**
-\anchor demoprograms
-
-@defgroup demos Demo Programs
-
-Some demo programs are listed here. Their full source codes can be found in
-the \c demo subdirectory of the source tree.
-
-In order to compile them, use the <tt>make demo</tt> or the
-<tt>make check</tt> commands.
-*/
-
 }