# Changeset 991:fb932bcfd803 in lemon for lemon

Ignore:
Timestamp:
09/04/10 23:58:03 (9 years ago)
Branch:
default
Children:
998:3ffd46dc8e01, 1317:b40c2bbb8da5
Phase:
public
Message:

Improve arc mixing in NS and enable it by default (#391)

File:
1 edited

Unmodified
Removed
• ## lemon/network_simplex.h

 r990 /// /// \param graph The digraph the algorithm runs on. /// \param arc_mixing Indicate if the arcs have to be stored in a /// \param arc_mixing Indicate if the arcs will be stored in a /// mixed order in the internal data structure. /// In special cases, it could lead to better overall performance, /// but it is usually slower. Therefore it is disabled by default. NetworkSimplex(const GR& graph, bool arc_mixing = false) : /// In general, it leads to similar performance as using the original /// arc order, but it makes the algorithm more robust and in special /// cases, even significantly faster. Therefore, it is enabled by default. NetworkSimplex(const GR& graph, bool arc_mixing = true) : _graph(graph), _node_id(graph), _arc_id(graph), _arc_mixing(arc_mixing), if (_arc_mixing) { // Store the arcs in a mixed order int k = std::max(int(std::sqrt(double(_arc_num))), 10); const int skip = std::max(_arc_num / _node_num, 3); int i = 0, j = 0; for (ArcIt a(_graph); a != INVALID; ++a) { _source[i] = _node_id[_graph.source(a)]; _target[i] = _node_id[_graph.target(a)]; if ((i += k) >= _arc_num) i = ++j; if ((i += skip) >= _arc_num) i = ++j; } } else {
Note: See TracChangeset for help on using the changeset viewer.