623 /// \brief Constructor. |
623 /// \brief Constructor. |
624 /// |
624 /// |
625 /// The constructor of the class. |
625 /// The constructor of the class. |
626 /// |
626 /// |
627 /// \param graph The digraph the algorithm runs on. |
627 /// \param graph The digraph the algorithm runs on. |
628 NetworkSimplex(const GR& graph) : |
628 /// \param arc_mixing Indicate if the arcs have to be stored in a |
|
629 /// mixed order in the internal data structure. |
|
630 /// In special cases, it could lead to better overall performance, |
|
631 /// but it is usually slower. Therefore it is disabled by default. |
|
632 NetworkSimplex(const GR& graph, bool arc_mixing = false) : |
629 _graph(graph), _node_id(graph), _arc_id(graph), |
633 _graph(graph), _node_id(graph), _arc_id(graph), |
630 INF(std::numeric_limits<Value>::has_infinity ? |
634 INF(std::numeric_limits<Value>::has_infinity ? |
631 std::numeric_limits<Value>::infinity() : |
635 std::numeric_limits<Value>::infinity() : |
632 std::numeric_limits<Value>::max()) |
636 std::numeric_limits<Value>::max()) |
633 { |
637 { |
661 _rev_thread.resize(all_node_num); |
665 _rev_thread.resize(all_node_num); |
662 _succ_num.resize(all_node_num); |
666 _succ_num.resize(all_node_num); |
663 _last_succ.resize(all_node_num); |
667 _last_succ.resize(all_node_num); |
664 _state.resize(max_arc_num); |
668 _state.resize(max_arc_num); |
665 |
669 |
666 // Copy the graph (store the arcs in a mixed order) |
670 // Copy the graph |
667 int i = 0; |
671 int i = 0; |
668 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
672 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { |
669 _node_id[n] = i; |
673 _node_id[n] = i; |
670 } |
674 } |
671 int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
675 if (arc_mixing) { |
672 i = 0; |
676 // Store the arcs in a mixed order |
673 for (ArcIt a(_graph); a != INVALID; ++a) { |
677 int k = std::max(int(std::sqrt(double(_arc_num))), 10); |
674 _arc_id[a] = i; |
678 int i = 0, j = 0; |
675 _source[i] = _node_id[_graph.source(a)]; |
679 for (ArcIt a(_graph); a != INVALID; ++a) { |
676 _target[i] = _node_id[_graph.target(a)]; |
680 _arc_id[a] = i; |
677 if ((i += k) >= _arc_num) i = (i % k) + 1; |
681 _source[i] = _node_id[_graph.source(a)]; |
|
682 _target[i] = _node_id[_graph.target(a)]; |
|
683 if ((i += k) >= _arc_num) i = ++j; |
|
684 } |
|
685 } else { |
|
686 // Store the arcs in the original order |
|
687 int i = 0; |
|
688 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { |
|
689 _arc_id[a] = i; |
|
690 _source[i] = _node_id[_graph.source(a)]; |
|
691 _target[i] = _node_id[_graph.target(a)]; |
|
692 } |
678 } |
693 } |
679 |
694 |
680 // Initialize maps |
695 // Initialize maps |
681 for (int i = 0; i != _node_num; ++i) { |
696 for (int i = 0; i != _node_num; ++i) { |
682 _supply[i] = 0; |
697 _supply[i] = 0; |