No children
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 2 0
merge tip default
0 files changed with 25 insertions and 22 deletions:
↑ Collapse diff ↑
Show white space 6 line context
... ...
@@ -89,4 +89,4 @@
89 89
  /// \warning Both \c V and \c C must be signed number types.
90
  /// \warning All input data (capacities, supply values, and costs) must
91
  /// be integer.
90
  /// \warning Capacity bounds and supply values must be integer, but
91
  /// arc costs can be arbitrary real numbers.
92 92
  /// \warning This algorithm does not support negative costs for
Ignore white space 6 line context
... ...
@@ -124,10 +124,13 @@
124 124
    ///
125
    /// \ref NetworkSimplex provides five different pivot rule
126
    /// implementations that significantly affect the running time
125
    /// \ref NetworkSimplex provides five different implementations for
126
    /// the pivot strategy that significantly affects the running time
127 127
    /// of the algorithm.
128
    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
129
    /// turend out to be the most efficient and the most robust on various
130
    /// test inputs.
131
    /// However, another pivot rule can be selected using the \ref run()
132
    /// function with the proper parameter.
128
    /// According to experimental tests conducted on various problem
129
    /// instances, \ref BLOCK_SEARCH "Block Search" and
130
    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
131
    /// to be the most efficient.
132
    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
133
    /// seemed to be slightly more robust, it is used by default.
134
    /// However, another pivot rule can easily be selected using the
135
    /// \ref run() function with the proper parameter.
133 136
    enum PivotRule {
... ...
@@ -157,3 +160,3 @@
157 160
      /// It is a modified version of the Candidate List method.
158
      /// It keeps only the several best eligible arcs from the former
161
      /// It keeps only a few of the best eligible arcs from the former
159 162
      /// candidate list and extends this list in every iteration.
... ...
@@ -540,3 +543,3 @@
540 543
        bool operator()(int left, int right) {
541
          return _map[left] > _map[right];
544
          return _map[left] < _map[right];
542 545
        }
... ...
@@ -558,3 +561,3 @@
558 561
        const int MIN_BLOCK_SIZE = 10;
559
        const double HEAD_LENGTH_FACTOR = 0.1;
562
        const double HEAD_LENGTH_FACTOR = 0.01;
560 563
        const int MIN_HEAD_LENGTH = 3;
... ...
@@ -602,5 +605,5 @@
602 605
        for (e = 0; e != _next_arc; ++e) {
603
          _cand_cost[e] = _state[e] *
604
            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
605
          if (_cand_cost[e] < 0) {
606
          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
607
          if (c < 0) {
608
            _cand_cost[e] = c;
606 609
            _candidates[_curr_length++] = e;
... ...
@@ -617,12 +620,12 @@
617 620

	
618
        // Make heap of the candidate list (approximating a partial sort)
619
        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
620
                   _sort_func );
621
        // Perform partial sort operation on the candidate list
622
        int new_length = std::min(_head_length + 1, _curr_length);
623
        std::partial_sort(_candidates.begin(), _candidates.begin() + new_length,
624
                          _candidates.begin() + _curr_length, _sort_func);
621 625

	
622
        // Pop the first element of the heap
626
        // Select the entering arc and remove it from the list
623 627
        _in_arc = _candidates[0];
624 628
        _next_arc = e;
625
        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
626
                  _sort_func );
627
        _curr_length = std::min(_head_length, _curr_length - 1);
629
        _candidates[0] = _candidates[new_length - 1];
630
        _curr_length = new_length - 1;
628 631
        return true;
0 comments (0 inline)