Changeset 910:f3bc4e9b5f3a in lemon for lemon/capacity_scaling.h

Timestamp:

02/20/10 18:39:03 (14 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

New heuristics for MCF algorithms (#340)
and some implementation improvements.

• A useful heuristic is added to NetworkSimplex? to make the initial pivots faster.
• A powerful global update heuristic is added to CostScaling? and the implementation is reworked with various improvements.
• Better relabeling in CostScaling? to improve numerical stability and make the code faster.
• A small improvement is made in CapacityScaling? for better delta computation.
• Add notes to the classes about the usage of vector<char> instead of vector<bool> for efficiency reasons.

File:

• lemon/capacity_scaling.h (modified) (2 diffs)

lemon/capacity_scaling.h

@@ -135 +135 @@
 
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> BoolVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 
   private:
@@ -765 +766 @@
       if (_factor > 1) {
         // With scaling
-        Value max_sup = 0, max_dem = 0;
-        for (int i = 0; i != _node_num; ++i) {
+        Value max_sup = 0, max_dem = 0, max_cap = 0;
+        for (int i = 0; i != _root; ++i) {
           Value ex = _excess[i];
           if ( ex > max_sup) max_sup =  ex;
           if (-ex > max_dem) max_dem = -ex;
-        }
-        Value max_cap = 0;
-        for (int j = 0; j != _res_arc_num; ++j) {
-          if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+          int last_out = _first_out[i+1] - 1;
+          for (int j = _first_out[i]; j != last_out; ++j) {
+            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
+          }
         }
         max_sup = std::min(std::min(max_sup, max_dem), max_cap);