Changeset 1071:879fcb781086 in lemon-main for lemon/cycle_canceling.h

Timestamp:

07/30/13 15:24:45 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1069:d1a48668ddb4 (diff), 1070:ee9bac10f58e (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 #454

Files:

• lemon/cycle_canceling.h (modified) (2 diffs)
• lemon/cycle_canceling.h (modified) (3 diffs)

lemon/cycle_canceling.h

@@ -671 +671 @@
       if (_sum_supply > 0) return INFEASIBLE;
 
+      // Check lower and upper bounds
+      LEMON_DEBUG(checkBoundMaps(),
+          "Upper bounds must be greater or equal to the lower bounds");
+
 
       // Initialize vectors
@@ -779 +783 @@
 
       return OPTIMAL;
+    }
+    
+    // Check if the upper bound is greater or equal to the lower bound
+    // on each arc.
+    bool checkBoundMaps() {
+      for (int j = 0; j != _res_arc_num; ++j) {
+        if (_upper[j] < _lower[j]) return false;
+      }
+      return true;
     }
 

lemon/cycle_canceling.h

@@ -48 +48 @@
   /// \ref CycleCanceling implements three different cycle-canceling
   /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
-  /// \ref amo93networkflows, \ref klein67primal,
-  /// \ref goldberg89cyclecanceling.
+  /// \cite amo93networkflows, \cite klein67primal,
+  /// \cite goldberg89cyclecanceling.
   /// 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".)
   ///
@@ -132 +132 @@
       /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
       /// well-known strongly polynomial method
-      /// \ref goldberg89cyclecanceling. It improves along a
+      /// \cite 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>e<sup>3</sup>log(n)).
@@ -138 +138 @@
       /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
       /// improved version of the previous method
-      /// \ref goldberg89cyclecanceling.
+      /// \cite goldberg89cyclecanceling.
       /// It is faster both in theory and in practice, its running time
       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).