Changeset 1003:16f55008c863 in lemon-main for lemon/cycle_canceling.h

Timestamp:

01/30/12 23:24:40 (12 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Doc improvements for min cost flow algorithms (#437)

File:

• lemon/cycle_canceling.h (modified) (7 diffs)

lemon/cycle_canceling.h

@@ -49 +49 @@
   /// \ref amo93networkflows, \ref klein67primal,
   /// \ref goldberg89cyclecanceling.
-  /// The most efficent one (both theoretically and practically)
-  /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
-  /// thus it is the default method.
-  /// It is strongly polynomial, but in practice, it is typically much
-  /// slower than the scaling algorithms and NetworkSimplex.
+  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
+  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
+  /// It runs in strongly polynomial time, but in practice, it is typically
+  /// orders of magnitude slower than the scaling algorithms and
+  /// \ref NetworkSimplex.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
   ///
   /// Most of the parameters of the problem (except for the digraph)
@@ -117 +118 @@
     ///
     /// \ref CycleCanceling provides three different cycle-canceling
-    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
+    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
     /// is used, which is by far the most efficient and the most robust.
     /// However, the other methods can be selected using the \ref run()
@@ -123 +124 @@
     enum Method {
       /// A simple cycle-canceling method, which uses the
-      /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
-      /// number for detecting negative cycles in the residual network.
+      /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
+      /// cycles in the residual network.
+      /// The number of Bellman-Ford iterations is bounded by a successively
+      /// increased limit.
       SIMPLE_CYCLE_CANCELING,
       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
@@ -130 +133 @@
       /// \ref goldberg89cyclecanceling. It improves along a
       /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
-      /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
+      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
       MINIMUM_MEAN_CYCLE_CANCELING,
-      /// The "Cancel And Tighten" algorithm, which can be viewed as an
+      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
       /// improved version of the previous method
       /// \ref goldberg89cyclecanceling.
       /// It is faster both in theory and in practice, its running time
-      /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
+      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
       CANCEL_AND_TIGHTEN
     };
@@ -611 +614 @@
     }
 
-    /// \brief Return the flow map (the primal solution).
+    /// \brief Copy the flow values (the primal solution) into the
+    /// given map.
     ///
     /// This function copies the flow value on each arc into the given
@@ -635 +639 @@
     }
 
-    /// \brief Return the potential map (the dual solution).
+    /// \brief Copy the potential values (the dual solution) into the
+    /// given map.
     ///
     /// This function copies the potential (dual value) of each node
@@ -955 +960 @@
     }
 
-    // Execute the "Cancel And Tighten" method
+    // Execute the "Cancel-and-Tighten" method
     void startCancelAndTighten() {
       // Constants for the min mean cycle computations