634 /// \brief Constructor. |
634 /// \brief Constructor. |
635 /// |
635 /// |
636 /// The constructor of the class. |
636 /// The constructor of the class. |
637 /// |
637 /// |
638 /// \param graph The digraph the algorithm runs on. |
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 /// mixed order in the internal data structure. |
640 /// mixed order in the internal data structure. |
641 /// In special cases, it could lead to better overall performance, |
641 /// In general, it leads to similar performance as using the original |
642 /// but it is usually slower. Therefore it is disabled by default. |
642 /// arc order, but it makes the algorithm more robust and in special |
643 NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
643 /// cases, even significantly faster. Therefore, it is enabled by default. |
|
644 NetworkSimplex(const GR& graph, bool arc_mixing = true) : |
644 _graph(graph), _node_id(graph), _arc_id(graph), |
645 _graph(graph), _node_id(graph), _arc_id(graph), |
645 _arc_mixing(arc_mixing), |
646 _arc_mixing(arc_mixing), |
646 MAX(std::numeric_limits<Value>::max()), |
647 MAX(std::numeric_limits<Value>::max()), |
647 INF(std::numeric_limits<Value>::has_infinity ? |
648 INF(std::numeric_limits<Value>::has_infinity ? |
648 std::numeric_limits<Value>::infinity() : MAX) |
649 std::numeric_limits<Value>::infinity() : MAX) |
928 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
929 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
929 _node_id[n] = i; |
930 _node_id[n] = i; |
930 } |
931 } |
931 if (_arc_mixing) { |
932 if (_arc_mixing) { |
932 // Store the arcs in a mixed order |
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 int i = 0, j = 0; |
935 int i = 0, j = 0; |
935 for (ArcIt a(_graph); a != INVALID; ++a) { |
936 for (ArcIt a(_graph); a != INVALID; ++a) { |
936 _arc_id[a] = i; |
937 _arc_id[a] = i; |
937 _source[i] = _node_id[_graph.source(a)]; |
938 _source[i] = _node_id[_graph.source(a)]; |
938 _target[i] = _node_id[_graph.target(a)]; |
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 } else { |
942 } else { |
942 // Store the arcs in the original order |
943 // Store the arcs in the original order |
943 int i = 0; |
944 int i = 0; |
944 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { |
945 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { |