Internal restructuring and renamings in NetworkSimplex (#234)
authorPeter Kovacs <kpeter@inf.elte.hu>
Mon, 23 Mar 2009 23:54:42 +0100
changeset 603425cc8328c0e
parent 602 a79ef774fae1
child 604 8c3112a66878
Internal restructuring and renamings in NetworkSimplex (#234)
lemon/network_simplex.h
     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 = &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.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;