Changeset 1104:a78e5b779b69 in lemon-main for lemon/capacity_scaling.h
- Timestamp:
- 10/17/13 15:08:41 (11 years ago)
- Branch:
- default
- Parents:
- 1101:15e233f588da (diff), 1103: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/capacity_scaling.h
r1092 r1104 164 164 165 165 // Parameters of the problem 166 bool _ha ve_lower;166 bool _has_lower; 167 167 Value _sum_supply; 168 168 … … 357 357 template <typename LowerMap> 358 358 CapacityScaling& lowerMap(const LowerMap& map) { 359 _ha ve_lower = true;359 _has_lower = true; 360 360 for (ArcIt a(_graph); a != INVALID; ++a) { 361 361 _lower[_arc_idf[a]] = map[a]; 362 _lower[_arc_idb[a]] = map[a];363 362 } 364 363 return *this; … … 544 543 _cost[j] = _forward[j] ? 1 : -1; 545 544 } 546 _ha ve_lower = false;545 _has_lower = false; 547 546 return *this; 548 547 } … … 755 754 const Value MAX = std::numeric_limits<Value>::max(); 756 755 int last_out; 757 if (_ha ve_lower) {756 if (_has_lower) { 758 757 for (int i = 0; i != _root; ++i) { 759 758 last_out = _first_out[i+1]; … … 840 839 } 841 840 842 // Check if the upper bound is greater or equal to the lower bound843 // on each arc.841 // Check if the upper bound is greater than or equal to the lower bound 842 // on each forward arc. 844 843 bool checkBoundMaps() { 845 844 for (int j = 0; j != _res_arc_num; ++j) { 846 if (_ upper[j] < _lower[j]) return false;845 if (_forward[j] && _upper[j] < _lower[j]) return false; 847 846 } 848 847 return true; … … 858 857 859 858 // Handle non-zero lower bounds 860 if (_ha ve_lower) {859 if (_has_lower) { 861 860 int limit = _first_out[_root]; 862 861 for (int j = 0; j != limit; ++j) { 863 if ( !_forward[j]) _res_cap[j] += _lower[j];862 if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; 864 863 } 865 864 } -
lemon/capacity_scaling.h
r1103 r1104 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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(m\log U (n+m)\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 … … 117 119 typedef typename TR::Heap Heap; 118 120 119 /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm 121 /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class" 122 /// of the algorithm 120 123 typedef TR Traits; 121 124 … … 643 646 /// 644 647 /// This function returns the total cost of the found flow. 645 /// Its complexity is O( e).648 /// Its complexity is O(m). 646 649 /// 647 650 /// \note The return type of the function can be specified as a … … 835 838 return OPTIMAL; 836 839 } 837 840 838 841 // Check if the upper bound is greater than or equal to the lower bound 839 842 // on each forward arc.
Note: See TracChangeset
for help on using the changeset viewer.