Changeset 1298:a78e5b779b69 in lemon for lemon/capacity_scaling.h

Timestamp:

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

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

1299:b6bad215bccd, 1300:62dba6c90f35

Parents:

1294:15e233f588da (diff), 1297: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/capacity_scaling.h (modified) (6 diffs)
• lemon/capacity_scaling.h (modified) (5 diffs)

lemon/capacity_scaling.h

@@ -164 +164 @@
 
     // Parameters of the problem
-    bool _have_lower;
+    bool _has_lower;
     Value _sum_supply;
 
@@ -357 +357 @@
     template <typename LowerMap>
     CapacityScaling& 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;
@@ -544 +543 @@
         _cost[j] = _forward[j] ? 1 : -1;
       }
-      _have_lower = false;
+      _has_lower = false;
       return *this;
     }
@@ -755 +754 @@
       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];
@@ -840 +839 @@
     }
 
-    // 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;
@@ -858 +857 @@
 
       // 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/capacity_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).
@@ -67 +67 @@
   /// \ref CapacityScaling implements the capacity scaling version
   /// of the successive shortest path algorithm for finding a
-  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
-  /// \ref edmondskarp72theoretical. It is an efficient dual
-  /// solution method.
+  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
+  /// \cite edmondskarp72theoretical. It is an efficient dual
+  /// solution method, which runs in polynomial time
+  /// \f$O(m\log U (n+m)\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
@@ -117 +119 @@
     typedef typename TR::Heap Heap;
 
-    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
+    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
+    /// of the algorithm
     typedef TR Traits;
 
@@ -643 +646 @@
     ///
     /// 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
@@ -835 +838 @@
       return OPTIMAL;
     }
-    
+
     // Check if the upper bound is greater than or equal to the lower bound
     // on each forward arc.