Changeset 810:3b53491bf643 in lemon-main for lemon/capacity_scaling.h

Timestamp:

11/12/09 23:34:35 (14 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Rebase:

31306464373530663736663634663865303635326136663934636335303533383063623764626530

Message:

More options for run() in scaling MCF algorithms (#180)

• Three methods can be selected and the scaling factor can be given for CostScaling?.
• The scaling factor can be given for CapacityScaling?.

File:

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

lemon/capacity_scaling.h

@@ -174 +174 @@
 
     Value _delta;
-    int _phase_num;
+    int _factor;
     IntVector _pred;
 
@@ -514 +514 @@
     /// have to be set again. See \ref reset() for examples.
     /// However the underlying digraph must not be modified after this
-    /// class have been constructed, since it copies the digraph.
-    ///
-    /// \param scaling Enable or disable capacity scaling.
-    /// If the maximum upper bound and/or the amount of total supply
-    /// is rather small, the algorithm could be slightly faster without
-    /// scaling.
+    /// class have been constructed, since it copies and extends the graph.
+    ///
+    /// \param factor The capacity scaling factor. It must be larger than
+    /// one to use scaling. If it is less or equal to one, then scaling
+    /// will be disabled.
     ///
     /// \return \c INFEASIBLE if no feasible flow exists,
@@ -532 +531 @@
     ///
     /// \see ProblemType
-    ProblemType run(bool scaling = true) {
-      ProblemType pt = init(scaling);
+    ProblemType run(int factor = 4) {
+      _factor = factor;
+      ProblemType pt = init();
       if (pt != OPTIMAL) return pt;
       return start();
@@ -547 +547 @@
     /// used, all the parameters given before are kept for the next
     /// \ref run() call.
-    /// However the underlying digraph must not be modified after this
+    /// However, the underlying digraph must not be modified after this
     /// class have been constructed, since it copies and extends the graph.
     ///
@@ -678 +678 @@
 
     // Initialize the algorithm
-    ProblemType init(bool scaling) {
+    ProblemType init() {
       if (_node_num == 0) return INFEASIBLE;
 
@@ -759 +759 @@
 
       // Initialize delta value
-      if (scaling) {
+      if (_factor > 1) {
         // With scaling
         Value max_sup = 0, max_dem = 0;
@@ -771 +771 @@
         }
         max_sup = std::min(std::min(max_sup, max_dem), max_cap);
-        _phase_num = 0;
-        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
-          ++_phase_num;
+        for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
       } else {
         // Without scaling
@@ -812 +810 @@
       // Perform capacity scaling phases
       int s, t;
-      int phase_cnt = 0;
-      int factor = 4;
       ResidualDijkstra _dijkstra(*this);
       while (true) {
@@ -888 +884 @@
 
         if (_delta == 1) break;
-        if (++phase_cnt == _phase_num / 4) factor = 2;
-        _delta = _delta <= factor ? 1 : _delta / factor;
+        _delta = _delta <= _factor ? 1 : _delta / _factor;
       }