Changeset 1002:f63ba40a60f4 in lemon-main

Timestamp:

01/30/12 23:24:14 (13 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improve module docs and references (#437)

Files:

• doc/groups.dox (modified) (3 diffs)
• doc/min_cost_flow.dox (modified) (1 diff)
• doc/references.bib (modified) (3 diffs)
• lemon/hartmann_orlin_mmc.h (modified) (1 diff)
• lemon/howard_mmc.h (modified) (1 diff)
• lemon/karp_mmc.h (modified) (1 diff)

doc/groups.dox

@@ -408 +408 @@
 
 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
-implementations, but the other two algorithms could be faster in special cases.
+implementations, but the other algorithms could be faster in special cases.
 For example, if the total supply and/or capacities are rather small,
 \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).
 */
 
@@ -449 +454 @@
 
 This group contains the algorithms for finding minimum mean cycles
-\ref clrs01algorithms, \ref amo93networkflows.
+\ref amo93networkflows, \ref karp78characterization.
 
 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
@@ -465 +470 @@
 
 LEMON contains three algorithms for solving the minimum mean cycle problem:
-- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
-  \ref dasdan98minmeancycle.
+- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
-  version of Karp's algorithm \ref dasdan98minmeancycle.
+  version of Karp's algorithm \ref hartmann93finding.
 - \ref HowardMmc Howard's policy iteration algorithm
-  \ref dasdan98minmeancycle.
+  \ref dasdan98minmeancycle, \ref dasdan04experimental.
 
 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the

doc/min_cost_flow.dox

@@ -102 +102 @@
 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 
-However if the sum of the supply values is zero, then these two problems
+However, if the sum of the supply values is zero, then these two problems
 are equivalent.
 The \ref min_cost_flow_algs "algorithms" in LEMON support the general

doc/references.bib

@@ -5 +5 @@
   title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
                   {O}ptimization in {N}etworks},
-  howpublished = {\url{http://lemon.cs.elte.hu/}},
-  year =         2009
+  howpublished = {\url{http://lemon.cs.elte.hu/}}
 }
 
@@ -212 +211 @@
   volume =       23,
   pages =        {309-311}
+}
+
+@article{hartmann93finding,
+  author =       {Mark Hartmann and James B. Orlin},
+  title =        {Finding minimum cost to time ratio cycles with small
+                  integral transit times},
+  journal =      {Networks},
+  year =         1993,
+  volume =       23,
+  pages =        {567-574}
 }
 
@@ -226 +235 @@
 }
 
+@article{dasdan04experimental,
+  author =       {Ali Dasdan},
+  title =        {Experimental analysis of the fastest optimum cycle
+                  ratio and mean algorithms},
+  journal =      {ACM Trans. Des. Autom. Electron. Syst.},
+  year =         2004,
+  volume =       9,
+  issue =        4,
+  pages =        {385-418}
+} 
+
 
 %%%%% Minimum cost flow algorithms %%%%%

lemon/hartmann_orlin_mmc.h

@@ -99 +99 @@
   /// This class implements the Hartmann-Orlin algorithm for finding
   /// a directed cycle of minimum mean cost in a digraph
-  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// \ref hartmann93finding, \ref dasdan98minmeancycle.
   /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
   /// it applies an efficient early termination scheme.

lemon/howard_mmc.h

@@ -99 +99 @@
   /// This class implements Howard's policy iteration algorithm for finding
   /// a directed cycle of minimum mean cost in a digraph
-  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
   /// This class provides the most efficient algorithm for the
   /// minimum mean cycle problem, though the best known theoretical

lemon/karp_mmc.h

@@ -99 +99 @@
   /// This class implements Karp's algorithm for finding a directed
   /// cycle of minimum mean cost in a digraph
-  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
+  /// \ref karp78characterization, \ref dasdan98minmeancycle.
   /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
   ///