Changeset 1241:879fcb781086 in lemon for lemon/cycle_canceling.h
 Timestamp:
 07/30/13 15:24:45 (6 years ago)
 Branch:
 default
 Parents:
 1239:d1a48668ddb4 (diff), 1240:ee9bac10f58e (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/cycle_canceling.h
r1221 r1241 671 671 if (_sum_supply > 0) return INFEASIBLE; 672 672 673 // Check lower and upper bounds 674 LEMON_DEBUG(checkBoundMaps(), 675 "Upper bounds must be greater or equal to the lower bounds"); 676 673 677 674 678 // Initialize vectors … … 779 783 780 784 return OPTIMAL; 785 } 786 787 // Check if the upper bound is greater or equal to the lower bound 788 // on each arc. 789 bool checkBoundMaps() { 790 for (int j = 0; j != _res_arc_num; ++j) { 791 if (_upper[j] < _lower[j]) return false; 792 } 793 return true; 781 794 } 782 795 
lemon/cycle_canceling.h
r1240 r1241 48 48 /// \ref CycleCanceling implements three different cyclecanceling 49 49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" 50 /// \ ref amo93networkflows, \refklein67primal,51 /// \ refgoldberg89cyclecanceling.50 /// \cite amo93networkflows, \cite klein67primal, 51 /// \cite goldberg89cyclecanceling. 52 52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 53 53 /// "CancelandTighten" algorithm, thus it is the default method. 54 /// It runs in strongly polynomial time , but in practice, it is typically55 /// orders of magnitude slower than the scaling algorithms and56 /// \ref NetworkSimplex.54 /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)), 55 /// but in practice, it is typically orders of magnitude slower than 56 /// the scaling algorithms and \ref NetworkSimplex. 57 57 /// (For more information, see \ref min_cost_flow_algs "the module page".) 58 58 /// … … 132 132 /// The "Minimum Mean CycleCanceling" algorithm, which is a 133 133 /// wellknown strongly polynomial method 134 /// \ refgoldberg89cyclecanceling. It improves along a134 /// \cite goldberg89cyclecanceling. It improves along a 135 135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 136 136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). … … 138 138 /// The "CancelandTighten" algorithm, which can be viewed as an 139 139 /// improved version of the previous method 140 /// \ refgoldberg89cyclecanceling.140 /// \cite goldberg89cyclecanceling. 141 141 /// It is faster both in theory and in practice, its running time 142 142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
Note: See TracChangeset
for help on using the changeset viewer.