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