Changeset 1136:fcb6ad1e67d0 in lemon for lemon/network_simplex.h
 Timestamp:
 01/30/12 20:21:45 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r1026 r1136 123 123 /// the \ref run() function. 124 124 /// 125 /// \ref NetworkSimplex provides five different pivot rule126 /// implementations that significantly affectthe running time125 /// \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 { 134 137 … … 156 159 /// The \e Altering \e Candidate \e List pivot rule. 157 160 /// It is a modified version of the Candidate List method. 158 /// It keeps only the severalbest eligible arcs from the former161 /// It keeps only a few of the best eligible arcs from the former 159 162 /// candidate list and extends this list in every iteration. 160 163 ALTERING_LIST … … 539 542 SortFunc(const CostVector &map) : _map(map) {} 540 543 bool operator()(int left, int right) { 541 return _map[left] >_map[right];544 return _map[left] < _map[right]; 542 545 } 543 546 }; … … 557 560 const double BLOCK_SIZE_FACTOR = 1.0; 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; 561 564 … … 601 604 } 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; 607 610 } … … 616 619 search_end: 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 622 // Pop the first element of the heap 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); 625 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; 629 632 }
Note: See TracChangeset
for help on using the changeset viewer.