1.1 --- a/lemon/network_simplex.h	Wed Jul 01 16:34:01 2009 +0200
     1.2 +++ b/lemon/network_simplex.h	Thu Jul 02 17:36:29 2009 +0200
     1.3 @@ -625,7 +625,11 @@
     1.4      /// The constructor of the class.
     1.5      ///
     1.6      /// \param graph The digraph the algorithm runs on.
     1.7 -    NetworkSimplex(const GR& graph) :
     1.8 +    /// \param arc_mixing Indicate if the arcs have to be stored in a
     1.9 +    /// mixed order in the internal data structure. 
    1.10 +    /// In special cases, it could lead to better overall performance,
    1.11 +    /// but it is usually slower. Therefore it is disabled by default.
    1.12 +    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    1.13        _graph(graph), _node_id(graph), _arc_id(graph),
    1.14        INF(std::numeric_limits<Value>::has_infinity ?
    1.15            std::numeric_limits<Value>::infinity() :
    1.16 @@ -663,18 +667,29 @@
    1.17        _last_succ.resize(all_node_num);
    1.18        _state.resize(max_arc_num);
    1.19  
    1.20 -      // Copy the graph (store the arcs in a mixed order)
    1.21 +      // Copy the graph
    1.22        int i = 0;
    1.23        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    1.24          _node_id[n] = i;
    1.25        }
    1.26 -      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    1.27 -      i = 0;
    1.28 -      for (ArcIt a(_graph); a != INVALID; ++a) {
    1.29 -        _arc_id[a] = i;
    1.30 -        _source[i] = _node_id[_graph.source(a)];
    1.31 -        _target[i] = _node_id[_graph.target(a)];
    1.32 -        if ((i += k) >= _arc_num) i = (i % k) + 1;
    1.33 +      if (arc_mixing) {
    1.34 +        // Store the arcs in a mixed order
    1.35 +        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    1.36 +        int i = 0, j = 0;
    1.37 +        for (ArcIt a(_graph); a != INVALID; ++a) {
    1.38 +          _arc_id[a] = i;
    1.39 +          _source[i] = _node_id[_graph.source(a)];
    1.40 +          _target[i] = _node_id[_graph.target(a)];
    1.41 +          if ((i += k) >= _arc_num) i = ++j;
    1.42 +        }
    1.43 +      } else {
    1.44 +        // Store the arcs in the original order
    1.45 +        int i = 0;
    1.46 +        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    1.47 +          _arc_id[a] = i;
    1.48 +          _source[i] = _node_id[_graph.source(a)];
    1.49 +          _target[i] = _node_id[_graph.target(a)];
    1.50 +        }
    1.51        }
    1.52        
    1.53        // Initialize maps