author Peter Kovacs Mon, 23 Mar 2009 23:54:42 +0100 changeset 650 425cc8328c0e parent 649 a79ef774fae1 child 651 8c3112a66878
Internal restructuring and renamings in NetworkSimplex (#234)
 lemon/network_simplex.h file | annotate | diff | comparison | revisions
     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.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.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 = &map;
1.342 +      _flow_map = &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 = &map;
1.355 +      _potential_map = &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.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;