Changeset 1217:7bf489cf624e in lemon

Timestamp:

03/16/13 13:14:35 (11 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Minor fixes and improvements in the doc (#459)

Files:

• doc/groups.dox (modified) (2 diffs)
• lemon/capacity_scaling.h (modified) (1 diff)
• lemon/concepts/bpgraph.h (modified) (2 diffs)
• lemon/concepts/digraph.h (modified) (2 diffs)
• lemon/concepts/graph.h (modified) (2 diffs)
• lemon/concepts/graph_components.h (modified) (1 diff)
• lemon/cost_scaling.h (modified) (2 diffs)
• lemon/cycle_canceling.h (modified) (1 diff)
• lemon/hartmann_orlin_mmc.h (modified) (2 diffs)
• lemon/howard_mmc.h (modified) (1 diff)
• lemon/karp_mmc.h (modified) (1 diff)
• lemon/list_graph.h (modified) (1 diff)
• lemon/network_simplex.h (modified) (1 diff)

doc/groups.dox

@@ -393 +393 @@
 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
+problem and its dual solution, see: \ref min_cost_flow
 "Minimum Cost Flow Problem".
 
@@ -485 +485 @@
 time is exponential.
 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" 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.
+run in time O(ne) and use space O(n<sup>2</sup>+e).
 */
 

lemon/capacity_scaling.h

@@ -69 +69 @@
   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
   /// \ref edmondskarp72theoretical. It is an efficient dual
-  /// solution method.
+  /// solution method, which runs in polynomial time
+  /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum
+  /// of node supply and arc capacity values.
   ///
   /// This algorithm is typically slower than \ref CostScaling and

lemon/concepts/bpgraph.h

@@ -998 +998 @@
       /// \brief The base node of the iterator.
       ///
-      /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
@@ -1004 +1004 @@
       /// \brief The running node of the iterator.
       ///
-      /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/digraph.h

@@ -410 +410 @@
       /// \brief The base node of the iterator.
       ///
-      /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
@@ -416 +416 @@
       /// \brief The running node of the iterator.
       ///
-      /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/graph.h

@@ -758 +758 @@
       /// \brief The base node of the iterator.
       ///
-      /// Returns the base node of the given incomming arc iterator
+      /// Returns the base node of the given incoming arc iterator
       /// (i.e. the target node of the corresponding arc).
       Node baseNode(InArcIt) const { return INVALID; }
@@ -764 +764 @@
       /// \brief The running node of the iterator.
       ///
-      /// Returns the running node of the given incomming arc iterator
+      /// Returns the running node of the given incoming arc iterator
       /// (i.e. the source node of the corresponding arc).
       Node runningNode(InArcIt) const { return INVALID; }

lemon/concepts/graph_components.h

@@ -876 +876 @@
       void next(Arc&) const {}
 
-      /// \brief Return the first arc incomming to the given node.
-      ///
-      /// This function gives back the first arc incomming to the
+      /// \brief Return the first arc incoming to the given node.
+      ///
+      /// This function gives back the first arc incoming to the
       /// given node.
       void firstIn(Arc&, const Node&) const {}
 
-      /// \brief Return the next arc incomming to the given node.
-      ///
-      /// This function gives back the next arc incomming to the
+      /// \brief Return the next arc incoming to the given node.
+      ///
+      /// This function gives back the next arc incoming to the
       /// given node.
       void nextIn(Arc&) const {}

lemon/cost_scaling.h

@@ -97 +97 @@
   /// can be viewed as the generalization of the \ref Preflow
   /// "preflow push-relabel" algorithm for the maximum flow problem.
+  /// It is a polynomial algorithm, its running time complexity is
+  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
   ///
   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
@@ -1270 +1272 @@
           _buckets[r] = _bucket_next[u];
 
-          // Search the incomming arcs of u
+          // Search the incoming arcs of u
           LargeCost pi_u = _pi[u];
           int last_out = _first_out[u+1];

lemon/cycle_canceling.h

@@ -52 +52 @@
   /// 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.
+  /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)),
+  /// 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".)
   ///

lemon/hartmann_orlin_mmc.h

@@ -100 +100 @@
   /// a directed cycle of minimum mean cost in a digraph
   /// \ref hartmann93finding, \ref dasdan98minmeancycle.
-  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
-  /// it applies an efficient early termination scheme.
-  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
+  /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but
+  /// applies an early termination scheme. It makes the algorithm
+  /// significantly faster for some problem instances, but slower for others.
+  /// The algorithm runs in time O(ne) and uses space O(n<sup>2</sup>+e).
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
@@ -275 +276 @@
     ///
     /// If you don't call this function before calling \ref run() or
-    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
-    /// structure. The destuctor deallocates this automatically
+    /// \ref findCycleMean(), a local \ref Path "path" structure
+    /// will be allocated. The destuctor deallocates this automatically
     /// allocated object, of course.
     ///

lemon/howard_mmc.h

@@ -283 +283 @@
     ///
     /// If you don't call this function before calling \ref run() or
-    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
-    /// structure. The destuctor deallocates this automatically
+    /// \ref findCycleMean(), a local \ref Path "path" structure
+    /// will be allocated. The destuctor deallocates this automatically
     /// allocated object, of course.
     ///

lemon/karp_mmc.h

@@ -271 +271 @@
     ///
     /// If you don't call this function before calling \ref run() or
-    /// \ref findCycleMean(), it will allocate a local \ref Path "path"
-    /// structure. The destuctor deallocates this automatically
+    /// \ref findCycleMean(), a local \ref Path "path" structure
+    /// will be allocated. The destuctor deallocates this automatically
     /// allocated object, of course.
     ///

lemon/list_graph.h

@@ -446 +446 @@
     ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
     ///invalidated for the outgoing arcs of node \c v and \c InArcIt
-    ///iterators are invalidated for the incomming arcs of \c v.
+    ///iterators are invalidated for the incoming arcs of \c v.
     ///Moreover all iterators referencing node \c v or the removed
     ///loops are also invalidated. Other iterators remain valid.

lemon/network_simplex.h

@@ -1504 +1504 @@
           }
         } else {
-          // Find the min. cost incomming arc for each demand node
+          // Find the min. cost incoming arc for each demand node
           for (int i = 0; i != int(demand_nodes.size()); ++i) {
             Node v = demand_nodes[i];