Changeset - r775:e2bdd1a988f3
« 774:cab85b
777:4a45c8 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Add a parameter to control arc mixing in NS (#298)
0 1 0
default
1 file changed with 19 insertions and 4 deletions:
lemon/network_simplex.h
19
4
↑ Collapse diff ↑
lemon/network_simplex.h
Show white space 6 line context
... ... 
@@ -625,7 +625,11 @@
625 625 
    /// The constructor of the class.
626 626 
    ///
627 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 633 
      _graph(graph), _node_id(graph), _arc_id(graph),
630 634 
      INF(std::numeric_limits<Value>::has_infinity ?
631 635 
          std::numeric_limits<Value>::infinity() :
... ... 
@@ -663,18 +667,29 @@
663 667 
      _last_succ.resize(all_node_num);
664 668 
      _state.resize(max_arc_num);
665 669 

			




	666
	
	
		
      // Copy the graph (store the arcs in a mixed order)


			




	
	670
	
		
      // Copy the graph


			




	667
	671
	
		
      int i = 0;


			




	668
	672
	
		
      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {


			




	669
	673
	
		
        _node_id[n] = i;


			




	670
	674
	
		
      }


			




	
	675
	
		
      if (arc_mixing) {


			




	
	676
	
		
        // Store the arcs in a mixed order


			




	671
	677
	
		
      int k = std::max(int(std::sqrt(double(_arc_num))), 10);


			




	672
	
	
		
      i = 0;


			




	
	678
	
		
        int i = 0, j = 0;


			




	673
	679
	
		
      for (ArcIt a(_graph); a != INVALID; ++a) {


			




	674
	680
	
		
        _arc_id[a] = i;


			




	675
	681
	
		
        _source[i] = _node_id[_graph.source(a)];


			




	676
	682
	
		
        _target[i] = _node_id[_graph.target(a)];


			




	677
	
	
		
        if ((i += k) >= _arc_num) i = (i % k) + 1;


			




	
	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
	695
	
		
      // Initialize maps


			




        

    






    
    



    


    

     
    
0 comments (0 inline)