Changeset 910:f3bc4e9b5f3a in lemon for lemon/cycle_canceling.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/cycle_canceling.h (modified) (3 diffs)

lemon/cycle_canceling.h

@@ -145 +145 @@
     
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> CharVector;
     typedef std::vector<double> DoubleVector;
     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:
@@ -199 +200 @@
     IntArcMap _arc_idb;
     IntVector _first_out;
-    CharVector _forward;
+    BoolVector _forward;
     IntVector _source;
     IntVector _target;
@@ -934 +935 @@
       DoubleVector pi(_res_node_num, 0.0);
       IntVector level(_res_node_num);
-      CharVector reached(_res_node_num);
-      CharVector processed(_res_node_num);
+      BoolVector reached(_res_node_num);
+      BoolVector processed(_res_node_num);
       IntVector pred_node(_res_node_num);
       IntVector pred_arc(_res_node_num);