Changeset 1241:879fcb781086 in lemon for lemon/capacity_scaling.h
 Timestamp:
 07/30/13 15:24:45 (7 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/capacity_scaling.h
r1221 r1241 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
r1240 r1241 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.