COIN-OR::LEMON - Graph Library

Changeset 728:e2bdd1a988f3 in lemon-main


Ignore:
Timestamp:
07/02/09 17:36:29 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add a parameter to control arc mixing in NS (#298)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r727 r728  
    626626    ///
    627627    /// \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) :
    629633      _graph(graph), _node_id(graph), _arc_id(graph),
    630634      INF(std::numeric_limits<Value>::has_infinity ?
     
    664668      _state.resize(max_arc_num);
    665669
    666       // Copy the graph (store the arcs in a mixed order)
     670      // Copy the graph
    667671      int i = 0;
    668672      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    669673        _node_id[n] = i;
    670674      }
    671       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    672       i = 0;
    673       for (ArcIt a(_graph); a != INVALID; ++a) {
    674         _arc_id[a] = i;
    675         _source[i] = _node_id[_graph.source(a)];
    676         _target[i] = _node_id[_graph.target(a)];
    677         if ((i += k) >= _arc_num) i = (i % k) + 1;
     675      if (arc_mixing) {
     676        // Store the arcs in a mixed order
     677        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     678        int i = 0, j = 0;
     679        for (ArcIt a(_graph); a != INVALID; ++a) {
     680          _arc_id[a] = i;
     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        }
    678693      }
    679694     
Note: See TracChangeset for help on using the changeset viewer.