Changeset 1104:a78e5b779b69 in lemon-main for lemon/cost_scaling.h

Timestamp:

10/17/13 15:08:41 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1101:15e233f588da (diff), 1103:c0c2f5c87aa6 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge bugfix #478

Files:

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

lemon/cost_scaling.h

@@ -257 +257 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     Value _sum_supply;
     int _sup_node_num;
@@ -373 +373 @@
     template <typename LowerMap>
     CostScaling& lowerMap(const LowerMap& map) {
-      _have_lower = true;
+      _has_lower = true;
       for (ArcIt a(_graph); a != INVALID; ++a) {
         _lower[_arc_idf[a]] = map[a];
-        _lower[_arc_idb[a]] = map[a];
       }
       return *this;
@@ -569 +568 @@
         _scost[_reverse[j]] = 0;
       }
-      _have_lower = false;
+      _has_lower = false;
       return *this;
     }
@@ -781 +780 @@
       const Value MAX = std::numeric_limits<Value>::max();
       int last_out;
-      if (_have_lower) {
+      if (_has_lower) {
         for (int i = 0; i != _root; ++i) {
           last_out = _first_out[i+1];
@@ -838 +837 @@
         sup[n] = _supply[_node_id[n]];
       }
-      if (_have_lower) {
+      if (_has_lower) {
         for (ArcIt a(_graph); a != INVALID; ++a) {
           int j = _arc_idf[a];
@@ -908 +907 @@
     }
 
-    // Check if the upper bound is greater or equal to the lower bound
-    // on each arc.
+    // Check if the upper bound is greater than or equal to the lower bound
+    // on each forward arc.
     bool checkBoundMaps() {
       for (int j = 0; j != _res_arc_num; ++j) {
-        if (_upper[j] < _lower[j]) return false;
+        if (_forward[j] && _upper[j] < _lower[j]) return false;
       }
       return true;
@@ -992 +991 @@
 
       // Handle non-zero lower bounds
-      if (_have_lower) {
+      if (_has_lower) {
         int limit = _first_out[_root];
         for (int j = 0; j != limit; ++j) {
-          if (!_forward[j]) _res_cap[j] += _lower[j];
+          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
         }
       }

lemon/cost_scaling.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2010
+ * Copyright (C) 2003-2013
  * 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" \ref amo93networkflows, \ref goldberg90approximation,
-  /// \ref goldberg97efficient, \ref bunnagel98efficient.
+  /// "minimum cost flow" \cite amo93networkflows,
+  /// \cite goldberg90approximation,
+  /// \cite goldberg97efficient, \cite 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
@@ -151 +154 @@
     typedef typename TR::LargeCost LargeCost;
 
-    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
+    /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
+    /// of the algorithm
     typedef TR Traits;
 
@@ -211 +215 @@
     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:
@@ -667 +672 @@
     ///
     /// This function returns the total cost of the found flow.
-    /// Its complexity is O(e).
+    /// Its complexity is O(m).
     ///
     /// \note The return type of the function can be specified as a
@@ -901 +906 @@
       return OPTIMAL;
     }
-    
+
     // Check if the upper bound is greater than or equal to the lower bound
     // on each forward arc.
@@ -1282 +1287 @@
           _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];