COIN-OR::LEMON - Graph Library

Changeset 896:fb932bcfd803 in lemon-main


Ignore:
Timestamp:
09/04/10 23:58:03 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
903:3ffd46dc8e01, 1117:b40c2bbb8da5
Phase:
public
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r895 r896  
    637637    ///
    638638    /// \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
    640640    /// 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) :
    644645      _graph(graph), _node_id(graph), _arc_id(graph),
    645646      _arc_mixing(arc_mixing),
     
    931932      if (_arc_mixing) {
    932933        // 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);
    934935        int i = 0, j = 0;
    935936        for (ArcIt a(_graph); a != INVALID; ++a) {
     
    937938          _source[i] = _node_id[_graph.source(a)];
    938939          _target[i] = _node_id[_graph.target(a)];
    939           if ((i += k) >= _arc_num) i = ++j;
     940          if ((i += skip) >= _arc_num) i = ++j;
    940941        }
    941942      } else {
Note: See TracChangeset for help on using the changeset viewer.