Changes in doc/groups.dox [879:25804ef35064:1366:abc24245d276] in lemon

File:

• doc/groups.dox (modified) (18 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-2013
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -113 +113 @@
 detailed documentation of particular adaptors.
 
+Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
+an adaptor can even be applied to another one.
+The following image illustrates a situation when a \ref SubDigraph adaptor
+is applied on a digraph and \ref Undirector is applied on the subgraph.
+
+\image html adaptors2.png
+\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
+
 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
@@ -264 +272 @@
 
 /**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
 @defgroup auxdat Auxiliary Data Structures
 @ingroup datas
@@ -318 +318 @@
 This group contains the common graph search algorithms, namely
 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
-\ref clrs01algorithms.
+\cite clrs01algorithms.
 */
 
@@ -327 +327 @@
 
 This group contains the algorithms for finding shortest paths in digraphs
-\ref clrs01algorithms.
+\cite clrs01algorithms.
 
  - \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -349 +349 @@
 
 This group contains the algorithms for finding minimum cost spanning
-trees and arborescences \ref clrs01algorithms.
+trees and arborescences \cite clrs01algorithms.
 */
 
@@ -358 +358 @@
 
 This group contains the algorithms for finding maximum flows and
-feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
+feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
 
 The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -374 +374 @@
 LEMON contains several algorithms for solving maximum flow problems:
 - \ref EdmondsKarp Edmonds-Karp algorithm
-  \ref edmondskarp72theoretical.
+  \cite edmondskarp72theoretical.
 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
-  \ref goldberg88newapproach.
+  \cite goldberg88newapproach.
 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
-  \ref dinic70algorithm, \ref sleator83dynamic.
+  \cite dinic70algorithm, \cite sleator83dynamic.
 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
-  \ref goldberg88newapproach, \ref sleator83dynamic.
+  \cite goldberg88newapproach, \cite sleator83dynamic.
 
 In most cases the \ref Preflow algorithm provides the
@@ -387 +387 @@
 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.
@@ -400 +400 @@
 
 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
+circulations \cite amo93networkflows. 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.
+   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
  - \ref CostScaling Cost Scaling algorithm based on push/augment and
-   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
-   \ref bunnagel98efficient.
+   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
+   \cite bunnagel98efficient.
  - \ref CapacityScaling Capacity Scaling algorithm based on the successive
-   shortest path method \ref edmondskarp72theoretical.
+   shortest path method \cite edmondskarp72theoretical.
  - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
-   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
-
-In general NetworkSimplex is the most efficient implementation,
-but in special cases other algorithms could be faster.
+   strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
+
+In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
+implementations.
+\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
+several thousands of nodes) and on dense graphs, while \ref CostScaling is
+typically more efficient on large graphs (e.g. hundreds of thousands of
+nodes or above), especially if they are sparse.
+However, other algorithms could be faster in special cases.
 For example, if the total supply and/or capacities are rather small,
-CapacityScaling is usually the fastest algorithm (without effective scaling).
+\ref CapacityScaling is usually the fastest algorithm
+(without effective scaling).
+
+These classes are intended to be used with integer-valued input data
+(capacities, supply values, and costs), except for \ref CapacityScaling,
+which is capable of handling real-valued arc costs (other numerical
+data are required to be integer).
+
+For more details about these implementations and for a comprehensive
+experimental study, see the paper \cite KiralyKovacs12MCF.
+It also compares these codes to other publicly available
+minimum cost flow solvers.
 */
 
@@ -457 +473 @@
 
 This group contains the algorithms for finding minimum mean cycles
-\ref clrs01algorithms, \ref amo93networkflows.
+\cite amo93networkflows, \cite karp78characterization.
 
 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
@@ -473 +489 @@
 
 LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
-  \ref dasdan98minmeancycle.
-- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
-  version of Karp's algorithm \ref dasdan98minmeancycle.
-- \ref Howard "Howard"'s policy iteration algorithm
-  \ref dasdan98minmeancycle.
-
-In practice, the Howard algorithm proved to be by far the most efficient
-one, though the best known theoretical bound on its running time is
-exponential.
-Both Karp and HartmannOrlin 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.
+- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
+- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
+  version of Karp's algorithm \cite hartmann93finding.
+- \ref HowardMmc Howard's policy iteration algorithm
+  \cite dasdan98minmeancycle, \cite dasdan04experimental.
+
+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(nm) and use space O(n<sup>2</sup>+m).
 */
 
@@ -523 +537 @@
   Edmond's blossom shrinking algorithm for calculating maximum weighted
   perfect matching in general graphs.
-
-\image html bipartite_matching.png
-\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
+- \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
 */
 
@@ -541 +562 @@
 
 /**
-@defgroup planar Planarity Embedding and Drawing
+@defgroup graph_isomorphism Graph Isomorphism
+@ingroup algs
+\brief Algorithms for testing (sub)graph isomorphism
+
+This group contains algorithms for finding isomorph copies of a
+given graph in another one, or simply check whether two graphs are isomorphic.
+
+The formal definition of subgraph isomorphism is as follows.
+
+We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
+function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
+embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
+
+The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
+mapping with the property that whenever \f$(u,v)\in E_1\f$, then
+\f$(f(u),f(v))\in E_2\f$.
+
+In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
+also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
+E_2\f$
+
+In addition, the graph nodes may be \e labeled, i.e. we are given two
+node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
+L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
+G_1\f$.
+
+*/
+
+/**
+@defgroup planar Planar Embedding and Drawing
 @ingroup algs
 \brief Algorithms for planarity checking, embedding and drawing
@@ -553 +603 @@
 
 /**
-@defgroup approx Approximation Algorithms
+@defgroup tsp Traveling Salesman Problem
+@ingroup algs
+\brief Algorithms for the symmetric traveling salesman problem
+
+This group contains basic heuristic algorithms for the the symmetric
+\e traveling \e salesman \e problem (TSP).
+Given an \ref FullGraph "undirected full graph" with a cost map on its edges,
+the problem is to find a shortest possible tour that visits each node exactly
+once (i.e. the minimum cost Hamiltonian cycle).
+
+These TSP algorithms are intended to be used with a \e metric \e cost
+\e function, i.e. the edge costs should satisfy the triangle inequality.
+Otherwise the algorithms could yield worse results.
+
+LEMON provides five well-known heuristics for solving symmetric TSP:
+ - \ref NearestNeighborTsp Neareast neighbor algorithm
+ - \ref GreedyTsp Greedy algorithm
+ - \ref InsertionTsp Insertion heuristic (with four selection methods)
+ - \ref ChristofidesTsp Christofides algorithm
+ - \ref Opt2Tsp 2-opt algorithm
+
+\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest
+solution methods. Furthermore, \ref InsertionTsp is usually quite effective.
+
+\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed
+approximation factor: 3/2.
+
+\ref Opt2Tsp usually provides the best results in practice, but
+it is the slowest method. It can also be used to improve given tours,
+for example, the results of other algorithms.
+
+\image html tsp.png
+\image latex tsp.eps "Traveling salesman problem" width=\textwidth
+*/
+
+/**
+@defgroup approx_algs Approximation Algorithms
 @ingroup algs
 \brief Approximation algorithms.
@@ -559 +645 @@
 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.
 */
 
@@ -588 +678 @@
 high-level interface.
 
-The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
-\ref cplex, \ref soplex.
+The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
+\cite cplex, \cite soplex.
 */
 
@@ -676 +766 @@
 This group contains general \c EPS drawing methods and special
 graph exporting tools.
+
+\image html graph_to_eps.png
 */