1.1 --- a/lemon/capacity_scaling.h	Wed Feb 01 06:43:50 2012 +0100
     1.2 +++ b/lemon/capacity_scaling.h	Fri Feb 03 05:55:39 2012 +0100
     1.3 @@ -87,8 +87,8 @@
     1.4    /// consider to use the named template parameters instead.
     1.5    ///
     1.6    /// \warning Both \c V and \c C must be signed number types.
     1.7 -  /// \warning All input data (capacities, supply values, and costs) must
     1.8 -  /// be integer.
     1.9 +  /// \warning Capacity bounds and supply values must be integer, but
    1.10 +  /// arc costs can be arbitrary real numbers.
    1.11    /// \warning This algorithm does not support negative costs for
    1.12    /// arcs having infinite upper bound.
    1.13  #ifdef DOXYGEN

     2.1 --- a/lemon/network_simplex.h	Wed Feb 01 06:43:50 2012 +0100
     2.2 +++ b/lemon/network_simplex.h	Fri Feb 03 05:55:39 2012 +0100
     2.3 @@ -122,14 +122,17 @@
     2.4      /// Enum type containing constants for selecting the pivot rule for
     2.5      /// the \ref run() function.
     2.6      ///
     2.7 -    /// \ref NetworkSimplex provides five different pivot rule
     2.8 -    /// implementations that significantly affect the running time
     2.9 +    /// \ref NetworkSimplex provides five different implementations for
    2.10 +    /// the pivot strategy that significantly affects the running time
    2.11      /// of the algorithm.
    2.12 -    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    2.13 -    /// turend out to be the most efficient and the most robust on various
    2.14 -    /// test inputs.
    2.15 -    /// However, another pivot rule can be selected using the \ref run()
    2.16 -    /// function with the proper parameter.
    2.17 +    /// According to experimental tests conducted on various problem
    2.18 +    /// instances, \ref BLOCK_SEARCH "Block Search" and
    2.19 +    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
    2.20 +    /// to be the most efficient.
    2.21 +    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
    2.22 +    /// seemed to be slightly more robust, it is used by default.
    2.23 +    /// However, another pivot rule can easily be selected using the
    2.24 +    /// \ref run() function with the proper parameter.
    2.25      enum PivotRule {
    2.26  
    2.27        /// The \e First \e Eligible pivot rule.
    2.28 @@ -155,7 +158,7 @@
    2.29  
    2.30        /// The \e Altering \e Candidate \e List pivot rule.
    2.31        /// It is a modified version of the Candidate List method.
    2.32 -      /// It keeps only the several best eligible arcs from the former
    2.33 +      /// It keeps only a few of the best eligible arcs from the former
    2.34        /// candidate list and extends this list in every iteration.
    2.35        ALTERING_LIST
    2.36      };
    2.37 @@ -538,7 +541,7 @@
    2.38        public:
    2.39          SortFunc(const CostVector &map) : _map(map) {}
    2.40          bool operator()(int left, int right) {
    2.41 -          return _map[left] > _map[right];
    2.42 +          return _map[left] < _map[right];
    2.43          }
    2.44        };
    2.45  
    2.46 @@ -556,7 +559,7 @@
    2.47          // The main parameters of the pivot rule
    2.48          const double BLOCK_SIZE_FACTOR = 1.0;
    2.49          const int MIN_BLOCK_SIZE = 10;
    2.50 -        const double HEAD_LENGTH_FACTOR = 0.1;
    2.51 +        const double HEAD_LENGTH_FACTOR = 0.01;
    2.52          const int MIN_HEAD_LENGTH = 3;
    2.53  
    2.54          _block_size = std::max( int(BLOCK_SIZE_FACTOR *
    2.55 @@ -600,9 +603,9 @@
    2.56            }
    2.57          }
    2.58          for (e = 0; e != _next_arc; ++e) {
    2.59 -          _cand_cost[e] = _state[e] *
    2.60 -            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    2.61 -          if (_cand_cost[e] < 0) {
    2.62 +          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    2.63 +          if (c < 0) {
    2.64 +            _cand_cost[e] = c;
    2.65              _candidates[_curr_length++] = e;
    2.66            }
    2.67            if (--cnt == 0) {
    2.68 @@ -615,16 +618,16 @@
    2.69  
    2.70        search_end:
    2.71  
    2.72 -        // Make heap of the candidate list (approximating a partial sort)
    2.73 -        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    2.74 -                   _sort_func );
    2.75 +        // Perform partial sort operation on the candidate list
    2.76 +        int new_length = std::min(_head_length + 1, _curr_length);
    2.77 +        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
    2.78 +                          _candidates.begin() + _curr_length, _sort_func);
    2.79  
    2.80 -        // Pop the first element of the heap
    2.81 +        // Select the entering arc and remove it from the list
    2.82          _in_arc = _candidates[0];
    2.83          _next_arc = e;
    2.84 -        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    2.85 -                  _sort_func );
    2.86 -        _curr_length = std::min(_head_length, _curr_length - 1);
    2.87 +        _candidates[0] = _candidates[new_length - 1];
    2.88 +        _curr_length = new_length - 1;
    2.89          return true;
    2.90        }
    2.91