Changes in lemon/cost_scaling.h [1298:a78e5b779b69:1297:c0c2f5c87aa6] in lemon

File:

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

lemon/cost_scaling.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2013
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -92 +92 @@
   /// \ref CostScaling implements a cost scaling algorithm that performs
   /// push/augment and relabel operations for finding a \ref min_cost_flow
-  /// "minimum cost flow" \cite amo93networkflows,
-  /// \cite goldberg90approximation,
-  /// \cite goldberg97efficient, \cite bunnagel98efficient.
+  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
+  /// \ref goldberg97efficient, \ref bunnagel98efficient.
   /// It is a highly efficient primal-dual solution method, which
   /// 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^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
   ///
   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
@@ -154 +151 @@
     typedef typename TR::LargeCost LargeCost;
 
-    /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
-    /// of the algorithm
+    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
     typedef TR Traits;
 
@@ -215 +211 @@
     typedef std::vector<LargeCost> LargeCostVector;
     typedef std::vector<char> BoolVector;
-    // Note: vector<char> is used instead of vector<bool>
-    // for efficiency reasons
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 
   private:
@@ -672 +667 @@
     ///
     /// This function returns the total cost of the found flow.
-    /// Its complexity is O(m).
+    /// Its complexity is O(e).
     ///
     /// \note The return type of the function can be specified as a
@@ -906 +901 @@
       return OPTIMAL;
     }
-
+    
     // Check if the upper bound is greater than or equal to the lower bound
     // on each forward arc.
@@ -1287 +1282 @@
           _buckets[r] = _bucket_next[u];
 
-          // Search the incoming arcs of u
+          // Search the incomming arcs of u
           LargeCost pi_u = _pi[u];
           int last_out = _first_out[u+1];