1.1 --- a/lemon/capacity_scaling.h Tue Feb 09 23:29:51 2010 +0100
1.2 +++ b/lemon/capacity_scaling.h Wed Feb 10 19:05:20 2010 +0100
1.3 @@ -314,69 +314,7 @@
1.4 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
1.5 "The cost type of CapacityScaling must be signed");
1.6
1.7 - // Resize vectors
1.8 - _node_num = countNodes(_graph);
1.9 - _arc_num = countArcs(_graph);
1.10 - _res_arc_num = 2 * (_arc_num + _node_num);
1.11 - _root = _node_num;
1.12 - ++_node_num;
1.13 -
1.14 - _first_out.resize(_node_num + 1);
1.15 - _forward.resize(_res_arc_num);
1.16 - _source.resize(_res_arc_num);
1.17 - _target.resize(_res_arc_num);
1.18 - _reverse.resize(_res_arc_num);
1.19 -
1.20 - _lower.resize(_res_arc_num);
1.21 - _upper.resize(_res_arc_num);
1.22 - _cost.resize(_res_arc_num);
1.23 - _supply.resize(_node_num);
1.24 -
1.25 - _res_cap.resize(_res_arc_num);
1.26 - _pi.resize(_node_num);
1.27 - _excess.resize(_node_num);
1.28 - _pred.resize(_node_num);
1.29 -
1.30 - // Copy the graph
1.31 - int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
1.32 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.33 - _node_id[n] = i;
1.34 - }
1.35 - i = 0;
1.36 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.37 - _first_out[i] = j;
1.38 - for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
1.39 - _arc_idf[a] = j;
1.40 - _forward[j] = true;
1.41 - _source[j] = i;
1.42 - _target[j] = _node_id[_graph.runningNode(a)];
1.43 - }
1.44 - for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
1.45 - _arc_idb[a] = j;
1.46 - _forward[j] = false;
1.47 - _source[j] = i;
1.48 - _target[j] = _node_id[_graph.runningNode(a)];
1.49 - }
1.50 - _forward[j] = false;
1.51 - _source[j] = i;
1.52 - _target[j] = _root;
1.53 - _reverse[j] = k;
1.54 - _forward[k] = true;
1.55 - _source[k] = _root;
1.56 - _target[k] = i;
1.57 - _reverse[k] = j;
1.58 - ++j; ++k;
1.59 - }
1.60 - _first_out[i] = j;
1.61 - _first_out[_node_num] = k;
1.62 - for (ArcIt a(_graph); a != INVALID; ++a) {
1.63 - int fi = _arc_idf[a];
1.64 - int bi = _arc_idb[a];
1.65 - _reverse[fi] = bi;
1.66 - _reverse[bi] = fi;
1.67 - }
1.68 -
1.69 - // Reset parameters
1.70 + // Reset data structures
1.71 reset();
1.72 }
1.73
1.74 @@ -511,12 +449,12 @@
1.75 /// .supplyMap(sup).run();
1.76 /// \endcode
1.77 ///
1.78 - /// This function can be called more than once. All the parameters
1.79 - /// that have been given are kept for the next call, unless
1.80 - /// \ref reset() is called, thus only the modified parameters
1.81 - /// have to be set again. See \ref reset() for examples.
1.82 - /// However, the underlying digraph must not be modified after this
1.83 - /// class have been constructed, since it copies and extends the graph.
1.84 + /// This function can be called more than once. All the given parameters
1.85 + /// are kept for the next call, unless \ref resetParams() or \ref reset()
1.86 + /// is used, thus only the modified parameters have to be set again.
1.87 + /// If the underlying digraph was also modified after the construction
1.88 + /// of the class (or the last \ref reset() call), then the \ref reset()
1.89 + /// function must be called.
1.90 ///
1.91 /// \param factor The capacity scaling factor. It must be larger than
1.92 /// one to use scaling. If it is less or equal to one, then scaling
1.93 @@ -533,6 +471,7 @@
1.94 /// these cases.
1.95 ///
1.96 /// \see ProblemType
1.97 + /// \see resetParams(), reset()
1.98 ProblemType run(int factor = 4) {
1.99 _factor = factor;
1.100 ProblemType pt = init();
1.101 @@ -546,11 +485,12 @@
1.102 /// before using functions \ref lowerMap(), \ref upperMap(),
1.103 /// \ref costMap(), \ref supplyMap(), \ref stSupply().
1.104 ///
1.105 - /// It is useful for multiple run() calls. If this function is not
1.106 - /// used, all the parameters given before are kept for the next
1.107 - /// \ref run() call.
1.108 - /// However, the underlying digraph must not be modified after this
1.109 - /// class have been constructed, since it copies and extends the graph.
1.110 + /// It is useful for multiple \ref run() calls. Basically, all the given
1.111 + /// parameters are kept for the next \ref run() call, unless
1.112 + /// \ref resetParams() or \ref reset() is used.
1.113 + /// If the underlying digraph was also modified after the construction
1.114 + /// of the class or the last \ref reset() call, then the \ref reset()
1.115 + /// function must be used, otherwise \ref resetParams() is sufficient.
1.116 ///
1.117 /// For example,
1.118 /// \code
1.119 @@ -560,20 +500,22 @@
1.120 /// cs.lowerMap(lower).upperMap(upper).costMap(cost)
1.121 /// .supplyMap(sup).run();
1.122 ///
1.123 - /// // Run again with modified cost map (reset() is not called,
1.124 + /// // Run again with modified cost map (resetParams() is not called,
1.125 /// // so only the cost map have to be set again)
1.126 /// cost[e] += 100;
1.127 /// cs.costMap(cost).run();
1.128 ///
1.129 - /// // Run again from scratch using reset()
1.130 + /// // Run again from scratch using resetParams()
1.131 /// // (the lower bounds will be set to zero on all arcs)
1.132 - /// cs.reset();
1.133 + /// cs.resetParams();
1.134 /// cs.upperMap(capacity).costMap(cost)
1.135 /// .supplyMap(sup).run();
1.136 /// \endcode
1.137 ///
1.138 /// \return <tt>(*this)</tt>
1.139 - CapacityScaling& reset() {
1.140 + ///
1.141 + /// \see reset(), run()
1.142 + CapacityScaling& resetParams() {
1.143 for (int i = 0; i != _node_num; ++i) {
1.144 _supply[i] = 0;
1.145 }
1.146 @@ -586,6 +528,93 @@
1.147 return *this;
1.148 }
1.149
1.150 + /// \brief Reset the internal data structures and all the parameters
1.151 + /// that have been given before.
1.152 + ///
1.153 + /// This function resets the internal data structures and all the
1.154 + /// paramaters that have been given before using functions \ref lowerMap(),
1.155 + /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
1.156 + ///
1.157 + /// It is useful for multiple \ref run() calls. Basically, all the given
1.158 + /// parameters are kept for the next \ref run() call, unless
1.159 + /// \ref resetParams() or \ref reset() is used.
1.160 + /// If the underlying digraph was also modified after the construction
1.161 + /// of the class or the last \ref reset() call, then the \ref reset()
1.162 + /// function must be used, otherwise \ref resetParams() is sufficient.
1.163 + ///
1.164 + /// See \ref resetParams() for examples.
1.165 + ///
1.166 + /// \return <tt>(*this)</tt>
1.167 + ///
1.168 + /// \see resetParams(), run()
1.169 + CapacityScaling& reset() {
1.170 + // Resize vectors
1.171 + _node_num = countNodes(_graph);
1.172 + _arc_num = countArcs(_graph);
1.173 + _res_arc_num = 2 * (_arc_num + _node_num);
1.174 + _root = _node_num;
1.175 + ++_node_num;
1.176 +
1.177 + _first_out.resize(_node_num + 1);
1.178 + _forward.resize(_res_arc_num);
1.179 + _source.resize(_res_arc_num);
1.180 + _target.resize(_res_arc_num);
1.181 + _reverse.resize(_res_arc_num);
1.182 +
1.183 + _lower.resize(_res_arc_num);
1.184 + _upper.resize(_res_arc_num);
1.185 + _cost.resize(_res_arc_num);
1.186 + _supply.resize(_node_num);
1.187 +
1.188 + _res_cap.resize(_res_arc_num);
1.189 + _pi.resize(_node_num);
1.190 + _excess.resize(_node_num);
1.191 + _pred.resize(_node_num);
1.192 +
1.193 + // Copy the graph
1.194 + int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
1.195 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.196 + _node_id[n] = i;
1.197 + }
1.198 + i = 0;
1.199 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.200 + _first_out[i] = j;
1.201 + for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
1.202 + _arc_idf[a] = j;
1.203 + _forward[j] = true;
1.204 + _source[j] = i;
1.205 + _target[j] = _node_id[_graph.runningNode(a)];
1.206 + }
1.207 + for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
1.208 + _arc_idb[a] = j;
1.209 + _forward[j] = false;
1.210 + _source[j] = i;
1.211 + _target[j] = _node_id[_graph.runningNode(a)];
1.212 + }
1.213 + _forward[j] = false;
1.214 + _source[j] = i;
1.215 + _target[j] = _root;
1.216 + _reverse[j] = k;
1.217 + _forward[k] = true;
1.218 + _source[k] = _root;
1.219 + _target[k] = i;
1.220 + _reverse[k] = j;
1.221 + ++j; ++k;
1.222 + }
1.223 + _first_out[i] = j;
1.224 + _first_out[_node_num] = k;
1.225 + for (ArcIt a(_graph); a != INVALID; ++a) {
1.226 + int fi = _arc_idf[a];
1.227 + int bi = _arc_idb[a];
1.228 + _reverse[fi] = bi;
1.229 + _reverse[bi] = fi;
1.230 + }
1.231 +
1.232 + // Reset parameters
1.233 + resetParams();
1.234 + return *this;
1.235 + }
1.236 +
1.237 /// @}
1.238
1.239 /// \name Query Functions