Changeset 1298:a78e5b779b69 in lemon for lemon/cycle_canceling.h
 Timestamp:
 10/17/13 15:08:41 (6 years ago)
 Branch:
 default
 Children:
 1299:b6bad215bccd, 1300:62dba6c90f35
 Parents:
 1294:15e233f588da (diff), 1297:c0c2f5c87aa6 (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
r1270 r1298 196 196 197 197 // Parameters of the problem 198 bool _ha ve_lower;198 bool _has_lower; 199 199 Value _sum_supply; 200 200 … … 279 279 template <typename LowerMap> 280 280 CycleCanceling& lowerMap(const LowerMap& map) { 281 _ha ve_lower = true;281 _has_lower = true; 282 282 for (ArcIt a(_graph); a != INVALID; ++a) { 283 283 _lower[_arc_idf[a]] = map[a]; 284 _lower[_arc_idb[a]] = map[a];285 284 } 286 285 return *this; … … 472 471 _cost[_reverse[j]] = 0; 473 472 } 474 _ha ve_lower = false;473 _has_lower = false; 475 474 return *this; 476 475 } … … 685 684 const Value MAX = std::numeric_limits<Value>::max(); 686 685 int last_out; 687 if (_ha ve_lower) {686 if (_has_lower) { 688 687 for (int i = 0; i != _root; ++i) { 689 688 last_out = _first_out[i+1]; … … 728 727 sup[n] = _supply[_node_id[n]]; 729 728 } 730 if (_ha ve_lower) {729 if (_has_lower) { 731 730 for (ArcIt a(_graph); a != INVALID; ++a) { 732 731 int j = _arc_idf[a]; … … 785 784 } 786 785 787 // Check if the upper bound is greater or equal to the lower bound788 // on each arc.786 // Check if the upper bound is greater than or equal to the lower bound 787 // on each forward arc. 789 788 bool checkBoundMaps() { 790 789 for (int j = 0; j != _res_arc_num; ++j) { 791 if (_ upper[j] < _lower[j]) return false;790 if (_forward[j] && _upper[j] < _lower[j]) return false; 792 791 } 793 792 return true; … … 836 835 837 836 // Handle nonzero lower bounds 838 if (_ha ve_lower) {837 if (_has_lower) { 839 838 int limit = _first_out[_root]; 840 839 for (int j = 0; j != limit; ++j) { 841 if ( !_forward[j]) _res_cap[j] += _lower[j];840 if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; 842 841 } 843 842 } 
lemon/cycle_canceling.h
r1297 r1298 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003201 05 * Copyright (C) 20032013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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 \f$O(n^2 m^2 \log n)\f$, 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 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).136 /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$. 137 137 MINIMUM_MEAN_CYCLE_CANCELING, 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 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).142 /// complexity is \f$O(n^2 m^2 \log n)\f$. 143 143 CANCEL_AND_TIGHTEN 144 144 }; … … 576 576 /// 577 577 /// This function returns the total cost of the found flow. 578 /// Its complexity is O( e).578 /// Its complexity is O(m). 579 579 /// 580 580 /// \note The return type of the function can be specified as a … … 783 783 return OPTIMAL; 784 784 } 785 785 786 786 // Check if the upper bound is greater than or equal to the lower bound 787 787 // on each forward arc. … … 960 960 buildResidualNetwork(); 961 961 while (true) { 962 962 963 963 typename HwMmc::TerminationCause hw_tc = 964 964 hw_mmc.findCycleMean(hw_iter_limit); … … 976 976 hw_mmc.findCycle(); 977 977 } 978 978 979 979 // Compute delta value 980 980 Value delta = INF;
Note: See TracChangeset
for help on using the changeset viewer.