Changeset 1071:879fcb781086 in lemon-main

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

Location:

lemon

Files:

• capacity_scaling.h (modified) (2 diffs)
• capacity_scaling.h (modified) (1 diff)
• cost_scaling.h (modified) (2 diffs)
• cost_scaling.h (modified) (2 diffs)
• cycle_canceling.h (modified) (2 diffs)
• cycle_canceling.h (modified) (3 diffs)
• network_simplex.h (modified) (2 diffs)
• network_simplex.h (modified) (2 diffs)

lemon/capacity_scaling.h

@@ -740 +740 @@
       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
       for (int i = 0; i != _root; ++i) {
@@ -832 +837 @@
 
       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/capacity_scaling.h

@@ -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(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/cost_scaling.h

@@ -764 +764 @@
       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
@@ -899 +903 @@
 
       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/cost_scaling.h

@@ -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^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
   ///
   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
@@ -1283 +1285 @@
           _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

@@ -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)).

lemon/network_simplex.h

@@ -1068 +1068 @@
              (_stype == LEQ && _sum_supply >= 0)) ) return false;
 
+      // Check lower and upper bounds
+      LEMON_DEBUG(checkBoundMaps(),
+          "Upper bounds must be greater or equal to the lower bounds");
+
       // Remove non-zero lower bounds
       if (_have_lower) {
@@ -1231 +1235 @@
       return true;
     }
+    
+    // Check if the upper bound is greater or equal to the lower bound
+    // on each arc.
+    bool checkBoundMaps() {
+      for (int j = 0; j != _arc_num; ++j) {
+        if (_upper[j] < _lower[j]) return false;
+      }
+      return true;
+    }
 
     // Find the join node

lemon/network_simplex.h

@@ -42 +42 @@
   /// \ref NetworkSimplex implements the primal Network Simplex algorithm
   /// for finding a \ref min_cost_flow "minimum cost flow"
-  /// \ref amo93networkflows, \ref dantzig63linearprog,
-  /// \ref kellyoneill91netsimplex.
+  /// \cite amo93networkflows, \cite dantzig63linearprog,
+  /// \cite kellyoneill91netsimplex.
   /// This algorithm is a highly efficient specialized version of the
   /// linear programming simplex method directly for the minimum cost
@@ -1517 +1517 @@
           }
         } 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];