Changeset 1241:879fcb781086 in lemon for lemon/cost_scaling.h
- Timestamp:
- 07/30/13 15:24:45 (11 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/cost_scaling.h
r1221 r1241 764 764 if (_sum_supply > 0) return INFEASIBLE; 765 765 766 // Check lower and upper bounds 767 LEMON_DEBUG(checkBoundMaps(), 768 "Upper bounds must be greater or equal to the lower bounds"); 769 766 770 767 771 // Initialize vectors … … 899 903 900 904 return OPTIMAL; 905 } 906 907 // Check if the upper bound is greater or equal to the lower bound 908 // on each arc. 909 bool checkBoundMaps() { 910 for (int j = 0; j != _res_arc_num; ++j) { 911 if (_upper[j] < _lower[j]) return false; 912 } 913 return true; 901 914 } 902 915 -
lemon/cost_scaling.h
r1240 r1241 92 92 /// \ref CostScaling implements a cost scaling algorithm that performs 93 93 /// push/augment and relabel operations for finding a \ref min_cost_flow 94 /// "minimum cost flow" \ ref amo93networkflows, \refgoldberg90approximation,95 /// \ ref goldberg97efficient, \refbunnagel98efficient.94 /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation, 95 /// \cite goldberg97efficient, \cite bunnagel98efficient. 96 96 /// It is a highly efficient primal-dual solution method, which 97 97 /// can be viewed as the generalization of the \ref Preflow 98 98 /// "preflow push-relabel" algorithm for the maximum flow problem. 99 /// It is a polynomial algorithm, its running time complexity is 100 /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost. 99 101 /// 100 102 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest … … 1283 1285 _buckets[r] = _bucket_next[u]; 1284 1286 1285 // Search the incom ming arcs of u1287 // Search the incoming arcs of u 1286 1288 LargeCost pi_u = _pi[u]; 1287 1289 int last_out = _first_out[u+1];
Note: See TracChangeset
for help on using the changeset viewer.