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 2 line context
... ... 
@@ -638,7 +638,8 @@
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),
... ... 
@@ -932,3 +933,3 @@
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;
... ... 
@@ -938,3 +939,3 @@
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 
        }
0 comments (0 inline)