Changeset 1071:879fcb781086 in lemon-main for lemon/cycle_canceling.h
- Timestamp:
- 07/30/13 15:24:45 (11 years ago)
- Branch:
- default
- Parents:
- 1069:d1a48668ddb4 (diff), 1070: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
r1053 r1071 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
r1070 r1071 48 48 /// \ref CycleCanceling implements three different cycle-canceling 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 /// "Cancel-and-Tighten" 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 Cycle-Canceling" algorithm, which is a 133 133 /// well-known 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 "Cancel-and-Tighten" 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.