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
2.1 --- a/lemon/cost_scaling.h Tue Feb 09 23:29:51 2010 +0100
2.2 +++ b/lemon/cost_scaling.h Wed Feb 10 19:05:20 2010 +0100
2.3 @@ -332,74 +332,8 @@
2.4 "The flow type of CostScaling must be signed");
2.5 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
2.6 "The cost type of CostScaling must be signed");
2.7 -
2.8 - // Resize vectors
2.9 - _node_num = countNodes(_graph);
2.10 - _arc_num = countArcs(_graph);
2.11 - _res_node_num = _node_num + 1;
2.12 - _res_arc_num = 2 * (_arc_num + _node_num);
2.13 - _root = _node_num;
2.14 -
2.15 - _first_out.resize(_res_node_num + 1);
2.16 - _forward.resize(_res_arc_num);
2.17 - _source.resize(_res_arc_num);
2.18 - _target.resize(_res_arc_num);
2.19 - _reverse.resize(_res_arc_num);
2.20 -
2.21 - _lower.resize(_res_arc_num);
2.22 - _upper.resize(_res_arc_num);
2.23 - _scost.resize(_res_arc_num);
2.24 - _supply.resize(_res_node_num);
2.25
2.26 - _res_cap.resize(_res_arc_num);
2.27 - _cost.resize(_res_arc_num);
2.28 - _pi.resize(_res_node_num);
2.29 - _excess.resize(_res_node_num);
2.30 - _next_out.resize(_res_node_num);
2.31 -
2.32 - _arc_vec.reserve(_res_arc_num);
2.33 - _cost_vec.reserve(_res_arc_num);
2.34 -
2.35 - // Copy the graph
2.36 - int i = 0, j = 0, k = 2 * _arc_num + _node_num;
2.37 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
2.38 - _node_id[n] = i;
2.39 - }
2.40 - i = 0;
2.41 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
2.42 - _first_out[i] = j;
2.43 - for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
2.44 - _arc_idf[a] = j;
2.45 - _forward[j] = true;
2.46 - _source[j] = i;
2.47 - _target[j] = _node_id[_graph.runningNode(a)];
2.48 - }
2.49 - for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
2.50 - _arc_idb[a] = j;
2.51 - _forward[j] = false;
2.52 - _source[j] = i;
2.53 - _target[j] = _node_id[_graph.runningNode(a)];
2.54 - }
2.55 - _forward[j] = false;
2.56 - _source[j] = i;
2.57 - _target[j] = _root;
2.58 - _reverse[j] = k;
2.59 - _forward[k] = true;
2.60 - _source[k] = _root;
2.61 - _target[k] = i;
2.62 - _reverse[k] = j;
2.63 - ++j; ++k;
2.64 - }
2.65 - _first_out[i] = j;
2.66 - _first_out[_res_node_num] = k;
2.67 - for (ArcIt a(_graph); a != INVALID; ++a) {
2.68 - int fi = _arc_idf[a];
2.69 - int bi = _arc_idb[a];
2.70 - _reverse[fi] = bi;
2.71 - _reverse[bi] = fi;
2.72 - }
2.73 -
2.74 - // Reset parameters
2.75 + // Reset data structures
2.76 reset();
2.77 }
2.78
2.79 @@ -534,12 +468,12 @@
2.80 /// .supplyMap(sup).run();
2.81 /// \endcode
2.82 ///
2.83 - /// This function can be called more than once. All the parameters
2.84 - /// that have been given are kept for the next call, unless
2.85 - /// \ref reset() is called, thus only the modified parameters
2.86 - /// have to be set again. See \ref reset() for examples.
2.87 - /// However, the underlying digraph must not be modified after this
2.88 - /// class have been constructed, since it copies and extends the graph.
2.89 + /// This function can be called more than once. All the given parameters
2.90 + /// are kept for the next call, unless \ref resetParams() or \ref reset()
2.91 + /// is used, thus only the modified parameters have to be set again.
2.92 + /// If the underlying digraph was also modified after the construction
2.93 + /// of the class (or the last \ref reset() call), then the \ref reset()
2.94 + /// function must be called.
2.95 ///
2.96 /// \param method The internal method that will be used in the
2.97 /// algorithm. For more information, see \ref Method.
2.98 @@ -556,6 +490,7 @@
2.99 /// these cases.
2.100 ///
2.101 /// \see ProblemType, Method
2.102 + /// \see resetParams(), reset()
2.103 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
2.104 _alpha = factor;
2.105 ProblemType pt = init();
2.106 @@ -570,11 +505,12 @@
2.107 /// before using functions \ref lowerMap(), \ref upperMap(),
2.108 /// \ref costMap(), \ref supplyMap(), \ref stSupply().
2.109 ///
2.110 - /// It is useful for multiple run() calls. If this function is not
2.111 - /// used, all the parameters given before are kept for the next
2.112 - /// \ref run() call.
2.113 - /// However, the underlying digraph must not be modified after this
2.114 - /// class have been constructed, since it copies and extends the graph.
2.115 + /// It is useful for multiple \ref run() calls. Basically, all the given
2.116 + /// parameters are kept for the next \ref run() call, unless
2.117 + /// \ref resetParams() or \ref reset() is used.
2.118 + /// If the underlying digraph was also modified after the construction
2.119 + /// of the class or the last \ref reset() call, then the \ref reset()
2.120 + /// function must be used, otherwise \ref resetParams() is sufficient.
2.121 ///
2.122 /// For example,
2.123 /// \code
2.124 @@ -584,20 +520,22 @@
2.125 /// cs.lowerMap(lower).upperMap(upper).costMap(cost)
2.126 /// .supplyMap(sup).run();
2.127 ///
2.128 - /// // Run again with modified cost map (reset() is not called,
2.129 + /// // Run again with modified cost map (resetParams() is not called,
2.130 /// // so only the cost map have to be set again)
2.131 /// cost[e] += 100;
2.132 /// cs.costMap(cost).run();
2.133 ///
2.134 - /// // Run again from scratch using reset()
2.135 + /// // Run again from scratch using resetParams()
2.136 /// // (the lower bounds will be set to zero on all arcs)
2.137 - /// cs.reset();
2.138 + /// cs.resetParams();
2.139 /// cs.upperMap(capacity).costMap(cost)
2.140 /// .supplyMap(sup).run();
2.141 /// \endcode
2.142 ///
2.143 /// \return <tt>(*this)</tt>
2.144 - CostScaling& reset() {
2.145 + ///
2.146 + /// \see reset(), run()
2.147 + CostScaling& resetParams() {
2.148 for (int i = 0; i != _res_node_num; ++i) {
2.149 _supply[i] = 0;
2.150 }
2.151 @@ -617,6 +555,90 @@
2.152 return *this;
2.153 }
2.154
2.155 + /// \brief Reset all the parameters that have been given before.
2.156 + ///
2.157 + /// This function resets all the paramaters that have been given
2.158 + /// before using functions \ref lowerMap(), \ref upperMap(),
2.159 + /// \ref costMap(), \ref supplyMap(), \ref stSupply().
2.160 + ///
2.161 + /// It is useful for multiple run() calls. If this function is not
2.162 + /// used, all the parameters given before are kept for the next
2.163 + /// \ref run() call.
2.164 + /// However, the underlying digraph must not be modified after this
2.165 + /// class have been constructed, since it copies and extends the graph.
2.166 + /// \return <tt>(*this)</tt>
2.167 + CostScaling& reset() {
2.168 + // Resize vectors
2.169 + _node_num = countNodes(_graph);
2.170 + _arc_num = countArcs(_graph);
2.171 + _res_node_num = _node_num + 1;
2.172 + _res_arc_num = 2 * (_arc_num + _node_num);
2.173 + _root = _node_num;
2.174 +
2.175 + _first_out.resize(_res_node_num + 1);
2.176 + _forward.resize(_res_arc_num);
2.177 + _source.resize(_res_arc_num);
2.178 + _target.resize(_res_arc_num);
2.179 + _reverse.resize(_res_arc_num);
2.180 +
2.181 + _lower.resize(_res_arc_num);
2.182 + _upper.resize(_res_arc_num);
2.183 + _scost.resize(_res_arc_num);
2.184 + _supply.resize(_res_node_num);
2.185 +
2.186 + _res_cap.resize(_res_arc_num);
2.187 + _cost.resize(_res_arc_num);
2.188 + _pi.resize(_res_node_num);
2.189 + _excess.resize(_res_node_num);
2.190 + _next_out.resize(_res_node_num);
2.191 +
2.192 + _arc_vec.reserve(_res_arc_num);
2.193 + _cost_vec.reserve(_res_arc_num);
2.194 +
2.195 + // Copy the graph
2.196 + int i = 0, j = 0, k = 2 * _arc_num + _node_num;
2.197 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
2.198 + _node_id[n] = i;
2.199 + }
2.200 + i = 0;
2.201 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
2.202 + _first_out[i] = j;
2.203 + for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
2.204 + _arc_idf[a] = j;
2.205 + _forward[j] = true;
2.206 + _source[j] = i;
2.207 + _target[j] = _node_id[_graph.runningNode(a)];
2.208 + }
2.209 + for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
2.210 + _arc_idb[a] = j;
2.211 + _forward[j] = false;
2.212 + _source[j] = i;
2.213 + _target[j] = _node_id[_graph.runningNode(a)];
2.214 + }
2.215 + _forward[j] = false;
2.216 + _source[j] = i;
2.217 + _target[j] = _root;
2.218 + _reverse[j] = k;
2.219 + _forward[k] = true;
2.220 + _source[k] = _root;
2.221 + _target[k] = i;
2.222 + _reverse[k] = j;
2.223 + ++j; ++k;
2.224 + }
2.225 + _first_out[i] = j;
2.226 + _first_out[_res_node_num] = k;
2.227 + for (ArcIt a(_graph); a != INVALID; ++a) {
2.228 + int fi = _arc_idf[a];
2.229 + int bi = _arc_idb[a];
2.230 + _reverse[fi] = bi;
2.231 + _reverse[bi] = fi;
2.232 + }
2.233 +
2.234 + // Reset parameters
2.235 + resetParams();
2.236 + return *this;
2.237 + }
2.238 +
2.239 /// @}
2.240
2.241 /// \name Query Functions
3.1 --- a/lemon/cycle_canceling.h Tue Feb 09 23:29:51 2010 +0100
3.2 +++ b/lemon/cycle_canceling.h Wed Feb 10 19:05:20 2010 +0100
3.3 @@ -250,71 +250,7 @@
3.4 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
3.5 "The cost type of CycleCanceling must be signed");
3.6
3.7 - // Resize vectors
3.8 - _node_num = countNodes(_graph);
3.9 - _arc_num = countArcs(_graph);
3.10 - _res_node_num = _node_num + 1;
3.11 - _res_arc_num = 2 * (_arc_num + _node_num);
3.12 - _root = _node_num;
3.13 -
3.14 - _first_out.resize(_res_node_num + 1);
3.15 - _forward.resize(_res_arc_num);
3.16 - _source.resize(_res_arc_num);
3.17 - _target.resize(_res_arc_num);
3.18 - _reverse.resize(_res_arc_num);
3.19 -
3.20 - _lower.resize(_res_arc_num);
3.21 - _upper.resize(_res_arc_num);
3.22 - _cost.resize(_res_arc_num);
3.23 - _supply.resize(_res_node_num);
3.24 -
3.25 - _res_cap.resize(_res_arc_num);
3.26 - _pi.resize(_res_node_num);
3.27 -
3.28 - _arc_vec.reserve(_res_arc_num);
3.29 - _cost_vec.reserve(_res_arc_num);
3.30 - _id_vec.reserve(_res_arc_num);
3.31 -
3.32 - // Copy the graph
3.33 - int i = 0, j = 0, k = 2 * _arc_num + _node_num;
3.34 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
3.35 - _node_id[n] = i;
3.36 - }
3.37 - i = 0;
3.38 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
3.39 - _first_out[i] = j;
3.40 - for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
3.41 - _arc_idf[a] = j;
3.42 - _forward[j] = true;
3.43 - _source[j] = i;
3.44 - _target[j] = _node_id[_graph.runningNode(a)];
3.45 - }
3.46 - for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
3.47 - _arc_idb[a] = j;
3.48 - _forward[j] = false;
3.49 - _source[j] = i;
3.50 - _target[j] = _node_id[_graph.runningNode(a)];
3.51 - }
3.52 - _forward[j] = false;
3.53 - _source[j] = i;
3.54 - _target[j] = _root;
3.55 - _reverse[j] = k;
3.56 - _forward[k] = true;
3.57 - _source[k] = _root;
3.58 - _target[k] = i;
3.59 - _reverse[k] = j;
3.60 - ++j; ++k;
3.61 - }
3.62 - _first_out[i] = j;
3.63 - _first_out[_res_node_num] = k;
3.64 - for (ArcIt a(_graph); a != INVALID; ++a) {
3.65 - int fi = _arc_idf[a];
3.66 - int bi = _arc_idb[a];
3.67 - _reverse[fi] = bi;
3.68 - _reverse[bi] = fi;
3.69 - }
3.70 -
3.71 - // Reset parameters
3.72 + // Reset data structures
3.73 reset();
3.74 }
3.75
3.76 @@ -449,12 +385,12 @@
3.77 /// .supplyMap(sup).run();
3.78 /// \endcode
3.79 ///
3.80 - /// This function can be called more than once. All the parameters
3.81 - /// that have been given are kept for the next call, unless
3.82 - /// \ref reset() is called, thus only the modified parameters
3.83 - /// have to be set again. See \ref reset() for examples.
3.84 - /// However, the underlying digraph must not be modified after this
3.85 - /// class have been constructed, since it copies and extends the graph.
3.86 + /// This function can be called more than once. All the given parameters
3.87 + /// are kept for the next call, unless \ref resetParams() or \ref reset()
3.88 + /// is used, thus only the modified parameters have to be set again.
3.89 + /// If the underlying digraph was also modified after the construction
3.90 + /// of the class (or the last \ref reset() call), then the \ref reset()
3.91 + /// function must be called.
3.92 ///
3.93 /// \param method The cycle-canceling method that will be used.
3.94 /// For more information, see \ref Method.
3.95 @@ -470,6 +406,7 @@
3.96 /// these cases.
3.97 ///
3.98 /// \see ProblemType, Method
3.99 + /// \see resetParams(), reset()
3.100 ProblemType run(Method method = CANCEL_AND_TIGHTEN) {
3.101 ProblemType pt = init();
3.102 if (pt != OPTIMAL) return pt;
3.103 @@ -483,11 +420,12 @@
3.104 /// before using functions \ref lowerMap(), \ref upperMap(),
3.105 /// \ref costMap(), \ref supplyMap(), \ref stSupply().
3.106 ///
3.107 - /// It is useful for multiple run() calls. If this function is not
3.108 - /// used, all the parameters given before are kept for the next
3.109 - /// \ref run() call.
3.110 - /// However, the underlying digraph must not be modified after this
3.111 - /// class have been constructed, since it copies and extends the graph.
3.112 + /// It is useful for multiple \ref run() calls. Basically, all the given
3.113 + /// parameters are kept for the next \ref run() call, unless
3.114 + /// \ref resetParams() or \ref reset() is used.
3.115 + /// If the underlying digraph was also modified after the construction
3.116 + /// of the class or the last \ref reset() call, then the \ref reset()
3.117 + /// function must be used, otherwise \ref resetParams() is sufficient.
3.118 ///
3.119 /// For example,
3.120 /// \code
3.121 @@ -497,20 +435,22 @@
3.122 /// cc.lowerMap(lower).upperMap(upper).costMap(cost)
3.123 /// .supplyMap(sup).run();
3.124 ///
3.125 - /// // Run again with modified cost map (reset() is not called,
3.126 + /// // Run again with modified cost map (resetParams() is not called,
3.127 /// // so only the cost map have to be set again)
3.128 /// cost[e] += 100;
3.129 /// cc.costMap(cost).run();
3.130 ///
3.131 - /// // Run again from scratch using reset()
3.132 + /// // Run again from scratch using resetParams()
3.133 /// // (the lower bounds will be set to zero on all arcs)
3.134 - /// cc.reset();
3.135 + /// cc.resetParams();
3.136 /// cc.upperMap(capacity).costMap(cost)
3.137 /// .supplyMap(sup).run();
3.138 /// \endcode
3.139 ///
3.140 /// \return <tt>(*this)</tt>
3.141 - CycleCanceling& reset() {
3.142 + ///
3.143 + /// \see reset(), run()
3.144 + CycleCanceling& resetParams() {
3.145 for (int i = 0; i != _res_node_num; ++i) {
3.146 _supply[i] = 0;
3.147 }
3.148 @@ -530,6 +470,95 @@
3.149 return *this;
3.150 }
3.151
3.152 + /// \brief Reset the internal data structures and all the parameters
3.153 + /// that have been given before.
3.154 + ///
3.155 + /// This function resets the internal data structures and all the
3.156 + /// paramaters that have been given before using functions \ref lowerMap(),
3.157 + /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
3.158 + ///
3.159 + /// It is useful for multiple \ref run() calls. Basically, all the given
3.160 + /// parameters are kept for the next \ref run() call, unless
3.161 + /// \ref resetParams() or \ref reset() is used.
3.162 + /// If the underlying digraph was also modified after the construction
3.163 + /// of the class or the last \ref reset() call, then the \ref reset()
3.164 + /// function must be used, otherwise \ref resetParams() is sufficient.
3.165 + ///
3.166 + /// See \ref resetParams() for examples.
3.167 + ///
3.168 + /// \return <tt>(*this)</tt>
3.169 + ///
3.170 + /// \see resetParams(), run()
3.171 + CycleCanceling& reset() {
3.172 + // Resize vectors
3.173 + _node_num = countNodes(_graph);
3.174 + _arc_num = countArcs(_graph);
3.175 + _res_node_num = _node_num + 1;
3.176 + _res_arc_num = 2 * (_arc_num + _node_num);
3.177 + _root = _node_num;
3.178 +
3.179 + _first_out.resize(_res_node_num + 1);
3.180 + _forward.resize(_res_arc_num);
3.181 + _source.resize(_res_arc_num);
3.182 + _target.resize(_res_arc_num);
3.183 + _reverse.resize(_res_arc_num);
3.184 +
3.185 + _lower.resize(_res_arc_num);
3.186 + _upper.resize(_res_arc_num);
3.187 + _cost.resize(_res_arc_num);
3.188 + _supply.resize(_res_node_num);
3.189 +
3.190 + _res_cap.resize(_res_arc_num);
3.191 + _pi.resize(_res_node_num);
3.192 +
3.193 + _arc_vec.reserve(_res_arc_num);
3.194 + _cost_vec.reserve(_res_arc_num);
3.195 + _id_vec.reserve(_res_arc_num);
3.196 +
3.197 + // Copy the graph
3.198 + int i = 0, j = 0, k = 2 * _arc_num + _node_num;
3.199 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
3.200 + _node_id[n] = i;
3.201 + }
3.202 + i = 0;
3.203 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
3.204 + _first_out[i] = j;
3.205 + for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
3.206 + _arc_idf[a] = j;
3.207 + _forward[j] = true;
3.208 + _source[j] = i;
3.209 + _target[j] = _node_id[_graph.runningNode(a)];
3.210 + }
3.211 + for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
3.212 + _arc_idb[a] = j;
3.213 + _forward[j] = false;
3.214 + _source[j] = i;
3.215 + _target[j] = _node_id[_graph.runningNode(a)];
3.216 + }
3.217 + _forward[j] = false;
3.218 + _source[j] = i;
3.219 + _target[j] = _root;
3.220 + _reverse[j] = k;
3.221 + _forward[k] = true;
3.222 + _source[k] = _root;
3.223 + _target[k] = i;
3.224 + _reverse[k] = j;
3.225 + ++j; ++k;
3.226 + }
3.227 + _first_out[i] = j;
3.228 + _first_out[_res_node_num] = k;
3.229 + for (ArcIt a(_graph); a != INVALID; ++a) {
3.230 + int fi = _arc_idf[a];
3.231 + int bi = _arc_idb[a];
3.232 + _reverse[fi] = bi;
3.233 + _reverse[bi] = fi;
3.234 + }
3.235 +
3.236 + // Reset parameters
3.237 + resetParams();
3.238 + return *this;
3.239 + }
3.240 +
3.241 /// @}
3.242
3.243 /// \name Query Functions
4.1 --- a/lemon/network_simplex.h Tue Feb 09 23:29:51 2010 +0100
4.2 +++ b/lemon/network_simplex.h Wed Feb 10 19:05:20 2010 +0100
4.3 @@ -194,6 +194,7 @@
4.4 IntArcMap _arc_id;
4.5 IntVector _source;
4.6 IntVector _target;
4.7 + bool _arc_mixing;
4.8
4.9 // Node and arc data
4.10 ValueVector _lower;
4.11 @@ -633,6 +634,7 @@
4.12 /// but it is usually slower. Therefore it is disabled by default.
4.13 NetworkSimplex(const GR& graph, bool arc_mixing = false) :
4.14 _graph(graph), _node_id(graph), _arc_id(graph),
4.15 + _arc_mixing(arc_mixing),
4.16 MAX(std::numeric_limits<Value>::max()),
4.17 INF(std::numeric_limits<Value>::has_infinity ?
4.18 std::numeric_limits<Value>::infinity() : MAX)
4.19 @@ -643,58 +645,7 @@
4.20 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
4.21 "The cost type of NetworkSimplex must be signed");
4.22
4.23 - // Resize vectors
4.24 - _node_num = countNodes(_graph);
4.25 - _arc_num = countArcs(_graph);
4.26 - int all_node_num = _node_num + 1;
4.27 - int max_arc_num = _arc_num + 2 * _node_num;
4.28 -
4.29 - _source.resize(max_arc_num);
4.30 - _target.resize(max_arc_num);
4.31 -
4.32 - _lower.resize(_arc_num);
4.33 - _upper.resize(_arc_num);
4.34 - _cap.resize(max_arc_num);
4.35 - _cost.resize(max_arc_num);
4.36 - _supply.resize(all_node_num);
4.37 - _flow.resize(max_arc_num);
4.38 - _pi.resize(all_node_num);
4.39 -
4.40 - _parent.resize(all_node_num);
4.41 - _pred.resize(all_node_num);
4.42 - _forward.resize(all_node_num);
4.43 - _thread.resize(all_node_num);
4.44 - _rev_thread.resize(all_node_num);
4.45 - _succ_num.resize(all_node_num);
4.46 - _last_succ.resize(all_node_num);
4.47 - _state.resize(max_arc_num);
4.48 -
4.49 - // Copy the graph
4.50 - int i = 0;
4.51 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
4.52 - _node_id[n] = i;
4.53 - }
4.54 - if (arc_mixing) {
4.55 - // Store the arcs in a mixed order
4.56 - int k = std::max(int(std::sqrt(double(_arc_num))), 10);
4.57 - int i = 0, j = 0;
4.58 - for (ArcIt a(_graph); a != INVALID; ++a) {
4.59 - _arc_id[a] = i;
4.60 - _source[i] = _node_id[_graph.source(a)];
4.61 - _target[i] = _node_id[_graph.target(a)];
4.62 - if ((i += k) >= _arc_num) i = ++j;
4.63 - }
4.64 - } else {
4.65 - // Store the arcs in the original order
4.66 - int i = 0;
4.67 - for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
4.68 - _arc_id[a] = i;
4.69 - _source[i] = _node_id[_graph.source(a)];
4.70 - _target[i] = _node_id[_graph.target(a)];
4.71 - }
4.72 - }
4.73 -
4.74 - // Reset parameters
4.75 + // Reset data structures
4.76 reset();
4.77 }
4.78
4.79 @@ -842,12 +793,12 @@
4.80 /// .supplyMap(sup).run();
4.81 /// \endcode
4.82 ///
4.83 - /// This function can be called more than once. All the parameters
4.84 - /// that have been given are kept for the next call, unless
4.85 - /// \ref reset() is called, thus only the modified parameters
4.86 - /// have to be set again. See \ref reset() for examples.
4.87 - /// However, the underlying digraph must not be modified after this
4.88 - /// class have been constructed, since it copies and extends the graph.
4.89 + /// This function can be called more than once. All the given parameters
4.90 + /// are kept for the next call, unless \ref resetParams() or \ref reset()
4.91 + /// is used, thus only the modified parameters have to be set again.
4.92 + /// If the underlying digraph was also modified after the construction
4.93 + /// of the class (or the last \ref reset() call), then the \ref reset()
4.94 + /// function must be called.
4.95 ///
4.96 /// \param pivot_rule The pivot rule that will be used during the
4.97 /// algorithm. For more information, see \ref PivotRule.
4.98 @@ -861,6 +812,7 @@
4.99 /// cost and infinite upper bound.
4.100 ///
4.101 /// \see ProblemType, PivotRule
4.102 + /// \see resetParams(), reset()
4.103 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
4.104 if (!init()) return INFEASIBLE;
4.105 return start(pivot_rule);
4.106 @@ -872,11 +824,12 @@
4.107 /// before using functions \ref lowerMap(), \ref upperMap(),
4.108 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
4.109 ///
4.110 - /// It is useful for multiple run() calls. If this function is not
4.111 - /// used, all the parameters given before are kept for the next
4.112 - /// \ref run() call.
4.113 - /// However, the underlying digraph must not be modified after this
4.114 - /// class have been constructed, since it copies and extends the graph.
4.115 + /// It is useful for multiple \ref run() calls. Basically, all the given
4.116 + /// parameters are kept for the next \ref run() call, unless
4.117 + /// \ref resetParams() or \ref reset() is used.
4.118 + /// If the underlying digraph was also modified after the construction
4.119 + /// of the class or the last \ref reset() call, then the \ref reset()
4.120 + /// function must be used, otherwise \ref resetParams() is sufficient.
4.121 ///
4.122 /// For example,
4.123 /// \code
4.124 @@ -886,20 +839,22 @@
4.125 /// ns.lowerMap(lower).upperMap(upper).costMap(cost)
4.126 /// .supplyMap(sup).run();
4.127 ///
4.128 - /// // Run again with modified cost map (reset() is not called,
4.129 + /// // Run again with modified cost map (resetParams() is not called,
4.130 /// // so only the cost map have to be set again)
4.131 /// cost[e] += 100;
4.132 /// ns.costMap(cost).run();
4.133 ///
4.134 - /// // Run again from scratch using reset()
4.135 + /// // Run again from scratch using resetParams()
4.136 /// // (the lower bounds will be set to zero on all arcs)
4.137 - /// ns.reset();
4.138 + /// ns.resetParams();
4.139 /// ns.upperMap(capacity).costMap(cost)
4.140 /// .supplyMap(sup).run();
4.141 /// \endcode
4.142 ///
4.143 /// \return <tt>(*this)</tt>
4.144 - NetworkSimplex& reset() {
4.145 + ///
4.146 + /// \see reset(), run()
4.147 + NetworkSimplex& resetParams() {
4.148 for (int i = 0; i != _node_num; ++i) {
4.149 _supply[i] = 0;
4.150 }
4.151 @@ -913,6 +868,83 @@
4.152 return *this;
4.153 }
4.154
4.155 + /// \brief Reset the internal data structures and all the parameters
4.156 + /// that have been given before.
4.157 + ///
4.158 + /// This function resets the internal data structures and all the
4.159 + /// paramaters that have been given before using functions \ref lowerMap(),
4.160 + /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
4.161 + /// \ref supplyType().
4.162 + ///
4.163 + /// It is useful for multiple \ref run() calls. Basically, all the given
4.164 + /// parameters are kept for the next \ref run() call, unless
4.165 + /// \ref resetParams() or \ref reset() is used.
4.166 + /// If the underlying digraph was also modified after the construction
4.167 + /// of the class or the last \ref reset() call, then the \ref reset()
4.168 + /// function must be used, otherwise \ref resetParams() is sufficient.
4.169 + ///
4.170 + /// See \ref resetParams() for examples.
4.171 + ///
4.172 + /// \return <tt>(*this)</tt>
4.173 + ///
4.174 + /// \see resetParams(), run()
4.175 + NetworkSimplex& reset() {
4.176 + // Resize vectors
4.177 + _node_num = countNodes(_graph);
4.178 + _arc_num = countArcs(_graph);
4.179 + int all_node_num = _node_num + 1;
4.180 + int max_arc_num = _arc_num + 2 * _node_num;
4.181 +
4.182 + _source.resize(max_arc_num);
4.183 + _target.resize(max_arc_num);
4.184 +
4.185 + _lower.resize(_arc_num);
4.186 + _upper.resize(_arc_num);
4.187 + _cap.resize(max_arc_num);
4.188 + _cost.resize(max_arc_num);
4.189 + _supply.resize(all_node_num);
4.190 + _flow.resize(max_arc_num);
4.191 + _pi.resize(all_node_num);
4.192 +
4.193 + _parent.resize(all_node_num);
4.194 + _pred.resize(all_node_num);
4.195 + _forward.resize(all_node_num);
4.196 + _thread.resize(all_node_num);
4.197 + _rev_thread.resize(all_node_num);
4.198 + _succ_num.resize(all_node_num);
4.199 + _last_succ.resize(all_node_num);
4.200 + _state.resize(max_arc_num);
4.201 +
4.202 + // Copy the graph
4.203 + int i = 0;
4.204 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
4.205 + _node_id[n] = i;
4.206 + }
4.207 + if (_arc_mixing) {
4.208 + // Store the arcs in a mixed order
4.209 + int k = std::max(int(std::sqrt(double(_arc_num))), 10);
4.210 + int i = 0, j = 0;
4.211 + for (ArcIt a(_graph); a != INVALID; ++a) {
4.212 + _arc_id[a] = i;
4.213 + _source[i] = _node_id[_graph.source(a)];
4.214 + _target[i] = _node_id[_graph.target(a)];
4.215 + if ((i += k) >= _arc_num) i = ++j;
4.216 + }
4.217 + } else {
4.218 + // Store the arcs in the original order
4.219 + int i = 0;
4.220 + for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
4.221 + _arc_id[a] = i;
4.222 + _source[i] = _node_id[_graph.source(a)];
4.223 + _target[i] = _node_id[_graph.target(a)];
4.224 + }
4.225 + }
4.226 +
4.227 + // Reset parameters
4.228 + resetParams();
4.229 + return *this;
4.230 + }
4.231 +
4.232 /// @}
4.233
4.234 /// \name Query Functions
5.1 --- a/test/min_cost_flow_test.cc Tue Feb 09 23:29:51 2010 +0100
5.2 +++ b/test/min_cost_flow_test.cc Wed Feb 10 19:05:20 2010 +0100
5.3 @@ -157,7 +157,7 @@
5.4 MCF mcf(me.g);
5.5 const MCF& const_mcf = mcf;
5.6
5.7 - b = mcf.reset()
5.8 + b = mcf.reset().resetParams()
5.9 .lowerMap(me.lower)
5.10 .upperMap(me.upper)
5.11 .costMap(me.cost)
5.12 @@ -346,7 +346,7 @@
5.13 mcf1.stSupply(v, w, 27);
5.14 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2,
5.15 mcf1.OPTIMAL, true, 8010, test_str + "-4");
5.16 - mcf1.reset().supplyMap(s1);
5.17 + mcf1.resetParams().supplyMap(s1);
5.18 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1,
5.19 mcf1.OPTIMAL, true, 74, test_str + "-5");
5.20 mcf1.lowerMap(l2).stSupply(v, w, 27);
5.21 @@ -363,7 +363,7 @@
5.22 mcf1.OPTIMAL, true, 6360, test_str + "-9");
5.23
5.24 // Tests for the GEQ form
5.25 - mcf1.reset().upperMap(u).costMap(c).supplyMap(s5);
5.26 + mcf1.resetParams().upperMap(u).costMap(c).supplyMap(s5);
5.27 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5,
5.28 mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ);
5.29 mcf1.lowerMap(l2);
5.30 @@ -380,7 +380,7 @@
5.31 mcf2.upperMap(neg1_u2);
5.32 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s,
5.33 mcf2.OPTIMAL, true, -40000, test_str + "-14");
5.34 - mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
5.35 + mcf2.resetParams().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);
5.36 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s,
5.37 mcf2.UNBOUNDED, false, 0, test_str + "-15");
5.38