1.1 --- a/lemon/network_simplex.h	Mon Jan 30 19:29:03 2012 +0100
     1.2 +++ b/lemon/network_simplex.h	Fri Feb 03 05:55:01 2012 +0100
     1.3 @@ -122,14 +122,17 @@
     1.4      /// Enum type containing constants for selecting the pivot rule for
     1.5      /// the \ref run() function.
     1.6      ///
     1.7 -    /// \ref NetworkSimplex provides five different pivot rule
     1.8 -    /// implementations that significantly affect the running time
     1.9 +    /// \ref NetworkSimplex provides five different implementations for
    1.10 +    /// the pivot strategy that significantly affects the running time
    1.11      /// of the algorithm.
    1.12 -    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    1.13 -    /// turend out to be the most efficient and the most robust on various
    1.14 -    /// test inputs.
    1.15 -    /// However, another pivot rule can be selected using the \ref run()
    1.16 -    /// function with the proper parameter.
    1.17 +    /// According to experimental tests conducted on various problem
    1.18 +    /// instances, \ref BLOCK_SEARCH "Block Search" and
    1.19 +    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
    1.20 +    /// to be the most efficient.
    1.21 +    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
    1.22 +    /// seemed to be slightly more robust, it is used by default.
    1.23 +    /// However, another pivot rule can easily be selected using the
    1.24 +    /// \ref run() function with the proper parameter.
    1.25      enum PivotRule {
    1.26  
    1.27        /// The \e First \e Eligible pivot rule.
    1.28 @@ -155,7 +158,7 @@
    1.29  
    1.30        /// The \e Altering \e Candidate \e List pivot rule.
    1.31        /// It is a modified version of the Candidate List method.
    1.32 -      /// It keeps only the several best eligible arcs from the former
    1.33 +      /// It keeps only a few of the best eligible arcs from the former
    1.34        /// candidate list and extends this list in every iteration.
    1.35        ALTERING_LIST
    1.36      };
    1.37 @@ -538,7 +541,7 @@
    1.38        public:
    1.39          SortFunc(const CostVector &map) : _map(map) {}
    1.40          bool operator()(int left, int right) {
    1.41 -          return _map[left] > _map[right];
    1.42 +          return _map[left] < _map[right];
    1.43          }
    1.44        };
    1.45  
    1.46 @@ -556,7 +559,7 @@
    1.47          // The main parameters of the pivot rule
    1.48          const double BLOCK_SIZE_FACTOR = 1.0;
    1.49          const int MIN_BLOCK_SIZE = 10;
    1.50 -        const double HEAD_LENGTH_FACTOR = 0.1;
    1.51 +        const double HEAD_LENGTH_FACTOR = 0.01;
    1.52          const int MIN_HEAD_LENGTH = 3;
    1.53  
    1.54          _block_size = std::max( int(BLOCK_SIZE_FACTOR *
    1.55 @@ -600,9 +603,9 @@
    1.56            }
    1.57          }
    1.58          for (e = 0; e != _next_arc; ++e) {
    1.59 -          _cand_cost[e] = _state[e] *
    1.60 -            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    1.61 -          if (_cand_cost[e] < 0) {
    1.62 +          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    1.63 +          if (c < 0) {
    1.64 +            _cand_cost[e] = c;
    1.65              _candidates[_curr_length++] = e;
    1.66            }
    1.67            if (--cnt == 0) {
    1.68 @@ -615,16 +618,16 @@
    1.69  
    1.70        search_end:
    1.71  
    1.72 -        // Make heap of the candidate list (approximating a partial sort)
    1.73 -        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    1.74 -                   _sort_func );
    1.75 +        // Perform partial sort operation on the candidate list
    1.76 +        int new_length = std::min(_head_length + 1, _curr_length);
    1.77 +        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
    1.78 +                          _candidates.begin() + _curr_length, _sort_func);
    1.79  
    1.80 -        // Pop the first element of the heap
    1.81 +        // Select the entering arc and remove it from the list
    1.82          _in_arc = _candidates[0];
    1.83          _next_arc = e;
    1.84 -        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    1.85 -                  _sort_func );
    1.86 -        _curr_length = std::min(_head_length, _curr_length - 1);
    1.87 +        _candidates[0] = _candidates[new_length - 1];
    1.88 +        _curr_length = new_length - 1;
    1.89          return true;
    1.90        }
    1.91