1.1 --- a/lemon/cost_scaling.h Thu Mar 17 09:02:51 2011 +0100
1.2 +++ b/lemon/cost_scaling.h Tue Mar 15 17:59:57 2011 +0100
1.3 @@ -575,18 +575,25 @@
1.4 return *this;
1.5 }
1.6
1.7 - /// \brief Reset all the parameters that have been given before.
1.8 + /// \brief Reset the internal data structures and all the parameters
1.9 + /// that have been given before.
1.10 ///
1.11 - /// This function resets all the paramaters that have been given
1.12 - /// before using functions \ref lowerMap(), \ref upperMap(),
1.13 - /// \ref costMap(), \ref supplyMap(), \ref stSupply().
1.14 + /// This function resets the internal data structures and all the
1.15 + /// paramaters that have been given before using functions \ref lowerMap(),
1.16 + /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
1.17 ///
1.18 - /// It is useful for multiple run() calls. If this function is not
1.19 - /// used, all the parameters given before are kept for the next
1.20 - /// \ref run() call.
1.21 - /// However, the underlying digraph must not be modified after this
1.22 - /// class have been constructed, since it copies and extends the graph.
1.23 + /// It is useful for multiple \ref run() calls. By default, all the given
1.24 + /// parameters are kept for the next \ref run() call, unless
1.25 + /// \ref resetParams() or \ref reset() is used.
1.26 + /// If the underlying digraph was also modified after the construction
1.27 + /// of the class or the last \ref reset() call, then the \ref reset()
1.28 + /// function must be used, otherwise \ref resetParams() is sufficient.
1.29 + ///
1.30 + /// See \ref resetParams() for examples.
1.31 + ///
1.32 /// \return <tt>(*this)</tt>
1.33 + ///
1.34 + /// \see resetParams(), run()
1.35 CostScaling& reset() {
1.36 // Resize vectors
1.37 _node_num = countNodes(_graph);
1.38 @@ -890,14 +897,6 @@
1.39 }
1.40 }
1.41
1.42 - return OPTIMAL;
1.43 - }
1.44 -
1.45 - // Execute the algorithm and transform the results
1.46 - void start(Method method) {
1.47 - // Maximum path length for partial augment
1.48 - const int MAX_PATH_LENGTH = 4;
1.49 -
1.50 // Initialize data structures for buckets
1.51 _max_rank = _alpha * _res_node_num;
1.52 _buckets.resize(_max_rank);
1.53 @@ -905,7 +904,13 @@
1.54 _bucket_prev.resize(_res_node_num + 1);
1.55 _rank.resize(_res_node_num + 1);
1.56
1.57 - // Execute the algorithm
1.58 + return OPTIMAL;
1.59 + }
1.60 +
1.61 + // Execute the algorithm and transform the results
1.62 + void start(Method method) {
1.63 + const int MAX_PARTIAL_PATH_LENGTH = 4;
1.64 +
1.65 switch (method) {
1.66 case PUSH:
1.67 startPush();
1.68 @@ -914,7 +919,7 @@
1.69 startAugment(_res_node_num - 1);
1.70 break;
1.71 case PARTIAL_AUGMENT:
1.72 - startAugment(MAX_PATH_LENGTH);
1.73 + startAugment(MAX_PARTIAL_PATH_LENGTH);
1.74 break;
1.75 }
1.76
1.77 @@ -951,13 +956,15 @@
1.78 int last_out = _first_out[u+1];
1.79 LargeCost pi_u = _pi[u];
1.80 for (int a = _first_out[u]; a != last_out; ++a) {
1.81 - int v = _target[a];
1.82 - if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
1.83 - Value delta = _res_cap[a];
1.84 - _excess[u] -= delta;
1.85 - _excess[v] += delta;
1.86 - _res_cap[a] = 0;
1.87 - _res_cap[_reverse[a]] += delta;
1.88 + Value delta = _res_cap[a];
1.89 + if (delta > 0) {
1.90 + int v = _target[a];
1.91 + if (_cost[a] + pi_u - _pi[v] < 0) {
1.92 + _excess[u] -= delta;
1.93 + _excess[v] += delta;
1.94 + _res_cap[a] = 0;
1.95 + _res_cap[_reverse[a]] += delta;
1.96 + }
1.97 }
1.98 }
1.99 }
1.100 @@ -1001,25 +1008,27 @@
1.101
1.102 // Global potential update heuristic
1.103 void globalUpdate() {
1.104 - int bucket_end = _root + 1;
1.105 + const int bucket_end = _root + 1;
1.106
1.107 // Initialize buckets
1.108 for (int r = 0; r != _max_rank; ++r) {
1.109 _buckets[r] = bucket_end;
1.110 }
1.111 Value total_excess = 0;
1.112 + int b0 = bucket_end;
1.113 for (int i = 0; i != _res_node_num; ++i) {
1.114 if (_excess[i] < 0) {
1.115 _rank[i] = 0;
1.116 - _bucket_next[i] = _buckets[0];
1.117 - _bucket_prev[_buckets[0]] = i;
1.118 - _buckets[0] = i;
1.119 + _bucket_next[i] = b0;
1.120 + _bucket_prev[b0] = i;
1.121 + b0 = i;
1.122 } else {
1.123 total_excess += _excess[i];
1.124 _rank[i] = _max_rank;
1.125 }
1.126 }
1.127 if (total_excess == 0) return;
1.128 + _buckets[0] = b0;
1.129
1.130 // Search the buckets
1.131 int r = 0;
1.132 @@ -1041,8 +1050,9 @@
1.133 // Compute the new rank of v
1.134 LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
1.135 int new_rank_v = old_rank_v;
1.136 - if (nrc < LargeCost(_max_rank))
1.137 - new_rank_v = r + 1 + int(nrc);
1.138 + if (nrc < LargeCost(_max_rank)) {
1.139 + new_rank_v = r + 1 + static_cast<int>(nrc);
1.140 + }
1.141
1.142 // Change the rank of v
1.143 if (new_rank_v < old_rank_v) {
1.144 @@ -1054,14 +1064,16 @@
1.145 if (_buckets[old_rank_v] == v) {
1.146 _buckets[old_rank_v] = _bucket_next[v];
1.147 } else {
1.148 - _bucket_next[_bucket_prev[v]] = _bucket_next[v];
1.149 - _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
1.150 + int pv = _bucket_prev[v], nv = _bucket_next[v];
1.151 + _bucket_next[pv] = nv;
1.152 + _bucket_prev[nv] = pv;
1.153 }
1.154 }
1.155
1.156 - // Insert v to its new bucket
1.157 - _bucket_next[v] = _buckets[new_rank_v];
1.158 - _bucket_prev[_buckets[new_rank_v]] = v;
1.159 + // Insert v into its new bucket
1.160 + int nv = _buckets[new_rank_v];
1.161 + _bucket_next[v] = nv;
1.162 + _bucket_prev[nv] = v;
1.163 _buckets[new_rank_v] = v;
1.164 }
1.165 }