1.1 --- a/lemon/network_simplex.h Tue Feb 09 23:29:51 2010 +0100
1.2 +++ b/lemon/network_simplex.h Wed Feb 10 19:05:20 2010 +0100
1.3 @@ -194,6 +194,7 @@
1.4 IntArcMap _arc_id;
1.5 IntVector _source;
1.6 IntVector _target;
1.7 + bool _arc_mixing;
1.8
1.9 // Node and arc data
1.10 ValueVector _lower;
1.11 @@ -633,6 +634,7 @@
1.12 /// but it is usually slower. Therefore it is disabled by default.
1.13 NetworkSimplex(const GR& graph, bool arc_mixing = false) :
1.14 _graph(graph), _node_id(graph), _arc_id(graph),
1.15 + _arc_mixing(arc_mixing),
1.16 MAX(std::numeric_limits<Value>::max()),
1.17 INF(std::numeric_limits<Value>::has_infinity ?
1.18 std::numeric_limits<Value>::infinity() : MAX)
1.19 @@ -643,58 +645,7 @@
1.20 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
1.21 "The cost type of NetworkSimplex must be signed");
1.22
1.23 - // Resize vectors
1.24 - _node_num = countNodes(_graph);
1.25 - _arc_num = countArcs(_graph);
1.26 - int all_node_num = _node_num + 1;
1.27 - int max_arc_num = _arc_num + 2 * _node_num;
1.28 -
1.29 - _source.resize(max_arc_num);
1.30 - _target.resize(max_arc_num);
1.31 -
1.32 - _lower.resize(_arc_num);
1.33 - _upper.resize(_arc_num);
1.34 - _cap.resize(max_arc_num);
1.35 - _cost.resize(max_arc_num);
1.36 - _supply.resize(all_node_num);
1.37 - _flow.resize(max_arc_num);
1.38 - _pi.resize(all_node_num);
1.39 -
1.40 - _parent.resize(all_node_num);
1.41 - _pred.resize(all_node_num);
1.42 - _forward.resize(all_node_num);
1.43 - _thread.resize(all_node_num);
1.44 - _rev_thread.resize(all_node_num);
1.45 - _succ_num.resize(all_node_num);
1.46 - _last_succ.resize(all_node_num);
1.47 - _state.resize(max_arc_num);
1.48 -
1.49 - // Copy the graph
1.50 - int i = 0;
1.51 - for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.52 - _node_id[n] = i;
1.53 - }
1.54 - if (arc_mixing) {
1.55 - // Store the arcs in a mixed order
1.56 - int k = std::max(int(std::sqrt(double(_arc_num))), 10);
1.57 - int i = 0, j = 0;
1.58 - for (ArcIt a(_graph); a != INVALID; ++a) {
1.59 - _arc_id[a] = i;
1.60 - _source[i] = _node_id[_graph.source(a)];
1.61 - _target[i] = _node_id[_graph.target(a)];
1.62 - if ((i += k) >= _arc_num) i = ++j;
1.63 - }
1.64 - } else {
1.65 - // Store the arcs in the original order
1.66 - int i = 0;
1.67 - for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
1.68 - _arc_id[a] = i;
1.69 - _source[i] = _node_id[_graph.source(a)];
1.70 - _target[i] = _node_id[_graph.target(a)];
1.71 - }
1.72 - }
1.73 -
1.74 - // Reset parameters
1.75 + // Reset data structures
1.76 reset();
1.77 }
1.78
1.79 @@ -842,12 +793,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 pivot_rule The pivot rule that will be used during the
1.97 /// algorithm. For more information, see \ref PivotRule.
1.98 @@ -861,6 +812,7 @@
1.99 /// cost and infinite upper bound.
1.100 ///
1.101 /// \see ProblemType, PivotRule
1.102 + /// \see resetParams(), reset()
1.103 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
1.104 if (!init()) return INFEASIBLE;
1.105 return start(pivot_rule);
1.106 @@ -872,11 +824,12 @@
1.107 /// before using functions \ref lowerMap(), \ref upperMap(),
1.108 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
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 @@ -886,20 +839,22 @@
1.125 /// ns.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 /// ns.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 - /// ns.reset();
1.138 + /// ns.resetParams();
1.139 /// ns.upperMap(capacity).costMap(cost)
1.140 /// .supplyMap(sup).run();
1.141 /// \endcode
1.142 ///
1.143 /// \return <tt>(*this)</tt>
1.144 - NetworkSimplex& reset() {
1.145 + ///
1.146 + /// \see reset(), run()
1.147 + NetworkSimplex& resetParams() {
1.148 for (int i = 0; i != _node_num; ++i) {
1.149 _supply[i] = 0;
1.150 }
1.151 @@ -913,6 +868,83 @@
1.152 return *this;
1.153 }
1.154
1.155 + /// \brief Reset the internal data structures and all the parameters
1.156 + /// that have been given before.
1.157 + ///
1.158 + /// This function resets the internal data structures and all the
1.159 + /// paramaters that have been given before using functions \ref lowerMap(),
1.160 + /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
1.161 + /// \ref supplyType().
1.162 + ///
1.163 + /// It is useful for multiple \ref run() calls. Basically, all the given
1.164 + /// parameters are kept for the next \ref run() call, unless
1.165 + /// \ref resetParams() or \ref reset() is used.
1.166 + /// If the underlying digraph was also modified after the construction
1.167 + /// of the class or the last \ref reset() call, then the \ref reset()
1.168 + /// function must be used, otherwise \ref resetParams() is sufficient.
1.169 + ///
1.170 + /// See \ref resetParams() for examples.
1.171 + ///
1.172 + /// \return <tt>(*this)</tt>
1.173 + ///
1.174 + /// \see resetParams(), run()
1.175 + NetworkSimplex& reset() {
1.176 + // Resize vectors
1.177 + _node_num = countNodes(_graph);
1.178 + _arc_num = countArcs(_graph);
1.179 + int all_node_num = _node_num + 1;
1.180 + int max_arc_num = _arc_num + 2 * _node_num;
1.181 +
1.182 + _source.resize(max_arc_num);
1.183 + _target.resize(max_arc_num);
1.184 +
1.185 + _lower.resize(_arc_num);
1.186 + _upper.resize(_arc_num);
1.187 + _cap.resize(max_arc_num);
1.188 + _cost.resize(max_arc_num);
1.189 + _supply.resize(all_node_num);
1.190 + _flow.resize(max_arc_num);
1.191 + _pi.resize(all_node_num);
1.192 +
1.193 + _parent.resize(all_node_num);
1.194 + _pred.resize(all_node_num);
1.195 + _forward.resize(all_node_num);
1.196 + _thread.resize(all_node_num);
1.197 + _rev_thread.resize(all_node_num);
1.198 + _succ_num.resize(all_node_num);
1.199 + _last_succ.resize(all_node_num);
1.200 + _state.resize(max_arc_num);
1.201 +
1.202 + // Copy the graph
1.203 + int i = 0;
1.204 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.205 + _node_id[n] = i;
1.206 + }
1.207 + if (_arc_mixing) {
1.208 + // Store the arcs in a mixed order
1.209 + int k = std::max(int(std::sqrt(double(_arc_num))), 10);
1.210 + int i = 0, j = 0;
1.211 + for (ArcIt a(_graph); a != INVALID; ++a) {
1.212 + _arc_id[a] = i;
1.213 + _source[i] = _node_id[_graph.source(a)];
1.214 + _target[i] = _node_id[_graph.target(a)];
1.215 + if ((i += k) >= _arc_num) i = ++j;
1.216 + }
1.217 + } else {
1.218 + // Store the arcs in the original order
1.219 + int i = 0;
1.220 + for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
1.221 + _arc_id[a] = i;
1.222 + _source[i] = _node_id[_graph.source(a)];
1.223 + _target[i] = _node_id[_graph.target(a)];
1.224 + }
1.225 + }
1.226 +
1.227 + // Reset parameters
1.228 + resetParams();
1.229 + return *this;
1.230 + }
1.231 +
1.232 /// @}
1.233
1.234 /// \name Query Functions