1.1 --- a/lemon/capacity_scaling.h Tue Feb 09 23:29:51 2010 +0100
1.2 +++ b/lemon/capacity_scaling.h Sat Feb 20 18:39:03 2010 +0100
1.3 @@ -134,9 +134,10 @@
1.4 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.5
1.6 typedef std::vector<int> IntVector;
1.7 - typedef std::vector<char> BoolVector;
1.8 typedef std::vector<Value> ValueVector;
1.9 typedef std::vector<Cost> CostVector;
1.10 + typedef std::vector<char> BoolVector;
1.11 + // Note: vector<char> is used instead of vector<bool> for efficiency reasons
1.12
1.13 private:
1.14
1.15 @@ -764,15 +765,15 @@
1.16 // Initialize delta value
1.17 if (_factor > 1) {
1.18 // With scaling
1.19 - Value max_sup = 0, max_dem = 0;
1.20 - for (int i = 0; i != _node_num; ++i) {
1.21 + Value max_sup = 0, max_dem = 0, max_cap = 0;
1.22 + for (int i = 0; i != _root; ++i) {
1.23 Value ex = _excess[i];
1.24 if ( ex > max_sup) max_sup = ex;
1.25 if (-ex > max_dem) max_dem = -ex;
1.26 - }
1.27 - Value max_cap = 0;
1.28 - for (int j = 0; j != _res_arc_num; ++j) {
1.29 - if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
1.30 + int last_out = _first_out[i+1] - 1;
1.31 + for (int j = _first_out[i]; j != last_out; ++j) {
1.32 + if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
1.33 + }
1.34 }
1.35 max_sup = std::min(std::min(max_sup, max_dem), max_cap);
1.36 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;