1.1 --- a/lemon/capacity_scaling.h Thu Nov 12 23:30:45 2009 +0100
1.2 +++ b/lemon/capacity_scaling.h Thu Nov 12 23:34:35 2009 +0100
1.3 @@ -173,7 +173,7 @@
1.4 IntVector _deficit_nodes;
1.5
1.6 Value _delta;
1.7 - int _phase_num;
1.8 + int _factor;
1.9 IntVector _pred;
1.10
1.11 public:
1.12 @@ -513,12 +513,11 @@
1.13 /// \ref reset() is called, thus only the modified parameters
1.14 /// have to be set again. See \ref reset() for examples.
1.15 /// However the underlying digraph must not be modified after this
1.16 - /// class have been constructed, since it copies the digraph.
1.17 + /// class have been constructed, since it copies and extends the graph.
1.18 ///
1.19 - /// \param scaling Enable or disable capacity scaling.
1.20 - /// If the maximum upper bound and/or the amount of total supply
1.21 - /// is rather small, the algorithm could be slightly faster without
1.22 - /// scaling.
1.23 + /// \param factor The capacity scaling factor. It must be larger than
1.24 + /// one to use scaling. If it is less or equal to one, then scaling
1.25 + /// will be disabled.
1.26 ///
1.27 /// \return \c INFEASIBLE if no feasible flow exists,
1.28 /// \n \c OPTIMAL if the problem has optimal solution
1.29 @@ -531,8 +530,9 @@
1.30 /// these cases.
1.31 ///
1.32 /// \see ProblemType
1.33 - ProblemType run(bool scaling = true) {
1.34 - ProblemType pt = init(scaling);
1.35 + ProblemType run(int factor = 4) {
1.36 + _factor = factor;
1.37 + ProblemType pt = init();
1.38 if (pt != OPTIMAL) return pt;
1.39 return start();
1.40 }
1.41 @@ -546,7 +546,7 @@
1.42 /// It is useful for multiple run() calls. If this function is not
1.43 /// used, all the parameters given before are kept for the next
1.44 /// \ref run() call.
1.45 - /// However the underlying digraph must not be modified after this
1.46 + /// However, the underlying digraph must not be modified after this
1.47 /// class have been constructed, since it copies and extends the graph.
1.48 ///
1.49 /// For example,
1.50 @@ -677,7 +677,7 @@
1.51 private:
1.52
1.53 // Initialize the algorithm
1.54 - ProblemType init(bool scaling) {
1.55 + ProblemType init() {
1.56 if (_node_num == 0) return INFEASIBLE;
1.57
1.58 // Check the sum of supply values
1.59 @@ -758,7 +758,7 @@
1.60 }
1.61
1.62 // Initialize delta value
1.63 - if (scaling) {
1.64 + if (_factor > 1) {
1.65 // With scaling
1.66 Value max_sup = 0, max_dem = 0;
1.67 for (int i = 0; i != _node_num; ++i) {
1.68 @@ -770,9 +770,7 @@
1.69 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
1.70 }
1.71 max_sup = std::min(std::min(max_sup, max_dem), max_cap);
1.72 - _phase_num = 0;
1.73 - for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
1.74 - ++_phase_num;
1.75 + for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
1.76 } else {
1.77 // Without scaling
1.78 _delta = 1;
1.79 @@ -811,8 +809,6 @@
1.80 ProblemType startWithScaling() {
1.81 // Perform capacity scaling phases
1.82 int s, t;
1.83 - int phase_cnt = 0;
1.84 - int factor = 4;
1.85 ResidualDijkstra _dijkstra(*this);
1.86 while (true) {
1.87 // Saturate all arcs not satisfying the optimality condition
1.88 @@ -887,8 +883,7 @@
1.89 }
1.90
1.91 if (_delta == 1) break;
1.92 - if (++phase_cnt == _phase_num / 4) factor = 2;
1.93 - _delta = _delta <= factor ? 1 : _delta / factor;
1.94 + _delta = _delta <= _factor ? 1 : _delta / _factor;
1.95 }
1.96
1.97 return OPTIMAL;