COIN-OR::LEMON - Graph Library

Changeset 775:e2bdd1a988f3 in lemon


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

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r774 r775  
    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.