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