Changeset 840:2914b6f0fde0 in lemon-1.2 for lemon/cost_scaling.h

Timestamp:

02/26/10 14:00:20 (14 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

838:2c35bef44dd1 (diff), 839:f3bc4e9b5f3a (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 #340

Files:

• lemon/cost_scaling.h (modified) (19 diffs)
• lemon/cost_scaling.h (modified) (4 diffs)

lemon/cost_scaling.h

@@ -202 +202 @@
 
     typedef std::vector<int> IntVector;
-    typedef std::vector<char> BoolVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
     typedef std::vector<LargeCost> LargeCostVector;
+    typedef std::vector<char> BoolVector;
+    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 
   private:
@@ -249 +250 @@
     bool _have_lower;
     Value _sum_supply;
+    int _sup_node_num;
 
     // Data structures for storing the digraph
@@ -277 +279 @@
     int _alpha;
 
+    IntVector _buckets;
+    IntVector _bucket_next;
+    IntVector _bucket_prev;
+    IntVector _rank;
+    int _max_rank;
+  
     // Data for a StaticDigraph structure
     typedef std::pair<int, int> IntPair;
@@ -829 +837 @@
       }
 
+      _sup_node_num = 0;
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        if (sup[n] > 0) ++_sup_node_num;
+      }
+
       // Find a feasible flow using Circulation
       Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>
@@ -863 +876 @@
         for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
           int ra = _reverse[a];
-          _res_cap[a] = 1;
+          _res_cap[a] = 0;
           _res_cap[ra] = 0;
           _cost[a] = 0;
@@ -877 +890 @@
       // Maximum path length for partial augment
       const int MAX_PATH_LENGTH = 4;
-      
+
+      // Initialize data structures for buckets      
+      _max_rank = _alpha * _res_node_num;
+      _buckets.resize(_max_rank);
+      _bucket_next.resize(_res_node_num + 1);
+      _bucket_prev.resize(_res_node_num + 1);
+      _rank.resize(_res_node_num + 1);
+  
       // Execute the algorithm
       switch (method) {
@@ -916 +936 @@
       }
     }
+    
+    // Initialize a cost scaling phase
+    void initPhase() {
+      // Saturate arcs not satisfying the optimality condition
+      for (int u = 0; u != _res_node_num; ++u) {
+        int last_out = _first_out[u+1];
+        LargeCost pi_u = _pi[u];
+        for (int a = _first_out[u]; a != last_out; ++a) {
+          int v = _target[a];
+          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
+            Value delta = _res_cap[a];
+            _excess[u] -= delta;
+            _excess[v] += delta;
+            _res_cap[a] = 0;
+            _res_cap[_reverse[a]] += delta;
+          }
+        }
+      }
+      
+      // Find active nodes (i.e. nodes with positive excess)
+      for (int u = 0; u != _res_node_num; ++u) {
+        if (_excess[u] > 0) _active_nodes.push_back(u);
+      }
+
+      // Initialize the next arcs
+      for (int u = 0; u != _res_node_num; ++u) {
+        _next_out[u] = _first_out[u];
+      }
+    }
+    
+    // Early termination heuristic
+    bool earlyTermination() {
+      const double EARLY_TERM_FACTOR = 3.0;
+
+      // Build a static residual graph
+      _arc_vec.clear();
+      _cost_vec.clear();
+      for (int j = 0; j != _res_arc_num; ++j) {
+        if (_res_cap[j] > 0) {
+          _arc_vec.push_back(IntPair(_source[j], _target[j]));
+          _cost_vec.push_back(_cost[j] + 1);
+        }
+      }
+      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
+
+      // Run Bellman-Ford algorithm to check if the current flow is optimal
+      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
+      bf.init(0);
+      bool done = false;
+      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
+      for (int i = 0; i < K && !done; ++i) {
+        done = bf.processNextWeakRound();
+      }
+      return done;
+    }
+
+    // Global potential update heuristic
+    void globalUpdate() {
+      int bucket_end = _root + 1;
+    
+      // Initialize buckets
+      for (int r = 0; r != _max_rank; ++r) {
+        _buckets[r] = bucket_end;
+      }
+      Value total_excess = 0;
+      for (int i = 0; i != _res_node_num; ++i) {
+        if (_excess[i] < 0) {
+          _rank[i] = 0;
+          _bucket_next[i] = _buckets[0];
+          _bucket_prev[_buckets[0]] = i;
+          _buckets[0] = i;
+        } else {
+          total_excess += _excess[i];
+          _rank[i] = _max_rank;
+        }
+      }
+      if (total_excess == 0) return;
+
+      // Search the buckets
+      int r = 0;
+      for ( ; r != _max_rank; ++r) {
+        while (_buckets[r] != bucket_end) {
+          // Remove the first node from the current bucket
+          int u = _buckets[r];
+          _buckets[r] = _bucket_next[u];
+          
+          // Search the incomming arcs of u
+          LargeCost pi_u = _pi[u];
+          int last_out = _first_out[u+1];
+          for (int a = _first_out[u]; a != last_out; ++a) {
+            int ra = _reverse[a];
+            if (_res_cap[ra] > 0) {
+              int v = _source[ra];
+              int old_rank_v = _rank[v];
+              if (r < old_rank_v) {
+                // Compute the new rank of v
+                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
+                int new_rank_v = old_rank_v;
+                if (nrc < LargeCost(_max_rank))
+                  new_rank_v = r + 1 + int(nrc);
+                  
+                // Change the rank of v
+                if (new_rank_v < old_rank_v) {
+                  _rank[v] = new_rank_v;
+                  _next_out[v] = _first_out[v];
+                  
+                  // Remove v from its old bucket
+                  if (old_rank_v < _max_rank) {
+                    if (_buckets[old_rank_v] == v) {
+                      _buckets[old_rank_v] = _bucket_next[v];
+                    } else {
+                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
+                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
+                    }
+                  }
+                  
+                  // Insert v to its new bucket
+                  _bucket_next[v] = _buckets[new_rank_v];
+                  _bucket_prev[_buckets[new_rank_v]] = v;
+                  _buckets[new_rank_v] = v;
+                }
+              }
+            }
+          }
+
+          // Finish search if there are no more active nodes
+          if (_excess[u] > 0) {
+            total_excess -= _excess[u];
+            if (total_excess <= 0) break;
+          }
+        }
+        if (total_excess <= 0) break;
+      }
+      
+      // Relabel nodes
+      for (int u = 0; u != _res_node_num; ++u) {
+        int k = std::min(_rank[u], r);
+        if (k > 0) {
+          _pi[u] -= _epsilon * k;
+          _next_out[u] = _first_out[u];
+        }
+      }
+    }
 
     /// Execute the algorithm performing augment and relabel operations
     void startAugment(int max_length = std::numeric_limits<int>::max()) {
       // Paramters for heuristics
-      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
-      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
-
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const double GLOBAL_UPDATE_FACTOR = 3.0;
+
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
+        (_res_node_num + _sup_node_num * _sup_node_num));
+      int next_update_limit = global_update_freq;
+      
+      int relabel_cnt = 0;
+      
       // Perform cost scaling phases
-      IntVector pred_arc(_res_node_num);
-      std::vector<int> path_nodes;
+      std::vector<int> path;
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
                                         1 : _epsilon / _alpha )
       {
-        // "Early Termination" heuristic: use Bellman-Ford algorithm
-        // to check if the current flow is optimal
-        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
-          _arc_vec.clear();
-          _cost_vec.clear();
-          for (int j = 0; j != _res_arc_num; ++j) {
-            if (_res_cap[j] > 0) {
-              _arc_vec.push_back(IntPair(_source[j], _target[j]));
-              _cost_vec.push_back(_cost[j] + 1);
-            }
-          }
-          _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
-
-          BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
-          bf.init(0);
-          bool done = false;
-          int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
-          for (int i = 0; i < K && !done; ++i)
-            done = bf.processNextWeakRound();
-          if (done) break;
-        }
-
-        // Saturate arcs not satisfying the optimality condition
-        for (int a = 0; a != _res_arc_num; ++a) {
-          if (_res_cap[a] > 0 &&
-              _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
-            Value delta = _res_cap[a];
-            _excess[_source[a]] -= delta;
-            _excess[_target[a]] += delta;
-            _res_cap[a] = 0;
-            _res_cap[_reverse[a]] += delta;
-          }
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
         }
         
-        // Find active nodes (i.e. nodes with positive excess)
-        for (int u = 0; u != _res_node_num; ++u) {
-          if (_excess[u] > 0) _active_nodes.push_back(u);
-        }
-
-        // Initialize the next arcs
-        for (int u = 0; u != _res_node_num; ++u) {
-          _next_out[u] = _first_out[u];
-        }
-
+        // Initialize current phase
+        initPhase();
+        
         // Perform partial augment and relabel operations
         while (true) {
@@ -982 +1114 @@
           if (_active_nodes.size() == 0) break;
           int start = _active_nodes.front();
-          path_nodes.clear();
-          path_nodes.push_back(start);
 
           // Find an augmenting path from the start node
+          path.clear();
           int tip = start;
-          while (_excess[tip] >= 0 &&
-                 int(path_nodes.size()) <= max_length) {
+          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
             int u;
-            LargeCost min_red_cost, rc;
-            int last_out = _sum_supply < 0 ?
-              _first_out[tip+1] : _first_out[tip+1] - 1;
+            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
+            int last_out = _first_out[tip+1];
             for (int a = _next_out[tip]; a != last_out; ++a) {
-              if (_res_cap[a] > 0 &&
-                  _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
-                u = _target[a];
-                pred_arc[u] = a;
+              u = _target[a];
+              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
+                path.push_back(a);
                 _next_out[tip] = a;
                 tip = u;
-                path_nodes.push_back(tip);
                 goto next_step;
               }
@@ -1006 +1133 @@
 
             // Relabel tip node
-            min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
+            min_red_cost = std::numeric_limits<LargeCost>::max();
+            if (tip != start) {
+              int ra = _reverse[path.back()];
+              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
+            }
             for (int a = _first_out[tip]; a != last_out; ++a) {
-              rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
+              rc = _cost[a] + pi_tip - _pi[_target[a]];
               if (_res_cap[a] > 0 && rc < min_red_cost) {
                 min_red_cost = rc;
@@ -1014 +1145 @@
             }
             _pi[tip] -= min_red_cost + _epsilon;
-
-            // Reset the next arc of tip
             _next_out[tip] = _first_out[tip];
+            ++relabel_cnt;
 
             // Step back
             if (tip != start) {
-              path_nodes.pop_back();
-              tip = path_nodes.back();
+              tip = _source[path.back()];
+              path.pop_back();
             }
 
@@ -1029 +1159 @@
           // Augment along the found path (as much flow as possible)
           Value delta;
-          int u, v = path_nodes.front(), pa;
-          for (int i = 1; i < int(path_nodes.size()); ++i) {
+          int pa, u, v = start;
+          for (int i = 0; i != int(path.size()); ++i) {
+            pa = path[i];
             u = v;
-            v = path_nodes[i];
-            pa = pred_arc[v];
+            v = _target[pa];
             delta = std::min(_res_cap[pa], _excess[u]);
             _res_cap[pa] -= delta;
@@ -1042 +1172 @@
               _active_nodes.push_back(v);
           }
+
+          // Global update heuristic
+          if (relabel_cnt >= next_update_limit) {
+            globalUpdate();
+            next_update_limit += global_update_freq;
+          }
         }
       }
@@ -1049 +1185 @@
     void startPush() {
       // Paramters for heuristics
-      const int BF_HEURISTIC_EPSILON_BOUND = 1000;
-      const int BF_HEURISTIC_BOUND_FACTOR  = 3;
-
+      const int EARLY_TERM_EPSILON_LIMIT = 1000;
+      const double GLOBAL_UPDATE_FACTOR = 2.0;
+
+      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
+        (_res_node_num + _sup_node_num * _sup_node_num));
+      int next_update_limit = global_update_freq;
+
+      int relabel_cnt = 0;
+      
       // Perform cost scaling phases
       BoolVector hyper(_res_node_num, false);
+      LargeCostVector hyper_cost(_res_node_num);
       for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
                                         1 : _epsilon / _alpha )
       {
-        // "Early Termination" heuristic: use Bellman-Ford algorithm
-        // to check if the current flow is optimal
-        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
-          _arc_vec.clear();
-          _cost_vec.clear();
-          for (int j = 0; j != _res_arc_num; ++j) {
-            if (_res_cap[j] > 0) {
-              _arc_vec.push_back(IntPair(_source[j], _target[j]));
-              _cost_vec.push_back(_cost[j] + 1);
-            }
-          }
-          _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
-
-          BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
-          bf.init(0);
-          bool done = false;
-          int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num));
-          for (int i = 0; i < K && !done; ++i)
-            done = bf.processNextWeakRound();
-          if (done) break;
-        }
-
-        // Saturate arcs not satisfying the optimality condition
-        for (int a = 0; a != _res_arc_num; ++a) {
-          if (_res_cap[a] > 0 &&
-              _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
-            Value delta = _res_cap[a];
-            _excess[_source[a]] -= delta;
-            _excess[_target[a]] += delta;
-            _res_cap[a] = 0;
-            _res_cap[_reverse[a]] += delta;
-          }
-        }
-
-        // Find active nodes (i.e. nodes with positive excess)
-        for (int u = 0; u != _res_node_num; ++u) {
-          if (_excess[u] > 0) _active_nodes.push_back(u);
-        }
-
-        // Initialize the next arcs
-        for (int u = 0; u != _res_node_num; ++u) {
-          _next_out[u] = _first_out[u];
-        }
+        // Early termination heuristic
+        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
+          if (earlyTermination()) break;
+        }
+        
+        // Initialize current phase
+        initPhase();
 
         // Perform push and relabel operations
         while (_active_nodes.size() > 0) {
-          LargeCost min_red_cost, rc;
+          LargeCost min_red_cost, rc, pi_n;
           Value delta;
           int n, t, a, last_out = _res_arc_num;
 
+        next_node:
           // Select an active node (FIFO selection)
-        next_node:
           n = _active_nodes.front();
-          last_out = _sum_supply < 0 ?
-            _first_out[n+1] : _first_out[n+1] - 1;
-
+          last_out = _first_out[n+1];
+          pi_n = _pi[n];
+          
           // Perform push operations if there are admissible arcs
           if (_excess[n] > 0) {
             for (a = _next_out[n]; a != last_out; ++a) {
               if (_res_cap[a] > 0 &&
-                  _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) {
+                  _cost[a] + pi_n - _pi[_target[a]] < 0) {
                 delta = std::min(_res_cap[a], _excess[n]);
                 t = _target[a];
@@ -1123 +1230 @@
                 // Push-look-ahead heuristic
                 Value ahead = -_excess[t];
-                int last_out_t = _sum_supply < 0 ?
-                  _first_out[t+1] : _first_out[t+1] - 1;
+                int last_out_t = _first_out[t+1];
+                LargeCost pi_t = _pi[t];
                 for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
                   if (_res_cap[ta] > 0 && 
-                      _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0)
+                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
                     ahead += _res_cap[ta];
                   if (ahead >= delta) break;
@@ -1134 +1241 @@
 
                 // Push flow along the arc
-                if (ahead < delta) {
+                if (ahead < delta && !hyper[t]) {
                   _res_cap[a] -= ahead;
                   _res_cap[_reverse[a]] += ahead;
@@ -1141 +1248 @@
                   _active_nodes.push_front(t);
                   hyper[t] = true;
+                  hyper_cost[t] = _cost[a] + pi_n - pi_t;
                   _next_out[n] = a;
                   goto next_node;
@@ -1163 +1271 @@
           // Relabel the node if it is still active (or hyper)
           if (_excess[n] > 0 || hyper[n]) {
-            min_red_cost = std::numeric_limits<LargeCost>::max() / 2;
+             min_red_cost = hyper[n] ? -hyper_cost[n] :
+               std::numeric_limits<LargeCost>::max();
             for (int a = _first_out[n]; a != last_out; ++a) {
-              rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]];
+              rc = _cost[a] + pi_n - _pi[_target[a]];
               if (_res_cap[a] > 0 && rc < min_red_cost) {
                 min_red_cost = rc;
@@ -1171 +1280 @@
             }
             _pi[n] -= min_red_cost + _epsilon;
+            _next_out[n] = _first_out[n];
             hyper[n] = false;
-
-            // Reset the next arc
-            _next_out[n] = _first_out[n];
+            ++relabel_cnt;
           }
         
@@ -1184 +1292 @@
             _active_nodes.pop_front();
           }
+          
+          // Global update heuristic
+          if (relabel_cnt >= next_update_limit) {
+            globalUpdate();
+            for (int u = 0; u != _res_node_num; ++u)
+              hyper[u] = false;
+            next_update_limit += global_update_freq;
+          }
         }
       }

lemon/cost_scaling.h

@@ -105 +105 @@
   /// \tparam GR The digraph type the algorithm runs on.
   /// \tparam V The number type used for flow amounts, capacity bounds
-  /// and supply values in the algorithm. By default it is \c int.
+  /// and supply values in the algorithm. By default, it is \c int.
   /// \tparam C The number type used for costs and potentials in the
-  /// algorithm. By default it is the same as \c V.
+  /// algorithm. By default, it is the same as \c V.
+  /// \tparam TR The traits class that defines various types used by the
+  /// algorithm. By default, it is \ref CostScalingDefaultTraits
+  /// "CostScalingDefaultTraits<GR, V, C>".
+  /// In most cases, this parameter should not be set directly,
+  /// consider to use the named template parameters instead.
   ///
   /// \warning Both number types must be signed and all input data must
@@ -137 +142 @@
     ///
     /// The large cost type used for internal computations.
-    /// Using the \ref CostScalingDefaultTraits "default traits class",
-    /// it is \c long \c long if the \c Cost type is integer,
+    /// By default, it is \c long \c long if the \c Cost type is integer,
     /// otherwise it is \c double.
     typedef typename TR::LargeCost LargeCost;
@@ -341 +345 @@
       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
         "The cost type of CostScaling must be signed");
-
+      
+      // Reset data structures
+      reset();
+    }
+
+    /// \name Parameters
+    /// The parameters of the algorithm can be specified using these
+    /// functions.
+
+    /// @{
+
+    /// \brief Set the lower bounds on the arcs.
+    ///
+    /// This function sets the lower bounds on the arcs.
+    /// If it is not used before calling \ref run(), the lower bounds
+    /// will be set to zero on all arcs.
+    ///
+    /// \param map An arc map storing the lower bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template <typename LowerMap>
+    CostScaling& lowerMap(const LowerMap& map) {
+      _have_lower = true;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _lower[_arc_idf[a]] = map[a];
+        _lower[_arc_idb[a]] = map[a];
+      }
+      return *this;
+    }
+
+    /// \brief Set the upper bounds (capacities) on the arcs.
+    ///
+    /// This function sets the upper bounds (capacities) on the arcs.
+    /// If it is not used before calling \ref run(), the upper bounds
+    /// will be set to \ref INF on all arcs (i.e. the flow value will be
+    /// unbounded from above).
+    ///
+    /// \param map An arc map storing the upper bounds.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename UpperMap>
+    CostScaling& upperMap(const UpperMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _upper[_arc_idf[a]] = map[a];
+      }
+      return *this;
+    }
+
+    /// \brief Set the costs of the arcs.
+    ///
+    /// This function sets the costs of the arcs.
+    /// If it is not used before calling \ref run(), the costs
+    /// will be set to \c 1 on all arcs.
+    ///
+    /// \param map An arc map storing the costs.
+    /// Its \c Value type must be convertible to the \c Cost type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename CostMap>
+    CostScaling& costMap(const CostMap& map) {
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _scost[_arc_idf[a]] =  map[a];
+        _scost[_arc_idb[a]] = -map[a];
+      }
+      return *this;
+    }
+
+    /// \brief Set the supply values of the nodes.
+    ///
+    /// This function sets the supply values of the nodes.
+    /// If neither this function nor \ref stSupply() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// \param map A node map storing the supply values.
+    /// Its \c Value type must be convertible to the \c Value type
+    /// of the algorithm.
+    ///
+    /// \return <tt>(*this)</tt>
+    template<typename SupplyMap>
+    CostScaling& supplyMap(const SupplyMap& map) {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _supply[_node_id[n]] = map[n];
+      }
+      return *this;
+    }
+
+    /// \brief Set single source and target nodes and a supply value.
+    ///
+    /// This function sets a single source node and a single target node
+    /// and the required flow value.
+    /// If neither this function nor \ref supplyMap() is used before
+    /// calling \ref run(), the supply of each node will be set to zero.
+    ///
+    /// Using this function has the same effect as using \ref supplyMap()
+    /// with such a map in which \c k is assigned to \c s, \c -k is
+    /// assigned to \c t and all other nodes have zero supply value.
+    ///
+    /// \param s The source node.
+    /// \param t The target node.
+    /// \param k The required amount of flow from node \c s to node \c t
+    /// (i.e. the supply of \c s and the demand of \c t).
+    ///
+    /// \return <tt>(*this)</tt>
+    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      _supply[_node_id[s]] =  k;
+      _supply[_node_id[t]] = -k;
+      return *this;
+    }
+    
+    /// @}
+
+    /// \name Execution control
+    /// The algorithm can be executed using \ref run().
+
+    /// @{
+
+    /// \brief Run the algorithm.
+    ///
+    /// This function runs the algorithm.
+    /// The paramters can be specified using functions \ref lowerMap(),
+    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
+    /// For example,
+    /// \code
+    ///   CostScaling<ListDigraph> cs(graph);
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// This function can be called more than once. All the given parameters
+    /// are kept for the next call, unless \ref resetParams() or \ref reset()
+    /// is used, thus only the modified parameters have to be set again.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class (or the last \ref reset() call), then the \ref reset()
+    /// function must be called.
+    ///
+    /// \param method The internal method that will be used in the
+    /// algorithm. For more information, see \ref Method.
+    /// \param factor The cost scaling factor. It must be larger than one.
+    ///
+    /// \return \c INFEASIBLE if no feasible flow exists,
+    /// \n \c OPTIMAL if the problem has optimal solution
+    /// (i.e. it is feasible and bounded), and the algorithm has found
+    /// optimal flow and node potentials (primal and dual solutions),
+    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
+    /// and infinite upper bound. It means that the objective function
+    /// is unbounded on that arc, however, note that it could actually be
+    /// bounded over the feasible flows, but this algroithm cannot handle
+    /// these cases.
+    ///
+    /// \see ProblemType, Method
+    /// \see resetParams(), reset()
+    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
+      _alpha = factor;
+      ProblemType pt = init();
+      if (pt != OPTIMAL) return pt;
+      start(method);
+      return OPTIMAL;
+    }
+
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple \ref run() calls. Basically, all the given
+    /// parameters are kept for the next \ref run() call, unless
+    /// \ref resetParams() or \ref reset() is used.
+    /// If the underlying digraph was also modified after the construction
+    /// of the class or the last \ref reset() call, then the \ref reset()
+    /// function must be used, otherwise \ref resetParams() is sufficient.
+    ///
+    /// For example,
+    /// \code
+    ///   CostScaling<ListDigraph> cs(graph);
+    ///
+    ///   // First run
+    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
+    ///     .supplyMap(sup).run();
+    ///
+    ///   // Run again with modified cost map (resetParams() is not called,
+    ///   // so only the cost map have to be set again)
+    ///   cost[e] += 100;
+    ///   cs.costMap(cost).run();
+    ///
+    ///   // Run again from scratch using resetParams()
+    ///   // (the lower bounds will be set to zero on all arcs)
+    ///   cs.resetParams();
+    ///   cs.upperMap(capacity).costMap(cost)
+    ///     .supplyMap(sup).run();
+    /// \endcode
+    ///
+    /// \return <tt>(*this)</tt>
+    ///
+    /// \see reset(), run()
+    CostScaling& resetParams() {
+      for (int i = 0; i != _res_node_num; ++i) {
+        _supply[i] = 0;
+      }
+      int limit = _first_out[_root];
+      for (int j = 0; j != limit; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _scost[j] = _forward[j] ? 1 : -1;
+      }
+      for (int j = limit; j != _res_arc_num; ++j) {
+        _lower[j] = 0;
+        _upper[j] = INF;
+        _scost[j] = 0;
+        _scost[_reverse[j]] = 0;
+      }      
+      _have_lower = false;
+      return *this;
+    }
+
+    /// \brief Reset all the parameters that have been given before.
+    ///
+    /// This function resets all the paramaters that have been given
+    /// before using functions \ref lowerMap(), \ref upperMap(),
+    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
+    ///
+    /// It is useful for multiple run() calls. If this function is not
+    /// used, all the parameters given before are kept for the next
+    /// \ref run() call.
+    /// However, the underlying digraph must not be modified after this
+    /// class have been constructed, since it copies and extends the graph.
+    /// \return <tt>(*this)</tt>
+    CostScaling& reset() {
       // Resize vectors
       _node_num = countNodes(_graph);
@@ -409 +648 @@
       
       // Reset parameters
-      reset();
-    }
-
-    /// \name Parameters
-    /// The parameters of the algorithm can be specified using these
-    /// functions.
-
-    /// @{
-
-    /// \brief Set the lower bounds on the arcs.
-    ///
-    /// This function sets the lower bounds on the arcs.
-    /// If it is not used before calling \ref run(), the lower bounds
-    /// will be set to zero on all arcs.
-    ///
-    /// \param map An arc map storing the lower bounds.
-    /// Its \c Value type must be convertible to the \c Value type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template <typename LowerMap>
-    CostScaling& lowerMap(const LowerMap& map) {
-      _have_lower = true;
-      for (ArcIt a(_graph); a != INVALID; ++a) {
-        _lower[_arc_idf[a]] = map[a];
-        _lower[_arc_idb[a]] = map[a];
-      }
-      return *this;
-    }
-
-    /// \brief Set the upper bounds (capacities) on the arcs.
-    ///
-    /// This function sets the upper bounds (capacities) on the arcs.
-    /// If it is not used before calling \ref run(), the upper bounds
-    /// will be set to \ref INF on all arcs (i.e. the flow value will be
-    /// unbounded from above).
-    ///
-    /// \param map An arc map storing the upper bounds.
-    /// Its \c Value type must be convertible to the \c Value type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename UpperMap>
-    CostScaling& upperMap(const UpperMap& map) {
-      for (ArcIt a(_graph); a != INVALID; ++a) {
-        _upper[_arc_idf[a]] = map[a];
-      }
-      return *this;
-    }
-
-    /// \brief Set the costs of the arcs.
-    ///
-    /// This function sets the costs of the arcs.
-    /// If it is not used before calling \ref run(), the costs
-    /// will be set to \c 1 on all arcs.
-    ///
-    /// \param map An arc map storing the costs.
-    /// Its \c Value type must be convertible to the \c Cost type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename CostMap>
-    CostScaling& costMap(const CostMap& map) {
-      for (ArcIt a(_graph); a != INVALID; ++a) {
-        _scost[_arc_idf[a]] =  map[a];
-        _scost[_arc_idb[a]] = -map[a];
-      }
-      return *this;
-    }
-
-    /// \brief Set the supply values of the nodes.
-    ///
-    /// This function sets the supply values of the nodes.
-    /// If neither this function nor \ref stSupply() is used before
-    /// calling \ref run(), the supply of each node will be set to zero.
-    ///
-    /// \param map A node map storing the supply values.
-    /// Its \c Value type must be convertible to the \c Value type
-    /// of the algorithm.
-    ///
-    /// \return <tt>(*this)</tt>
-    template<typename SupplyMap>
-    CostScaling& supplyMap(const SupplyMap& map) {
-      for (NodeIt n(_graph); n != INVALID; ++n) {
-        _supply[_node_id[n]] = map[n];
-      }
-      return *this;
-    }
-
-    /// \brief Set single source and target nodes and a supply value.
-    ///
-    /// This function sets a single source node and a single target node
-    /// and the required flow value.
-    /// If neither this function nor \ref supplyMap() is used before
-    /// calling \ref run(), the supply of each node will be set to zero.
-    ///
-    /// Using this function has the same effect as using \ref supplyMap()
-    /// with such a map in which \c k is assigned to \c s, \c -k is
-    /// assigned to \c t and all other nodes have zero supply value.
-    ///
-    /// \param s The source node.
-    /// \param t The target node.
-    /// \param k The required amount of flow from node \c s to node \c t
-    /// (i.e. the supply of \c s and the demand of \c t).
-    ///
-    /// \return <tt>(*this)</tt>
-    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
-      for (int i = 0; i != _res_node_num; ++i) {
-        _supply[i] = 0;
-      }
-      _supply[_node_id[s]] =  k;
-      _supply[_node_id[t]] = -k;
-      return *this;
-    }
-    
-    /// @}
-
-    /// \name Execution control
-    /// The algorithm can be executed using \ref run().
-
-    /// @{
-
-    /// \brief Run the algorithm.
-    ///
-    /// This function runs the algorithm.
-    /// The paramters can be specified using functions \ref lowerMap(),
-    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
-    /// For example,
-    /// \code
-    ///   CostScaling<ListDigraph> cs(graph);
-    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
-    ///     .supplyMap(sup).run();
-    /// \endcode
-    ///
-    /// This function can be called more than once. All the parameters
-    /// that have been given are kept for the next call, unless
-    /// \ref reset() is called, thus only the modified parameters
-    /// 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 and extends the graph.
-    ///
-    /// \param method The internal method that will be used in the
-    /// algorithm. For more information, see \ref Method.
-    /// \param factor The cost scaling factor. It must be larger than one.
-    ///
-    /// \return \c INFEASIBLE if no feasible flow exists,
-    /// \n \c OPTIMAL if the problem has optimal solution
-    /// (i.e. it is feasible and bounded), and the algorithm has found
-    /// optimal flow and node potentials (primal and dual solutions),
-    /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
-    /// and infinite upper bound. It means that the objective function
-    /// is unbounded on that arc, however, note that it could actually be
-    /// bounded over the feasible flows, but this algroithm cannot handle
-    /// these cases.
-    ///
-    /// \see ProblemType, Method
-    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
-      _alpha = factor;
-      ProblemType pt = init();
-      if (pt != OPTIMAL) return pt;
-      start(method);
-      return OPTIMAL;
-    }
-
-    /// \brief Reset all the parameters that have been given before.
-    ///
-    /// This function resets all the paramaters that have been given
-    /// before using functions \ref lowerMap(), \ref upperMap(),
-    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
-    ///
-    /// It is useful for multiple run() calls. If this function is not
-    /// used, all the parameters given before are kept for the next
-    /// \ref run() call.
-    /// However, the underlying digraph must not be modified after this
-    /// class have been constructed, since it copies and extends the graph.
-    ///
-    /// For example,
-    /// \code
-    ///   CostScaling<ListDigraph> cs(graph);
-    ///
-    ///   // First run
-    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
-    ///     .supplyMap(sup).run();
-    ///
-    ///   // Run again with modified cost map (reset() is not called,
-    ///   // so only the cost map have to be set again)
-    ///   cost[e] += 100;
-    ///   cs.costMap(cost).run();
-    ///
-    ///   // Run again from scratch using reset()
-    ///   // (the lower bounds will be set to zero on all arcs)
-    ///   cs.reset();
-    ///   cs.upperMap(capacity).costMap(cost)
-    ///     .supplyMap(sup).run();
-    /// \endcode
-    ///
-    /// \return <tt>(*this)</tt>
-    CostScaling& reset() {
-      for (int i = 0; i != _res_node_num; ++i) {
-        _supply[i] = 0;
-      }
-      int limit = _first_out[_root];
-      for (int j = 0; j != limit; ++j) {
-        _lower[j] = 0;
-        _upper[j] = INF;
-        _scost[j] = _forward[j] ? 1 : -1;
-      }
-      for (int j = limit; j != _res_arc_num; ++j) {
-        _lower[j] = 0;
-        _upper[j] = INF;
-        _scost[j] = 0;
-        _scost[_reverse[j]] = 0;
-      }      
-      _have_lower = false;
+      resetParams();
       return *this;
     }