Changes in doc/groups.dox [844:c01a98ce01fd:318:1e2d6ca80793] in lemon

File:

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

doc/groups.dox

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -17 +17 @@
  */
 
-namespace lemon {
-
 /**
 @defgroup datas Data Structures
-This group contains the several data structures implemented in LEMON.
+This group describes the several data structures implemented in LEMON.
 */
 
@@ -63 +61 @@
 
 /**
-@defgroup graph_adaptors Adaptor Classes for Graphs
+@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 @ingroup graphs
-\brief Adaptor classes for digraphs and graphs
-
-This group contains several useful adaptor classes for digraphs and graphs.
-
-The main parts of LEMON are the different graph structures, generic
-graph algorithms, graph concepts, which couple them, and graph
-adaptors. While the previous notions are more or less clear, the
-latter one needs further explanation. Graph adaptors are graph classes
-which serve for considering graph structures in different ways.
-
-A short example makes this much clearer.  Suppose that we have an
-instance \c g of a directed graph type, say ListDigraph and an algorithm
-\code
-template <typename Digraph>
-int algorithm(const Digraph&);
-\endcode
-is needed to run on the reverse oriented graph.  It may be expensive
-(in time or in memory usage) to copy \c g with the reversed
-arcs.  In this case, an adaptor class is used, which (according
-to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
-The adaptor uses the original digraph structure and digraph operations when
-methods of the reversed oriented graph are called.  This means that the adaptor
-have minor memory usage, and do not perform sophisticated algorithmic
-actions.  The purpose of it is to give a tool for the cases when a
-graph have to be used in a specific alteration.  If this alteration is
-obtained by a usual construction like filtering the node or the arc set or
-considering a new orientation, then an adaptor is worthwhile to use.
-To come back to the reverse oriented graph, in this situation
-\code
-template<typename Digraph> class ReverseDigraph;
-\endcode
-template class can be used. The code looks as follows
-\code
-ListDigraph g;
-ReverseDigraph<ListDigraph> rg(g);
-int result = algorithm(rg);
-\endcode
-During running the algorithm, the original digraph \c g is untouched.
-This techniques give rise to an elegant code, and based on stable
-graph adaptors, complex algorithms can be implemented easily.
-
-In flow, circulation and matching problems, the residual
-graph is of particular importance. Combining an adaptor implementing
-this with shortest path algorithms or minimum mean cycle algorithms,
-a range of weighted and cardinality optimization algorithms can be
-obtained. For other examples, the interested user is referred to the
-detailed documentation of particular adaptors.
-
-The behavior of graph adaptors can be very different. Some of them keep
-capabilities of the original graph while in other cases this would be
-meaningless. This means that the concepts that they meet depend
-on the graph adaptor, and the wrapped graph.
-For example, if an arc of a reversed digraph is deleted, this is carried
-out by deleting the corresponding arc of the original digraph, thus the
-adaptor modifies the original digraph.
-However in case of a residual digraph, this operation has no sense.
-
-Let us stand one more example here to simplify your work.
-ReverseDigraph has constructor
-\code
-ReverseDigraph(Digraph& digraph);
-\endcode
-This means that in a situation, when a <tt>const %ListDigraph&</tt>
-reference to a graph is given, then it have to be instantiated with
-<tt>Digraph=const %ListDigraph</tt>.
-\code
-int algorithm1(const ListDigraph& g) {
-  ReverseDigraph<const ListDigraph> rg(g);
-  return algorithm2(rg);
-}
-\endcode
+\brief Graph types between real graphs and graph adaptors.
+
+This group describes some graph types between real graphs and graph adaptors.
+These classes wrap graphs to give new functionality as the adaptors do it.
+On the other hand they are not light-weight structures as the adaptors.
 */
 
@@ -143 +75 @@
 \brief Map structures implemented in LEMON.
 
-This group contains the map structures implemented in LEMON.
+This group describes the map structures implemented in LEMON.
 
 LEMON provides several special purpose maps and map adaptors that e.g. combine
@@ -156 +88 @@
 \brief Special graph-related maps.
 
-This group contains maps that are specifically designed to assign
-values to the nodes and arcs/edges of graphs.
-
-If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
-\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
+This group describes maps that are specifically designed to assign
+values to the nodes and arcs of graphs.
 */
 
@@ -168 +97 @@
 \brief Tools to create new maps from existing ones
 
-This group contains map adaptors that are used to create "implicit"
+This group describes map adaptors that are used to create "implicit"
 maps from other maps.
 
-Most of them are \ref concepts::ReadMap "read-only maps".
+Most of them are \ref lemon::concepts::ReadMap "read-only maps".
 They can make arithmetic and logical operations between one or two maps
 (negation, shifting, addition, multiplication, logical 'and', 'or',
@@ -227 +156 @@
 
 /**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group describes two dimensional data storages implemented in LEMON.
+*/
+
+/**
 @defgroup paths Path Structures
 @ingroup datas
 \brief %Path structures implemented in LEMON.
 
-This group contains the path structures implemented in LEMON.
+This group describes the path structures implemented in LEMON.
 
 LEMON provides flexible data structures to work with paths.
@@ -247 +184 @@
 \brief Auxiliary data structures implemented in LEMON.
 
-This group contains some data structures implemented in LEMON in
+This group describes some data structures implemented in LEMON in
 order to make it easier to implement combinatorial algorithms.
 */
@@ -253 +190 @@
 /**
 @defgroup algs Algorithms
-\brief This group contains the several algorithms
+\brief This group describes the several algorithms
 implemented in LEMON.
 
-This group contains the several algorithms
+This group describes the several algorithms
 implemented in LEMON.
 */
@@ -265 +202 @@
 \brief Common graph search algorithms.
 
-This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+This group describes the common graph search algorithms like
+Breadth-First Search (BFS) and Depth-First Search (DFS).
 */
 
@@ -274 +211 @@
 \brief Algorithms for finding shortest paths.
 
-This group contains the algorithms for finding shortest paths in digraphs.
-
- - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 
-   source node when all arc lengths are non-negative.
- - \ref Suurballe A successive shortest path algorithm for finding
-   arc-disjoint paths between two nodes having minimum total length.
+This group describes the algorithms for finding shortest paths in graphs.
 */
 
@@ -287 +219 @@
 \brief Algorithms for finding maximum flows.
 
-This group contains the algorithms for finding maximum flows and
+This group describes the algorithms for finding maximum flows and
 feasible circulations.
 
-The \e maximum \e flow \e problem is to find a flow of maximum value between
-a single source and a single target. Formally, there is a \f$G=(V,A)\f$
-digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
-\f$s, t \in V\f$ source and target nodes.
-A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
-following optimization problem.
-
-\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
-\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
-    \quad \forall u\in V\setminus\{s,t\} \f]
-\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
-
-\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
-Tarjan for solving this problem. It also provides functions to query the
-minimum cut, which is the dual problem of maximum flow.
-
-
-\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.
-For more information, see \ref Circulation.
-*/
-
-/**
-@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
+The maximum flow problem is to find a flow between a single source and
+a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
+directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
+function and given \f$s, t \in V\f$ source and target node. The
+maximum flow is the \f$f_a\f$ solution of the next optimization problem:
+
+\f[ 0 \le f_a \le c_a \f]
+\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
+\qquad \forall u \in V \setminus \{s,t\}\f]
+\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
+
+LEMON contains several algorithms for solving maximum flow problems:
+- \ref lemon::EdmondsKarp "Edmonds-Karp"
+- \ref lemon::Preflow "Goldberg's Preflow algorithm"
+- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
+- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
+
+In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
+fastest method to compute the maximum flow. All impelementations
+provides functions to query the minimum cut, which is the dual linear
+programming problem of the maximum flow.
+*/
+
+/**
+@defgroup min_cost_flow Minimum Cost Flow Algorithms
 @ingroup algs
 
 \brief Algorithms for finding minimum cost flows and circulations.
 
-This group contains the algorithms for finding minimum cost flows and
-circulations. For more information about this problem and its dual
-solution see \ref min_cost_flow "Minimum Cost Flow Problem".
-
-\ref NetworkSimplex is an efficient implementation of the primal Network
-Simplex algorithm for finding minimum cost flows. It also provides dual
-solution (node potentials), if an optimal flow is found.
+This group describes the algorithms for finding minimum cost flows and
+circulations.
 */
 
@@ -334 +261 @@
 \brief Algorithms for finding minimum cut in graphs.
 
-This group contains the algorithms for finding minimum cut in graphs.
-
-The \e minimum \e cut \e problem is to find a non-empty and non-complete
-\f$X\f$ subset of the nodes with minimum overall capacity on
-outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
-\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
+This group describes the algorithms for finding minimum cut in graphs.
+
+The minimum cut problem is to find a non-empty and non-complete
+\f$X\f$ subset of the vertices with minimum overall capacity on
+outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
+\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 cut is the \f$X\f$ solution of the next optimization problem:
 
 \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}c_{uv}\f]
 
 LEMON contains several algorithms related to minimum cut problems:
 
-- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
-  in directed graphs.
-- \ref GomoryHu "Gomory-Hu tree computation" for calculating
-  all-pairs minimum cut in undirected graphs.
+- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
+  in directed graphs
+- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
+  calculate minimum cut in undirected graphs
+- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
+  pairs minimum cut in undirected graphs
 
 If you want to find minimum cut just between two distinict nodes,
-see the \ref max_flow "maximum flow problem".
-*/
-
-/**
-@defgroup graph_properties Connectivity and Other Graph Properties
+please see the \ref max_flow "Maximum Flow page".
+*/
+
+/**
+@defgroup graph_prop Connectivity and Other Graph Properties
 @ingroup algs
 \brief Algorithms for discovering the graph properties
 
-This group contains the algorithms for discovering the graph properties
+This group describes the algorithms for discovering the graph properties
 like connectivity, bipartiteness, euler property, simplicity etc.
 
@@ -369 +298 @@
 
 /**
+@defgroup planar Planarity Embedding and Drawing
+@ingroup algs
+\brief Algorithms for planarity checking, embedding and drawing
+
+This group describes the algorithms for planarity checking,
+embedding and drawing.
+
+\image html planar.png
+\image latex planar.eps "Plane graph" width=\textwidth
+*/
+
+/**
 @defgroup matching Matching Algorithms
 @ingroup algs
 \brief Algorithms for finding matchings in graphs and bipartite graphs.
 
-This group contains the algorithms for calculating matchings in graphs.
-The general matching problem is finding a subset of the edges for which
-each node has at most one incident edge.
+This group contains algorithm objects and functions to calculate
+matchings in graphs and bipartite graphs. The general matching problem is
+finding a subset of the arcs which does not shares common endpoints.
 
 There are several different algorithms for calculate matchings in
-graphs. The goal of the matching optimization
-can be finding maximum cardinality, maximum weight or minimum cost
+graphs.  The matching problems in bipartite graphs are generally
+easier than in general graphs. The goal of the matching optimization
+can be the finding maximum cardinality, maximum weight or minimum cost
 matching. The search can be constrained to find perfect or
 maximum cardinality matching.
 
-The matching algorithms implemented in LEMON:
-- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
-  maximum cardinality matching in general graphs.
-- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
-  maximum weighted matching in general graphs.
-- \ref MaxWeightedPerfectMatching
-  Edmond's blossom shrinking algorithm for calculating maximum weighted
-  perfect matching in general graphs.
+LEMON contains the next algorithms:
+- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
+  augmenting path algorithm for calculate maximum cardinality matching in
+  bipartite graphs
+- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
+  algorithm for calculate maximum cardinality matching in bipartite graphs
+- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
+  Successive shortest path algorithm for calculate maximum weighted matching
+  and maximum weighted bipartite matching in bipartite graph
+- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
+  Successive shortest path algorithm for calculate minimum cost maximum
+  matching in bipartite graph
+- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
+  for calculate maximum cardinality matching in general graph
+- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
+  shrinking algorithm for calculate maximum weighted matching in general
+  graph
+- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
+  Edmond's blossom shrinking algorithm for calculate maximum weighted
+  perfect matching in general graph
 
 \image html bipartite_matching.png
@@ -399 +353 @@
 @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.
+\brief Algorithms for finding a minimum cost spanning tree in a graph.
+
+This group describes the algorithms for finding a minimum cost spanning
+tree in a graph
 */
 
@@ -410 +364 @@
 \brief Auxiliary algorithms implemented in LEMON.
 
-This group contains some algorithms implemented in LEMON
+This group describes some algorithms implemented in LEMON
 in order to make it easier to implement complex algorithms.
 */
 
 /**
+@defgroup approx Approximation Algorithms
+@ingroup algs
+\brief Approximation algorithms.
+
+This group describes the approximation and heuristic algorithms
+implemented in LEMON.
+*/
+
+/**
 @defgroup gen_opt_group General Optimization Tools
-\brief This group contains some general optimization frameworks
+\brief This group describes some general optimization frameworks
 implemented in LEMON.
 
-This group contains some general optimization frameworks
+This group describes some general optimization frameworks
 implemented in LEMON.
 */
@@ -428 +391 @@
 \brief Lp and Mip solver interfaces for LEMON.
 
-This group contains Lp and Mip solver interfaces for LEMON. The
+This group describes Lp and Mip solver interfaces for LEMON. The
 various LP solvers could be used in the same manner with this
 interface.
+*/
+
+/**
+@defgroup lp_utils Tools for Lp and Mip Solvers
+@ingroup lp_group
+\brief Helper tools to the Lp and Mip solvers.
+
+This group adds some helper tools to general optimization framework
+implemented in LEMON.
+*/
+
+/**
+@defgroup metah Metaheuristics
+@ingroup gen_opt_group
+\brief Metaheuristics for LEMON library.
+
+This group describes some metaheuristic optimization tools.
 */
 
@@ -445 +425 @@
 \brief Simple basic graph utilities.
 
-This group contains some simple basic graph utilities.
+This group describes some simple basic graph utilities.
 */
 
@@ -453 +433 @@
 \brief Tools for development, debugging and testing.
 
-This group contains several useful tools for development,
+This group describes several useful tools for development,
 debugging and testing.
 */
@@ -462 +442 @@
 \brief Simple tools for measuring the performance of algorithms.
 
-This group contains simple tools for measuring the performance
+This group describes simple tools for measuring the performance
 of algorithms.
 */
@@ -471 +451 @@
 \brief Exceptions defined in LEMON.
 
-This group contains the exceptions defined in LEMON.
+This group describes the exceptions defined in LEMON.
 */
 
@@ -478 +458 @@
 \brief Graph Input-Output methods
 
-This group contains the tools for importing and exporting graphs
+This group describes the tools for importing and exporting graphs
 and graph related data. Now it supports the \ref lgf-format
 "LEMON Graph Format", the \c DIMACS format and the encapsulated
@@ -485 +465 @@
 
 /**
-@defgroup lemon_io LEMON Graph Format
+@defgroup lemon_io LEMON Input-Output
 @ingroup io_group
 \brief Reading and writing LEMON Graph Format.
 
-This group contains methods for reading and writing
+This group describes methods for reading and writing
 \ref lgf-format "LEMON Graph Format".
 */
@@ -498 +478 @@
 \brief General \c EPS drawer and graph exporter
 
-This group contains general \c EPS drawing methods and special
+This group describes general \c EPS drawing methods and special
 graph exporting tools.
-*/
-
-/**
-@defgroup dimacs_group DIMACS format
-@ingroup io_group
-\brief Read and write files in DIMACS format
-
-Tools to read a digraph from or write it to a file in DIMACS format data.
-*/
-
-/**
-@defgroup nauty_group NAUTY Format
-@ingroup io_group
-\brief Read \e Nauty format
-
-Tool to read graphs from \e Nauty format data.
 */
 
@@ -522 +486 @@
 \brief Skeleton classes and concept checking classes
 
-This group contains the data/algorithm skeletons and concept checking
+This group describes the data/algorithm skeletons and concept checking
 classes implemented in LEMON.
 
@@ -552 +516 @@
 \brief Skeleton and concept checking classes for graph structures
 
-This group contains the skeletons and concept checking classes of LEMON's
+This group describes the skeletons and concept checking classes of LEMON's
 graph structures and helper classes used to implement these.
 */
@@ -561 +525 @@
 \brief Skeleton and concept checking classes for maps
 
-This group contains the skeletons and concept checking classes of maps.
+This group describes the skeletons and concept checking classes of maps.
 */
 
@@ -567 +531 @@
 \anchor demoprograms
 
-@defgroup demos Demo Programs
+@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
+It order to compile them, use <tt>--enable-demo</tt> configure option when
+build the library.
+*/
+
+/**
+@defgroup tools Standalone utility applications
 
 Some utility applications are listed here.
@@ -585 +549 @@
 */
 
-}