Changeset - r896:fb932bcfd803
« 895:dca9ee
903:3ffd46 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Improve arc mixing in NS and enable it by default (#391)
0 1 0
default
1 file changed with 7 insertions and 6 deletions:
lemon/network_simplex.h
7
6
↑ Collapse diff ↑
lemon/network_simplex.h
Show white space 12 line context
... ... 
@@ -633,17 +633,18 @@
633 633 

			




	634
	634
	
		
    /// \brief Constructor.


			




	635
	635
	
		
    ///


			




	636
	636
	
		
    /// The constructor of the class.


			




	637
	637
	
		
    ///


			




	638
	638
	
		
    /// \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


			




	640
	640
	
		
    /// 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) :


			




	644
	645
	
		
      _graph(graph), _node_id(graph), _arc_id(graph),


			




	645
	646
	
		
      _arc_mixing(arc_mixing),


			




	646
	647
	
		
      MAX(std::numeric_limits<Value>::max()),


			




	647
	648
	
		
      INF(std::numeric_limits<Value>::has_infinity ?


			




	648
	649
	
		
          std::numeric_limits<Value>::infinity() : MAX)


			




	649
	650
	
		
    {


			




	...
	...
	
		
@@ -927,19 +928,19 @@


			




	927
	928
	
		
      int i = 0;


			




	928
	929
	
		
      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {


			




	929
	930
	
		
        _node_id[n] = i;


			




	930
	931
	
		
      }


			




	931
	932
	
		
      if (_arc_mixing) {


			




	932
	933
	
		
        // 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);


			




	934
	935
	
		
        int i = 0, j = 0;


			




	935
	936
	
		
        for (ArcIt a(_graph); a != INVALID; ++a) {


			




	936
	937
	
		
          _arc_id[a] = i;


			




	937
	938
	
		
          _source[i] = _node_id[_graph.source(a)];


			




	938
	939
	
		
          _target[i] = _node_id[_graph.target(a)];


			




	939
	
	
		
          if ((i += k) >= _arc_num) i = ++j;


			




	
	940
	
		
          if ((i += skip) >= _arc_num) i = ++j;


			




	940
	941
	
		
        }


			




	941
	942
	
		
      } else {


			




	942
	943
	
		
        // Store the arcs in the original order


			




	943
	944
	
		
        int i = 0;


			




	944
	945
	
		
        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {


			




	945
	946
	
		
          _arc_id[a] = i;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)