Index: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h	(revision 593)
+++ lemon/network_simplex.h	(revision 595)
@@ -29,4 +29,5 @@
 #include <algorithm>
 
+#include <lemon/core.h>
 #include <lemon/math.h>
 
@@ -121,5 +122,5 @@
 
     // References for the original data
-    const Digraph &_orig_graph;
+    const Digraph &_graph;
     const LowerMap *_orig_lower;
     const CapacityMap &_orig_cap;
@@ -131,19 +132,18 @@
 
     // Result maps
-    FlowMap *_flow_result;
-    PotentialMap *_potential_result;
+    FlowMap *_flow_map;
+    PotentialMap *_potential_map;
     bool _local_flow;
     bool _local_potential;
-
-    // Data structures for storing the graph
-    ArcVector _arc;
-    NodeVector _node;
-    IntNodeMap _node_id;
-    IntVector _source;
-    IntVector _target;
 
     // The number of nodes and arcs in the original graph
     int _node_num;
     int _arc_num;
+
+    // Data structures for storing the graph
+    IntNodeMap _node_id;
+    ArcVector _arc_ref;
+    IntVector _source;
+    IntVector _target;
 
     // Node and arc maps
@@ -154,5 +154,5 @@
     CostVector _pi;
 
-    // Node and arc maps for the spanning tree structure
+    // Data for storing the spanning tree structure
     IntVector _depth;
     IntVector _parent;
@@ -161,14 +161,9 @@
     BoolVector _forward;
     IntVector _state;
-
-    // The root node
     int _root;
 
-    // The entering arc in the current pivot iteration
-    int _in_arc;
-
     // Temporary data used in the current pivot iteration
-    int join, u_in, v_in, u_out, v_out;
-    int right, first, second, last;
+    int in_arc, join, u_in, v_in, u_out, v_out;
+    int first, second, right, last;
     int stem, par_stem, new_stem;
     Capacity delta;
@@ -188,5 +183,4 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -204,7 +198,7 @@
       /// Constructor
       FirstEligiblePivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
       {}
 
@@ -246,5 +240,4 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -259,7 +252,7 @@
       /// Constructor
       BestEligiblePivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num)
       {}
 
@@ -292,5 +285,4 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -309,7 +301,7 @@
       /// Constructor
       BlockSearchPivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
       {
         // The main parameters of the pivot rule
@@ -371,5 +363,4 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -390,7 +381,7 @@
       /// Constructor
       CandidateListPivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
       {
         // The main parameters of the pivot rule
@@ -483,5 +474,4 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -516,7 +506,7 @@
       /// Constructor
       AlteringListPivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num),
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num),
         _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
       {
@@ -550,5 +540,5 @@
         // Extend the list
         int cnt = _block_size;
-        int last_edge = 0;
+        int last_arc = 0;
         int limit = _head_length;
 
@@ -558,5 +548,5 @@
           if (_cand_cost[e] < 0) {
             _candidates[_curr_length++] = e;
-            last_edge = e;
+            last_arc = e;
           }
           if (--cnt == 0) {
@@ -572,5 +562,5 @@
             if (_cand_cost[e] < 0) {
               _candidates[_curr_length++] = e;
-              last_edge = e;
+              last_arc = e;
             }
             if (--cnt == 0) {
@@ -582,5 +572,5 @@
         }
         if (_curr_length == 0) return false;
-        _next_arc = last_edge + 1;
+        _next_arc = last_arc + 1;
 
         // Make heap of the candidate list (approximating a partial sort)
@@ -604,19 +594,19 @@
     /// General constructor (with lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param lower The lower bounds of the arcs.
     /// \param capacity The capacities (upper bounds) of the arcs.
     /// \param cost The cost (length) values of the arcs.
     /// \param supply The supply values of the nodes (signed).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const LowerMap &lower,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     const SupplyMap &supply ) :
-      _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
+      _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(&supply),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
@@ -625,17 +615,17 @@
     /// General constructor (without lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param capacity The capacities (upper bounds) of the arcs.
     /// \param cost The cost (length) values of the arcs.
     /// \param supply The supply values of the nodes (signed).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     const SupplyMap &supply ) :
-      _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
+      _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(&supply),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
@@ -644,5 +634,5 @@
     /// Simple constructor (with lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param lower The lower bounds of the arcs.
     /// \param capacity The capacities (upper bounds) of the arcs.
@@ -652,5 +642,5 @@
     /// \param flow_value The required amount of flow from node \c s
     /// to node \c t (i.e. the supply of \c s and the demand of \c t).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const LowerMap &lower,
                     const CapacityMap &capacity,
@@ -658,10 +648,10 @@
                     Node s, Node t,
                     Capacity flow_value ) :
-      _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
+      _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(NULL),
       _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
@@ -670,5 +660,5 @@
     /// Simple constructor (without lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param capacity The capacities (upper bounds) of the arcs.
     /// \param cost The cost (length) values of the arcs.
@@ -677,21 +667,21 @@
     /// \param flow_value The required amount of flow from node \c s
     /// to node \c t (i.e. the supply of \c s and the demand of \c t).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     Node s, Node t,
                     Capacity flow_value ) :
-      _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
+      _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(NULL),
       _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
     /// Destructor.
     ~NetworkSimplex() {
-      if (_local_flow) delete _flow_result;
-      if (_local_potential) delete _potential_result;
+      if (_local_flow) delete _flow_map;
+      if (_local_potential) delete _potential_map;
     }
 
@@ -703,8 +693,8 @@
     NetworkSimplex& flowMap(FlowMap &map) {
       if (_local_flow) {
-        delete _flow_result;
+        delete _flow_map;
         _local_flow = false;
       }
-      _flow_result = &map;
+      _flow_map = &map;
       return *this;
     }
@@ -717,8 +707,8 @@
     NetworkSimplex& potentialMap(PotentialMap &map) {
       if (_local_potential) {
-        delete _potential_result;
+        delete _potential_map;
         _local_potential = false;
       }
-      _potential_result = &map;
+      _potential_map = &map;
       return *this;
     }
@@ -784,5 +774,5 @@
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return *_flow_result;
+      return *_flow_map;
     }
 
@@ -795,5 +785,5 @@
     /// \pre \ref run() must be called before using this function.
     const PotentialMap& potentialMap() const {
-      return *_potential_result;
+      return *_potential_map;
     }
 
@@ -804,5 +794,5 @@
     /// \pre \ref run() must be called before using this function.
     Capacity flow(const Arc& arc) const {
-      return (*_flow_result)[arc];
+      return (*_flow_map)[arc];
     }
 
@@ -813,5 +803,5 @@
     /// \pre \ref run() must be called before using this function.
     Cost potential(const Node& node) const {
-      return (*_potential_result)[node];
+      return (*_potential_map)[node];
     }
 
@@ -824,6 +814,6 @@
     Cost totalCost() const {
       Cost c = 0;
-      for (ArcIt e(_orig_graph); e != INVALID; ++e)
-        c += (*_flow_result)[e] * _orig_cost[e];
+      for (ArcIt e(_graph); e != INVALID; ++e)
+        c += (*_flow_map)[e] * _orig_cost[e];
       return c;
     }
@@ -836,28 +826,27 @@
     bool init() {
       // Initialize result maps
-      if (!_flow_result) {
-        _flow_result = new FlowMap(_orig_graph);
+      if (!_flow_map) {
+        _flow_map = new FlowMap(_graph);
         _local_flow = true;
       }
-      if (!_potential_result) {
-        _potential_result = new PotentialMap(_orig_graph);
+      if (!_potential_map) {
+        _potential_map = new PotentialMap(_graph);
         _local_potential = true;
       }
 
       // Initialize vectors
-      _node_num = countNodes(_orig_graph);
-      _arc_num = countArcs(_orig_graph);
+      _node_num = countNodes(_graph);
+      _arc_num = countArcs(_graph);
       int all_node_num = _node_num + 1;
-      int all_edge_num = _arc_num + _node_num;
-
-      _arc.resize(_arc_num);
-      _node.reserve(_node_num);
-      _source.resize(all_edge_num);
-      _target.resize(all_edge_num);
-
-      _cap.resize(all_edge_num);
-      _cost.resize(all_edge_num);
+      int all_arc_num = _arc_num + _node_num;
+
+      _arc_ref.resize(_arc_num);
+      _source.resize(all_arc_num);
+      _target.resize(all_arc_num);
+
+      _cap.resize(all_arc_num);
+      _cost.resize(all_arc_num);
       _supply.resize(all_node_num);
-      _flow.resize(all_edge_num, 0);
+      _flow.resize(all_arc_num, 0);
       _pi.resize(all_node_num, 0);
 
@@ -865,7 +854,7 @@
       _parent.resize(all_node_num);
       _pred.resize(all_node_num);
+      _forward.resize(all_node_num);
       _thread.resize(all_node_num);
-      _forward.resize(all_node_num);
-      _state.resize(all_edge_num, STATE_LOWER);
+      _state.resize(all_arc_num, STATE_LOWER);
 
       // Initialize node related data
@@ -874,6 +863,5 @@
         Supply sum = 0;
         int i = 0;
-        for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
-          _node.push_back(n);
+        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
           _node_id[n] = i;
           _supply[i] = (*_orig_supply)[n];
@@ -883,6 +871,5 @@
       } else {
         int i = 0;
-        for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
-          _node.push_back(n);
+        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
           _node_id[n] = i;
           _supply[i] = 0;
@@ -905,6 +892,6 @@
       int k = std::max(int(sqrt(_arc_num)), 10);
       int i = 0;
-      for (ArcIt e(_orig_graph); e != INVALID; ++e) {
-        _arc[i] = e;
+      for (ArcIt e(_graph); e != INVALID; ++e) {
+        _arc_ref[i] = e;
         if ((i += k) >= _arc_num) i = (i % k) + 1;
       }
@@ -912,7 +899,7 @@
       // Initialize arc maps
       for (int i = 0; i != _arc_num; ++i) {
-        Arc e = _arc[i];
-        _source[i] = _node_id[_orig_graph.source(e)];
-        _target[i] = _node_id[_orig_graph.target(e)];
+        Arc e = _arc_ref[i];
+        _source[i] = _node_id[_graph.source(e)];
+        _target[i] = _node_id[_graph.target(e)];
         _cost[i] = _orig_cost[e];
         _cap[i] = _orig_cap[e];
@@ -922,5 +909,5 @@
       if (_orig_lower) {
         for (int i = 0; i != _arc_num; ++i) {
-          Capacity c = (*_orig_lower)[_arc[i]];
+          Capacity c = (*_orig_lower)[_arc_ref[i]];
           if (c != 0) {
             _cap[i] -= c;
@@ -958,6 +945,6 @@
     // Find the join node
     void findJoinNode() {
-      int u = _source[_in_arc];
-      int v = _target[_in_arc];
+      int u = _source[in_arc];
+      int v = _target[in_arc];
       while (_depth[u] > _depth[v]) u = _parent[u];
       while (_depth[v] > _depth[u]) v = _parent[v];
@@ -974,12 +961,12 @@
       // Initialize first and second nodes according to the direction
       // of the cycle
-      if (_state[_in_arc] == STATE_LOWER) {
-        first  = _source[_in_arc];
-        second = _target[_in_arc];
+      if (_state[in_arc] == STATE_LOWER) {
+        first  = _source[in_arc];
+        second = _target[in_arc];
       } else {
-        first  = _target[_in_arc];
-        second = _source[_in_arc];
-      }
-      delta = _cap[_in_arc];
+        first  = _target[in_arc];
+        second = _source[in_arc];
+      }
+      delta = _cap[in_arc];
       int result = 0;
       Capacity d;
@@ -1021,10 +1008,10 @@
       // Augment along the cycle
       if (delta > 0) {
-        Capacity val = _state[_in_arc] * delta;
-        _flow[_in_arc] += val;
-        for (int u = _source[_in_arc]; u != join; u = _parent[u]) {
+        Capacity val = _state[in_arc] * delta;
+        _flow[in_arc] += val;
+        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
           _flow[_pred[u]] += _forward[u] ? -val : val;
         }
-        for (int u = _target[_in_arc]; u != join; u = _parent[u]) {
+        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
           _flow[_pred[u]] += _forward[u] ? val : -val;
         }
@@ -1032,9 +1019,9 @@
       // Update the state of the entering and leaving arcs
       if (change) {
-        _state[_in_arc] = STATE_TREE;
+        _state[in_arc] = STATE_TREE;
         _state[_pred[u_out]] =
           (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER;
       } else {
-        _state[_in_arc] = -_state[_in_arc];
+        _state[in_arc] = -_state[in_arc];
       }
     }
@@ -1107,6 +1094,6 @@
         u = v;
       }
-      _pred[u_in] = _in_arc;
-      _forward[u_in] = (u_in == _source[_in_arc]);
+      _pred[u_in] = in_arc;
+      _forward[u_in] = (u_in == _source[in_arc]);
     }
 
@@ -1164,18 +1151,18 @@
       }
 
-      // Copy flow values to _flow_result
+      // Copy flow values to _flow_map
       if (_orig_lower) {
         for (int i = 0; i != _arc_num; ++i) {
-          Arc e = _arc[i];
-          (*_flow_result)[e] = (*_orig_lower)[e] + _flow[i];
+          Arc e = _arc_ref[i];
+          _flow_map->set(e, (*_orig_lower)[e] + _flow[i]);
         }
       } else {
         for (int i = 0; i != _arc_num; ++i) {
-          (*_flow_result)[_arc[i]] = _flow[i];
-        }
-      }
-      // Copy potential values to _potential_result
-      for (int i = 0; i != _node_num; ++i) {
-        (*_potential_result)[_node[i]] = _pi[i];
+          _flow_map->set(_arc_ref[i], _flow[i]);
+        }
+      }
+      // Copy potential values to _potential_map
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _potential_map->set(n, _pi[_node_id[n]]);
       }
 
