Changeset 1071:879fcb781086 in lemon-main for lemon/capacity_scaling.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/capacity_scaling.h
r1053 r1071 740 740 if (_sum_supply > 0) return INFEASIBLE; 741 741 742 // Check lower and upper bounds 743 LEMON_DEBUG(checkBoundMaps(), 744 "Upper bounds must be greater or equal to the lower bounds"); 745 746 742 747 // Initialize vectors 743 748 for (int i = 0; i != _root; ++i) { … … 832 837 833 838 return OPTIMAL; 839 } 840 841 // Check if the upper bound is greater or equal to the lower bound 842 // on each arc. 843 bool checkBoundMaps() { 844 for (int j = 0; j != _res_arc_num; ++j) { 845 if (_upper[j] < _lower[j]) return false; 846 } 847 return true; 834 848 } 835 849 -
lemon/capacity_scaling.h
r1070 r1071 67 67 /// \ref CapacityScaling implements the capacity scaling version 68 68 /// of the successive shortest path algorithm for finding a 69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, 70 /// \ref edmondskarp72theoretical. It is an efficient dual 71 /// solution method. 69 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, 70 /// \cite edmondskarp72theoretical. It is an efficient dual 71 /// solution method, which runs in polynomial time 72 /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum 73 /// of node supply and arc capacity values. 72 74 /// 73 75 /// This algorithm is typically slower than \ref CostScaling and
Note: See TracChangeset
for help on using the changeset viewer.