Changeset 1166:d59484d5fc1f in lemon for lemon/network_simplex.h
 Timestamp:
 11/07/12 17:39:39 (7 years ago)
 Branch:
 default
 Parents:
 1163:e344f0887c59 (diff), 1165:16f55008c863 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r1136 r1166 49 49 /// 50 50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 51 /// implementations available in LEMON for this problem. 51 /// implementations available in LEMON for solving this problem. 52 /// (For more information, see \ref min_cost_flow_algs "the module page".) 52 53 /// Furthermore, this class supports both directions of the supply/demand 53 54 /// inequality constraints. For more information, see \ref SupplyType. … … 1010 1011 } 1011 1012 1012 /// \brief Return the flow map (the primal solution). 1013 /// \brief Copy the flow values (the primal solution) into the 1014 /// given map. 1013 1015 /// 1014 1016 /// This function copies the flow value on each arc into the given … … 1034 1036 } 1035 1037 1036 /// \brief Return the potential map (the dual solution). 1038 /// \brief Copy the potential values (the dual solution) into the 1039 /// given map. 1037 1040 /// 1038 1041 /// This function copies the potential (dual value) of each node 
lemon/network_simplex.h
r1165 r1166 124 124 /// the \ref run() function. 125 125 /// 126 /// \ref NetworkSimplex provides five different pivot rule127 /// implementations that significantly affectthe running time126 /// \ref NetworkSimplex provides five different implementations for 127 /// the pivot strategy that significantly affects the running time 128 128 /// of the algorithm. 129 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 130 /// turend out to be the most efficient and the most robust on various 131 /// test inputs. 132 /// However, another pivot rule can be selected using the \ref run() 133 /// function with the proper parameter. 129 /// According to experimental tests conducted on various problem 130 /// instances, \ref BLOCK_SEARCH "Block Search" and 131 /// \ref ALTERING_LIST "Altering Candidate List" rules turned out 132 /// to be the most efficient. 133 /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that 134 /// seemed to be slightly more robust, it is used by default. 135 /// However, another pivot rule can easily be selected using the 136 /// \ref run() function with the proper parameter. 134 137 enum PivotRule { 135 138 … … 157 160 /// The \e Altering \e Candidate \e List pivot rule. 158 161 /// It is a modified version of the Candidate List method. 159 /// It keeps only the severalbest eligible arcs from the former162 /// It keeps only a few of the best eligible arcs from the former 160 163 /// candidate list and extends this list in every iteration. 161 164 ALTERING_LIST … … 540 543 SortFunc(const CostVector &map) : _map(map) {} 541 544 bool operator()(int left, int right) { 542 return _map[left] >_map[right];545 return _map[left] < _map[right]; 543 546 } 544 547 }; … … 558 561 const double BLOCK_SIZE_FACTOR = 1.0; 559 562 const int MIN_BLOCK_SIZE = 10; 560 const double HEAD_LENGTH_FACTOR = 0. 1;563 const double HEAD_LENGTH_FACTOR = 0.01; 561 564 const int MIN_HEAD_LENGTH = 3; 562 565 … … 602 605 } 603 606 for (e = 0; e != _next_arc; ++e) { 604 _cand_cost[e] = _state[e] *605 (_cost[e] + _pi[_source[e]]  _pi[_target[e]]);606 if (_cand_cost[e] < 0) {607 c = _state[e] * (_cost[e] + _pi[_source[e]]  _pi[_target[e]]); 608 if (c < 0) { 609 _cand_cost[e] = c; 607 610 _candidates[_curr_length++] = e; 608 611 } … … 617 620 search_end: 618 621 619 // Make heap of the candidate list (approximating a partial sort) 620 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, 621 _sort_func ); 622 623 // Pop the first element of the heap 622 // Perform partial sort operation on the candidate list 623 int new_length = std::min(_head_length + 1, _curr_length); 624 std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, 625 _candidates.begin() + _curr_length, _sort_func); 626 627 // Select the entering arc and remove it from the list 624 628 _in_arc = _candidates[0]; 625 629 _next_arc = e; 626 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 627 _sort_func ); 628 _curr_length = std::min(_head_length, _curr_length  1); 630 _candidates[0] = _candidates[new_length  1]; 631 _curr_length = new_length  1; 629 632 return true; 630 633 }
Note: See TracChangeset
for help on using the changeset viewer.