Context Navigation

← Previous Changeset
Next Changeset →

Changeset 1165:16f55008c863 in lemon

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)

Files:

: 5 edited

doc/groups.dox (modified) (1 diff)
lemon/capacity_scaling.h (modified) (3 diffs)
lemon/cost_scaling.h (modified) (3 diffs)
lemon/cycle_canceling.h (modified) (7 diffs)
lemon/network_simplex.h (modified) (3 diffs)

Legend:

: Unmodified
: Added
: Removed

doc/groups.dox

-                      r1164
+                      r1165
 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
+implementations, but the other algorithms could be faster in special cases.
+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,
 \ref CapacityScaling is usually the fastest algorithm (without effective scaling).

lemon/capacity_scaling.h

-                      r1026
+                      r1165
   /// \ref edmondskarp72theoretical. It is an efficient dual
   /// solution method.
+  ///
+  /// This algorithm is typically slower than \ref CostScaling and
+  /// \ref NetworkSimplex, but in special cases, it can be more
+  /// efficient than them.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
   ///
   /// Most of the parameters of the problem (except for the digraph)
 …
+    }
+    /// \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
 …
+    }
+    /// \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

lemon/cost_scaling.h

-                      r1049
+                      r1165
   ///
   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
+  /// implementations available in LEMON for this problem.
+  /// implementations available in LEMON for solving this problem.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
   ///
   /// Most of the parameters of the problem (except for the digraph)
 …
+    }
+    /// \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
 …
+    }
+    /// \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

lemon/cycle_canceling.h

-                      r1026
+                      r1165
   /// \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)
 …
     ///
     /// \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()
 …
     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
 …
       /// \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
     };
 …
+    }
+    /// \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
 …
+    }
+    /// \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
 …
+    }
     // Execute the "Cancel And Tighten" method
+    // Execute the "Cancel-and-Tighten" method
     void startCancelAndTighten() {
       // Constants for the min mean cycle computations

lemon/network_simplex.h

-                      r1026
+                      r1165
   ///
   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
+  /// implementations available in LEMON for this problem.
+  /// implementations available in LEMON for solving this problem.
+  /// (For more information, see \ref min_cost_flow_algs "the module page".)
   /// Furthermore, this class supports both directions of the supply/demand
   /// inequality constraints. For more information, see \ref SupplyType.
 …
+    }
+    /// \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
 …
+    }
+    /// \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

Note: See TracChangeset for help on using the changeset viewer.