1.1 --- a/lemon/network_simplex.h Tue Feb 24 09:52:26 2009 +0100
1.2 +++ b/lemon/network_simplex.h Mon Mar 23 23:54:42 2009 +0100
1.3 @@ -28,6 +28,7 @@
1.4 #include <limits>
1.5 #include <algorithm>
1.6
1.7 +#include <lemon/core.h>
1.8 #include <lemon/math.h>
1.9
1.10 namespace lemon {
1.11 @@ -120,7 +121,7 @@
1.12 private:
1.13
1.14 // References for the original data
1.15 - const Digraph &_orig_graph;
1.16 + const Digraph &_graph;
1.17 const LowerMap *_orig_lower;
1.18 const CapacityMap &_orig_cap;
1.19 const CostMap &_orig_cost;
1.20 @@ -130,22 +131,21 @@
1.21 Capacity _orig_flow_value;
1.22
1.23 // Result maps
1.24 - FlowMap *_flow_result;
1.25 - PotentialMap *_potential_result;
1.26 + FlowMap *_flow_map;
1.27 + PotentialMap *_potential_map;
1.28 bool _local_flow;
1.29 bool _local_potential;
1.30
1.31 - // Data structures for storing the graph
1.32 - ArcVector _arc;
1.33 - NodeVector _node;
1.34 - IntNodeMap _node_id;
1.35 - IntVector _source;
1.36 - IntVector _target;
1.37 -
1.38 // The number of nodes and arcs in the original graph
1.39 int _node_num;
1.40 int _arc_num;
1.41
1.42 + // Data structures for storing the graph
1.43 + IntNodeMap _node_id;
1.44 + ArcVector _arc_ref;
1.45 + IntVector _source;
1.46 + IntVector _target;
1.47 +
1.48 // Node and arc maps
1.49 CapacityVector _cap;
1.50 CostVector _cost;
1.51 @@ -153,23 +153,18 @@
1.52 CapacityVector _flow;
1.53 CostVector _pi;
1.54
1.55 - // Node and arc maps for the spanning tree structure
1.56 + // Data for storing the spanning tree structure
1.57 IntVector _depth;
1.58 IntVector _parent;
1.59 IntVector _pred;
1.60 IntVector _thread;
1.61 BoolVector _forward;
1.62 IntVector _state;
1.63 -
1.64 - // The root node
1.65 int _root;
1.66
1.67 - // The entering arc in the current pivot iteration
1.68 - int _in_arc;
1.69 -
1.70 // Temporary data used in the current pivot iteration
1.71 - int join, u_in, v_in, u_out, v_out;
1.72 - int right, first, second, last;
1.73 + int in_arc, join, u_in, v_in, u_out, v_out;
1.74 + int first, second, right, last;
1.75 int stem, par_stem, new_stem;
1.76 Capacity delta;
1.77
1.78 @@ -187,7 +182,6 @@
1.79 private:
1.80
1.81 // References to the NetworkSimplex class
1.82 - const ArcVector &_arc;
1.83 const IntVector &_source;
1.84 const IntVector &_target;
1.85 const CostVector &_cost;
1.86 @@ -203,9 +197,9 @@
1.87
1.88 /// Constructor
1.89 FirstEligiblePivotRule(NetworkSimplex &ns) :
1.90 - _arc(ns._arc), _source(ns._source), _target(ns._target),
1.91 + _source(ns._source), _target(ns._target),
1.92 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
1.93 - _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
1.94 + _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
1.95 {}
1.96
1.97 /// Find next entering arc
1.98 @@ -245,7 +239,6 @@
1.99 private:
1.100
1.101 // References to the NetworkSimplex class
1.102 - const ArcVector &_arc;
1.103 const IntVector &_source;
1.104 const IntVector &_target;
1.105 const CostVector &_cost;
1.106 @@ -258,9 +251,9 @@
1.107
1.108 /// Constructor
1.109 BestEligiblePivotRule(NetworkSimplex &ns) :
1.110 - _arc(ns._arc), _source(ns._source), _target(ns._target),
1.111 + _source(ns._source), _target(ns._target),
1.112 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
1.113 - _in_arc(ns._in_arc), _arc_num(ns._arc_num)
1.114 + _in_arc(ns.in_arc), _arc_num(ns._arc_num)
1.115 {}
1.116
1.117 /// Find next entering arc
1.118 @@ -291,7 +284,6 @@
1.119 private:
1.120
1.121 // References to the NetworkSimplex class
1.122 - const ArcVector &_arc;
1.123 const IntVector &_source;
1.124 const IntVector &_target;
1.125 const CostVector &_cost;
1.126 @@ -308,9 +300,9 @@
1.127
1.128 /// Constructor
1.129 BlockSearchPivotRule(NetworkSimplex &ns) :
1.130 - _arc(ns._arc), _source(ns._source), _target(ns._target),
1.131 + _source(ns._source), _target(ns._target),
1.132 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
1.133 - _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
1.134 + _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
1.135 {
1.136 // The main parameters of the pivot rule
1.137 const double BLOCK_SIZE_FACTOR = 2.0;
1.138 @@ -370,7 +362,6 @@
1.139 private:
1.140
1.141 // References to the NetworkSimplex class
1.142 - const ArcVector &_arc;
1.143 const IntVector &_source;
1.144 const IntVector &_target;
1.145 const CostVector &_cost;
1.146 @@ -389,9 +380,9 @@
1.147
1.148 /// Constructor
1.149 CandidateListPivotRule(NetworkSimplex &ns) :
1.150 - _arc(ns._arc), _source(ns._source), _target(ns._target),
1.151 + _source(ns._source), _target(ns._target),
1.152 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
1.153 - _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
1.154 + _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
1.155 {
1.156 // The main parameters of the pivot rule
1.157 const double LIST_LENGTH_FACTOR = 1.0;
1.158 @@ -482,7 +473,6 @@
1.159 private:
1.160
1.161 // References to the NetworkSimplex class
1.162 - const ArcVector &_arc;
1.163 const IntVector &_source;
1.164 const IntVector &_target;
1.165 const CostVector &_cost;
1.166 @@ -515,9 +505,9 @@
1.167
1.168 /// Constructor
1.169 AlteringListPivotRule(NetworkSimplex &ns) :
1.170 - _arc(ns._arc), _source(ns._source), _target(ns._target),
1.171 + _source(ns._source), _target(ns._target),
1.172 _cost(ns._cost), _state(ns._state), _pi(ns._pi),
1.173 - _in_arc(ns._in_arc), _arc_num(ns._arc_num),
1.174 + _in_arc(ns.in_arc), _arc_num(ns._arc_num),
1.175 _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
1.176 {
1.177 // The main parameters of the pivot rule
1.178 @@ -549,7 +539,7 @@
1.179
1.180 // Extend the list
1.181 int cnt = _block_size;
1.182 - int last_edge = 0;
1.183 + int last_arc = 0;
1.184 int limit = _head_length;
1.185
1.186 for (int e = _next_arc; e < _arc_num; ++e) {
1.187 @@ -557,7 +547,7 @@
1.188 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
1.189 if (_cand_cost[e] < 0) {
1.190 _candidates[_curr_length++] = e;
1.191 - last_edge = e;
1.192 + last_arc = e;
1.193 }
1.194 if (--cnt == 0) {
1.195 if (_curr_length > limit) break;
1.196 @@ -571,7 +561,7 @@
1.197 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
1.198 if (_cand_cost[e] < 0) {
1.199 _candidates[_curr_length++] = e;
1.200 - last_edge = e;
1.201 + last_arc = e;
1.202 }
1.203 if (--cnt == 0) {
1.204 if (_curr_length > limit) break;
1.205 @@ -581,7 +571,7 @@
1.206 }
1.207 }
1.208 if (_curr_length == 0) return false;
1.209 - _next_arc = last_edge + 1;
1.210 + _next_arc = last_arc + 1;
1.211
1.212 // Make heap of the candidate list (approximating a partial sort)
1.213 make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
1.214 @@ -603,47 +593,47 @@
1.215 ///
1.216 /// General constructor (with lower bounds).
1.217 ///
1.218 - /// \param digraph The digraph the algorithm runs on.
1.219 + /// \param graph The digraph the algorithm runs on.
1.220 /// \param lower The lower bounds of the arcs.
1.221 /// \param capacity The capacities (upper bounds) of the arcs.
1.222 /// \param cost The cost (length) values of the arcs.
1.223 /// \param supply The supply values of the nodes (signed).
1.224 - NetworkSimplex( const Digraph &digraph,
1.225 + NetworkSimplex( const Digraph &graph,
1.226 const LowerMap &lower,
1.227 const CapacityMap &capacity,
1.228 const CostMap &cost,
1.229 const SupplyMap &supply ) :
1.230 - _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
1.231 + _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
1.232 _orig_cost(cost), _orig_supply(&supply),
1.233 - _flow_result(NULL), _potential_result(NULL),
1.234 + _flow_map(NULL), _potential_map(NULL),
1.235 _local_flow(false), _local_potential(false),
1.236 - _node_id(digraph)
1.237 + _node_id(graph)
1.238 {}
1.239
1.240 /// \brief General constructor (without lower bounds).
1.241 ///
1.242 /// General constructor (without lower bounds).
1.243 ///
1.244 - /// \param digraph The digraph the algorithm runs on.
1.245 + /// \param graph The digraph the algorithm runs on.
1.246 /// \param capacity The capacities (upper bounds) of the arcs.
1.247 /// \param cost The cost (length) values of the arcs.
1.248 /// \param supply The supply values of the nodes (signed).
1.249 - NetworkSimplex( const Digraph &digraph,
1.250 + NetworkSimplex( const Digraph &graph,
1.251 const CapacityMap &capacity,
1.252 const CostMap &cost,
1.253 const SupplyMap &supply ) :
1.254 - _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
1.255 + _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
1.256 _orig_cost(cost), _orig_supply(&supply),
1.257 - _flow_result(NULL), _potential_result(NULL),
1.258 + _flow_map(NULL), _potential_map(NULL),
1.259 _local_flow(false), _local_potential(false),
1.260 - _node_id(digraph)
1.261 + _node_id(graph)
1.262 {}
1.263
1.264 /// \brief Simple constructor (with lower bounds).
1.265 ///
1.266 /// Simple constructor (with lower bounds).
1.267 ///
1.268 - /// \param digraph The digraph the algorithm runs on.
1.269 + /// \param graph The digraph the algorithm runs on.
1.270 /// \param lower The lower bounds of the arcs.
1.271 /// \param capacity The capacities (upper bounds) of the arcs.
1.272 /// \param cost The cost (length) values of the arcs.
1.273 @@ -651,48 +641,48 @@
1.274 /// \param t The target node.
1.275 /// \param flow_value The required amount of flow from node \c s
1.276 /// to node \c t (i.e. the supply of \c s and the demand of \c t).
1.277 - NetworkSimplex( const Digraph &digraph,
1.278 + NetworkSimplex( const Digraph &graph,
1.279 const LowerMap &lower,
1.280 const CapacityMap &capacity,
1.281 const CostMap &cost,
1.282 Node s, Node t,
1.283 Capacity flow_value ) :
1.284 - _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
1.285 + _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
1.286 _orig_cost(cost), _orig_supply(NULL),
1.287 _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
1.288 - _flow_result(NULL), _potential_result(NULL),
1.289 + _flow_map(NULL), _potential_map(NULL),
1.290 _local_flow(false), _local_potential(false),
1.291 - _node_id(digraph)
1.292 + _node_id(graph)
1.293 {}
1.294
1.295 /// \brief Simple constructor (without lower bounds).
1.296 ///
1.297 /// Simple constructor (without lower bounds).
1.298 ///
1.299 - /// \param digraph The digraph the algorithm runs on.
1.300 + /// \param graph The digraph the algorithm runs on.
1.301 /// \param capacity The capacities (upper bounds) of the arcs.
1.302 /// \param cost The cost (length) values of the arcs.
1.303 /// \param s The source node.
1.304 /// \param t The target node.
1.305 /// \param flow_value The required amount of flow from node \c s
1.306 /// to node \c t (i.e. the supply of \c s and the demand of \c t).
1.307 - NetworkSimplex( const Digraph &digraph,
1.308 + NetworkSimplex( const Digraph &graph,
1.309 const CapacityMap &capacity,
1.310 const CostMap &cost,
1.311 Node s, Node t,
1.312 Capacity flow_value ) :
1.313 - _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
1.314 + _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
1.315 _orig_cost(cost), _orig_supply(NULL),
1.316 _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
1.317 - _flow_result(NULL), _potential_result(NULL),
1.318 + _flow_map(NULL), _potential_map(NULL),
1.319 _local_flow(false), _local_potential(false),
1.320 - _node_id(digraph)
1.321 + _node_id(graph)
1.322 {}
1.323
1.324 /// Destructor.
1.325 ~NetworkSimplex() {
1.326 - if (_local_flow) delete _flow_result;
1.327 - if (_local_potential) delete _potential_result;
1.328 + if (_local_flow) delete _flow_map;
1.329 + if (_local_potential) delete _potential_map;
1.330 }
1.331
1.332 /// \brief Set the flow map.
1.333 @@ -702,10 +692,10 @@
1.334 /// \return <tt>(*this)</tt>
1.335 NetworkSimplex& flowMap(FlowMap &map) {
1.336 if (_local_flow) {
1.337 - delete _flow_result;
1.338 + delete _flow_map;
1.339 _local_flow = false;
1.340 }
1.341 - _flow_result = ↦
1.342 + _flow_map = ↦
1.343 return *this;
1.344 }
1.345
1.346 @@ -716,10 +706,10 @@
1.347 /// \return <tt>(*this)</tt>
1.348 NetworkSimplex& potentialMap(PotentialMap &map) {
1.349 if (_local_potential) {
1.350 - delete _potential_result;
1.351 + delete _potential_map;
1.352 _local_potential = false;
1.353 }
1.354 - _potential_result = ↦
1.355 + _potential_map = ↦
1.356 return *this;
1.357 }
1.358
1.359 @@ -783,7 +773,7 @@
1.360 ///
1.361 /// \pre \ref run() must be called before using this function.
1.362 const FlowMap& flowMap() const {
1.363 - return *_flow_result;
1.364 + return *_flow_map;
1.365 }
1.366
1.367 /// \brief Return a const reference to the potential map
1.368 @@ -794,7 +784,7 @@
1.369 ///
1.370 /// \pre \ref run() must be called before using this function.
1.371 const PotentialMap& potentialMap() const {
1.372 - return *_potential_result;
1.373 + return *_potential_map;
1.374 }
1.375
1.376 /// \brief Return the flow on the given arc.
1.377 @@ -803,7 +793,7 @@
1.378 ///
1.379 /// \pre \ref run() must be called before using this function.
1.380 Capacity flow(const Arc& arc) const {
1.381 - return (*_flow_result)[arc];
1.382 + return (*_flow_map)[arc];
1.383 }
1.384
1.385 /// \brief Return the potential of the given node.
1.386 @@ -812,7 +802,7 @@
1.387 ///
1.388 /// \pre \ref run() must be called before using this function.
1.389 Cost potential(const Node& node) const {
1.390 - return (*_potential_result)[node];
1.391 + return (*_potential_map)[node];
1.392 }
1.393
1.394 /// \brief Return the total cost of the found flow.
1.395 @@ -823,8 +813,8 @@
1.396 /// \pre \ref run() must be called before using this function.
1.397 Cost totalCost() const {
1.398 Cost c = 0;
1.399 - for (ArcIt e(_orig_graph); e != INVALID; ++e)
1.400 - c += (*_flow_result)[e] * _orig_cost[e];
1.401 + for (ArcIt e(_graph); e != INVALID; ++e)
1.402 + c += (*_flow_map)[e] * _orig_cost[e];
1.403 return c;
1.404 }
1.405
1.406 @@ -835,46 +825,44 @@
1.407 // Initialize internal data structures
1.408 bool init() {
1.409 // Initialize result maps
1.410 - if (!_flow_result) {
1.411 - _flow_result = new FlowMap(_orig_graph);
1.412 + if (!_flow_map) {
1.413 + _flow_map = new FlowMap(_graph);
1.414 _local_flow = true;
1.415 }
1.416 - if (!_potential_result) {
1.417 - _potential_result = new PotentialMap(_orig_graph);
1.418 + if (!_potential_map) {
1.419 + _potential_map = new PotentialMap(_graph);
1.420 _local_potential = true;
1.421 }
1.422
1.423 // Initialize vectors
1.424 - _node_num = countNodes(_orig_graph);
1.425 - _arc_num = countArcs(_orig_graph);
1.426 + _node_num = countNodes(_graph);
1.427 + _arc_num = countArcs(_graph);
1.428 int all_node_num = _node_num + 1;
1.429 - int all_edge_num = _arc_num + _node_num;
1.430 + int all_arc_num = _arc_num + _node_num;
1.431
1.432 - _arc.resize(_arc_num);
1.433 - _node.reserve(_node_num);
1.434 - _source.resize(all_edge_num);
1.435 - _target.resize(all_edge_num);
1.436 + _arc_ref.resize(_arc_num);
1.437 + _source.resize(all_arc_num);
1.438 + _target.resize(all_arc_num);
1.439
1.440 - _cap.resize(all_edge_num);
1.441 - _cost.resize(all_edge_num);
1.442 + _cap.resize(all_arc_num);
1.443 + _cost.resize(all_arc_num);
1.444 _supply.resize(all_node_num);
1.445 - _flow.resize(all_edge_num, 0);
1.446 + _flow.resize(all_arc_num, 0);
1.447 _pi.resize(all_node_num, 0);
1.448
1.449 _depth.resize(all_node_num);
1.450 _parent.resize(all_node_num);
1.451 _pred.resize(all_node_num);
1.452 + _forward.resize(all_node_num);
1.453 _thread.resize(all_node_num);
1.454 - _forward.resize(all_node_num);
1.455 - _state.resize(all_edge_num, STATE_LOWER);
1.456 + _state.resize(all_arc_num, STATE_LOWER);
1.457
1.458 // Initialize node related data
1.459 bool valid_supply = true;
1.460 if (_orig_supply) {
1.461 Supply sum = 0;
1.462 int i = 0;
1.463 - for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
1.464 - _node.push_back(n);
1.465 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.466 _node_id[n] = i;
1.467 _supply[i] = (*_orig_supply)[n];
1.468 sum += _supply[i];
1.469 @@ -882,8 +870,7 @@
1.470 valid_supply = (sum == 0);
1.471 } else {
1.472 int i = 0;
1.473 - for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
1.474 - _node.push_back(n);
1.475 + for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
1.476 _node_id[n] = i;
1.477 _supply[i] = 0;
1.478 }
1.479 @@ -904,16 +891,16 @@
1.480 // Store the arcs in a mixed order
1.481 int k = std::max(int(sqrt(_arc_num)), 10);
1.482 int i = 0;
1.483 - for (ArcIt e(_orig_graph); e != INVALID; ++e) {
1.484 - _arc[i] = e;
1.485 + for (ArcIt e(_graph); e != INVALID; ++e) {
1.486 + _arc_ref[i] = e;
1.487 if ((i += k) >= _arc_num) i = (i % k) + 1;
1.488 }
1.489
1.490 // Initialize arc maps
1.491 for (int i = 0; i != _arc_num; ++i) {
1.492 - Arc e = _arc[i];
1.493 - _source[i] = _node_id[_orig_graph.source(e)];
1.494 - _target[i] = _node_id[_orig_graph.target(e)];
1.495 + Arc e = _arc_ref[i];
1.496 + _source[i] = _node_id[_graph.source(e)];
1.497 + _target[i] = _node_id[_graph.target(e)];
1.498 _cost[i] = _orig_cost[e];
1.499 _cap[i] = _orig_cap[e];
1.500 }
1.501 @@ -921,7 +908,7 @@
1.502 // Remove non-zero lower bounds
1.503 if (_orig_lower) {
1.504 for (int i = 0; i != _arc_num; ++i) {
1.505 - Capacity c = (*_orig_lower)[_arc[i]];
1.506 + Capacity c = (*_orig_lower)[_arc_ref[i]];
1.507 if (c != 0) {
1.508 _cap[i] -= c;
1.509 _supply[_source[i]] -= c;
1.510 @@ -957,8 +944,8 @@
1.511
1.512 // Find the join node
1.513 void findJoinNode() {
1.514 - int u = _source[_in_arc];
1.515 - int v = _target[_in_arc];
1.516 + int u = _source[in_arc];
1.517 + int v = _target[in_arc];
1.518 while (_depth[u] > _depth[v]) u = _parent[u];
1.519 while (_depth[v] > _depth[u]) v = _parent[v];
1.520 while (u != v) {
1.521 @@ -973,14 +960,14 @@
1.522 bool findLeavingArc() {
1.523 // Initialize first and second nodes according to the direction
1.524 // of the cycle
1.525 - if (_state[_in_arc] == STATE_LOWER) {
1.526 - first = _source[_in_arc];
1.527 - second = _target[_in_arc];
1.528 + if (_state[in_arc] == STATE_LOWER) {
1.529 + first = _source[in_arc];
1.530 + second = _target[in_arc];
1.531 } else {
1.532 - first = _target[_in_arc];
1.533 - second = _source[_in_arc];
1.534 + first = _target[in_arc];
1.535 + second = _source[in_arc];
1.536 }
1.537 - delta = _cap[_in_arc];
1.538 + delta = _cap[in_arc];
1.539 int result = 0;
1.540 Capacity d;
1.541 int e;
1.542 @@ -1020,22 +1007,22 @@
1.543 void changeFlow(bool change) {
1.544 // Augment along the cycle
1.545 if (delta > 0) {
1.546 - Capacity val = _state[_in_arc] * delta;
1.547 - _flow[_in_arc] += val;
1.548 - for (int u = _source[_in_arc]; u != join; u = _parent[u]) {
1.549 + Capacity val = _state[in_arc] * delta;
1.550 + _flow[in_arc] += val;
1.551 + for (int u = _source[in_arc]; u != join; u = _parent[u]) {
1.552 _flow[_pred[u]] += _forward[u] ? -val : val;
1.553 }
1.554 - for (int u = _target[_in_arc]; u != join; u = _parent[u]) {
1.555 + for (int u = _target[in_arc]; u != join; u = _parent[u]) {
1.556 _flow[_pred[u]] += _forward[u] ? val : -val;
1.557 }
1.558 }
1.559 // Update the state of the entering and leaving arcs
1.560 if (change) {
1.561 - _state[_in_arc] = STATE_TREE;
1.562 + _state[in_arc] = STATE_TREE;
1.563 _state[_pred[u_out]] =
1.564 (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER;
1.565 } else {
1.566 - _state[_in_arc] = -_state[_in_arc];
1.567 + _state[in_arc] = -_state[in_arc];
1.568 }
1.569 }
1.570
1.571 @@ -1106,8 +1093,8 @@
1.572 _forward[u] = !_forward[v];
1.573 u = v;
1.574 }
1.575 - _pred[u_in] = _in_arc;
1.576 - _forward[u_in] = (u_in == _source[_in_arc]);
1.577 + _pred[u_in] = in_arc;
1.578 + _forward[u_in] = (u_in == _source[in_arc]);
1.579 }
1.580
1.581 // Update _depth and _potential vectors
1.582 @@ -1163,20 +1150,20 @@
1.583 if (_flow[e] > 0) return false;
1.584 }
1.585
1.586 - // Copy flow values to _flow_result
1.587 + // Copy flow values to _flow_map
1.588 if (_orig_lower) {
1.589 for (int i = 0; i != _arc_num; ++i) {
1.590 - Arc e = _arc[i];
1.591 - (*_flow_result)[e] = (*_orig_lower)[e] + _flow[i];
1.592 + Arc e = _arc_ref[i];
1.593 + _flow_map->set(e, (*_orig_lower)[e] + _flow[i]);
1.594 }
1.595 } else {
1.596 for (int i = 0; i != _arc_num; ++i) {
1.597 - (*_flow_result)[_arc[i]] = _flow[i];
1.598 + _flow_map->set(_arc_ref[i], _flow[i]);
1.599 }
1.600 }
1.601 - // Copy potential values to _potential_result
1.602 - for (int i = 0; i != _node_num; ++i) {
1.603 - (*_potential_result)[_node[i]] = _pi[i];
1.604 + // Copy potential values to _potential_map
1.605 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.606 + _potential_map->set(n, _pi[_node_id[n]]);
1.607 }
1.608
1.609 return true;