1.1 --- a/lemon/network_simplex.h	Sun Aug 22 23:54:10 2010 +0200
     1.2 +++ b/lemon/network_simplex.h	Sat Sep 04 23:58:03 2010 +0200
     1.3 @@ -636,11 +636,12 @@
     1.4      /// The constructor of the class.
     1.5      ///
     1.6      /// \param graph The digraph the algorithm runs on.
     1.7 -    /// \param arc_mixing Indicate if the arcs have to be stored in a
     1.8 +    /// \param arc_mixing Indicate if the arcs will 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 +    /// In general, it leads to similar performance as using the original
    1.14 +    /// arc order, but it makes the algorithm more robust and in special
    1.15 +    /// cases, even significantly faster. Therefore, it is enabled by default.
    1.16 +    NetworkSimplex(const GR& graph, bool arc_mixing = true) :
    1.17        _graph(graph), _node_id(graph), _arc_id(graph),
    1.18        _arc_mixing(arc_mixing),
    1.19        MAX(std::numeric_limits<Value>::max()),
    1.20 @@ -930,13 +931,13 @@
    1.21        }
    1.22        if (_arc_mixing) {
    1.23          // Store the arcs in a mixed order
    1.24 -        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    1.25 +        const int skip = std::max(_arc_num / _node_num, 3);
    1.26          int i = 0, j = 0;
    1.27          for (ArcIt a(_graph); a != INVALID; ++a) {
    1.28            _arc_id[a] = i;
    1.29            _source[i] = _node_id[_graph.source(a)];
    1.30            _target[i] = _node_id[_graph.target(a)];
    1.31 -          if ((i += k) >= _arc_num) i = ++j;
    1.32 +          if ((i += skip) >= _arc_num) i = ++j;
    1.33          }
    1.34        } else {
    1.35          // Store the arcs in the original order