Changeset - r896:fb932bcfd803
« 895:dca9ee
903:3ffd46 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Improve arc mixing in NS and enable it by default (#391)
0 1 0
default
1 file changed with 7 insertions and 6 deletions:
lemon/network_simplex.h
7
6
↑ Collapse diff ↑
lemon/network_simplex.h
Show white space 6 line context
... ... 
@@ -636,11 +636,12 @@
636 636 
    /// The constructor of the class.
637 637 
    ///
638 638 
    /// \param graph The digraph the algorithm runs on.
639 
    /// \param arc_mixing Indicate if the arcs have to be stored in a
639 
    /// \param arc_mixing Indicate if the arcs will be stored in a
640 640 
    /// mixed order in the internal data structure.
641 
    /// In special cases, it could lead to better overall performance,
642 
    /// but it is usually slower. Therefore it is disabled by default.
643 
    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
641 
    /// In general, it leads to similar performance as using the original
642 
    /// arc order, but it makes the algorithm more robust and in special
643 
    /// cases, even significantly faster. Therefore, it is enabled by default.
644 
    NetworkSimplex(const GR& graph, bool arc_mixing = true) :
644 645 
      _graph(graph), _node_id(graph), _arc_id(graph),
645 646 
      _arc_mixing(arc_mixing),
646 647 
      MAX(std::numeric_limits<Value>::max()),
... ... 
@@ -930,13 +931,13 @@
930 931 
      }
931 932 
      if (_arc_mixing) {
932 933 
        // Store the arcs in a mixed order
933 
        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
934 
        const int skip = std::max(_arc_num / _node_num, 3);
934 935 
        int i = 0, j = 0;
935 936 
        for (ArcIt a(_graph); a != INVALID; ++a) {
936 937 
          _arc_id[a] = i;
937 938 
          _source[i] = _node_id[_graph.source(a)];
938 939 
          _target[i] = _node_id[_graph.target(a)];
939 
          if ((i += k) >= _arc_num) i = ++j;
940 
          if ((i += skip) >= _arc_num) i = ++j;
940 941 
        }
941 942 
      } else {
942 943 
        // Store the arcs in the original order
0 comments (0 inline)