equal
deleted
inserted
replaced
161 int _arc_num; |
161 int _arc_num; |
162 int _res_arc_num; |
162 int _res_arc_num; |
163 int _root; |
163 int _root; |
164 |
164 |
165 // Parameters of the problem |
165 // Parameters of the problem |
166 bool _have_lower; |
166 bool _has_lower; |
167 Value _sum_supply; |
167 Value _sum_supply; |
168 |
168 |
169 // Data structures for storing the digraph |
169 // Data structures for storing the digraph |
170 IntNodeMap _node_id; |
170 IntNodeMap _node_id; |
171 IntArcMap _arc_idf; |
171 IntArcMap _arc_idf; |
354 /// of the algorithm. |
354 /// of the algorithm. |
355 /// |
355 /// |
356 /// \return <tt>(*this)</tt> |
356 /// \return <tt>(*this)</tt> |
357 template <typename LowerMap> |
357 template <typename LowerMap> |
358 CapacityScaling& lowerMap(const LowerMap& map) { |
358 CapacityScaling& lowerMap(const LowerMap& map) { |
359 _have_lower = true; |
359 _has_lower = true; |
360 for (ArcIt a(_graph); a != INVALID; ++a) { |
360 for (ArcIt a(_graph); a != INVALID; ++a) { |
361 _lower[_arc_idf[a]] = map[a]; |
361 _lower[_arc_idf[a]] = map[a]; |
362 _lower[_arc_idb[a]] = map[a]; |
|
363 } |
362 } |
364 return *this; |
363 return *this; |
365 } |
364 } |
366 |
365 |
367 /// \brief Set the upper bounds (capacities) on the arcs. |
366 /// \brief Set the upper bounds (capacities) on the arcs. |
541 for (int j = 0; j != _res_arc_num; ++j) { |
540 for (int j = 0; j != _res_arc_num; ++j) { |
542 _lower[j] = 0; |
541 _lower[j] = 0; |
543 _upper[j] = INF; |
542 _upper[j] = INF; |
544 _cost[j] = _forward[j] ? 1 : -1; |
543 _cost[j] = _forward[j] ? 1 : -1; |
545 } |
544 } |
546 _have_lower = false; |
545 _has_lower = false; |
547 return *this; |
546 return *this; |
548 } |
547 } |
549 |
548 |
550 /// \brief Reset the internal data structures and all the parameters |
549 /// \brief Reset the internal data structures and all the parameters |
551 /// that have been given before. |
550 /// that have been given before. |
752 } |
751 } |
753 |
752 |
754 // Remove non-zero lower bounds |
753 // Remove non-zero lower bounds |
755 const Value MAX = std::numeric_limits<Value>::max(); |
754 const Value MAX = std::numeric_limits<Value>::max(); |
756 int last_out; |
755 int last_out; |
757 if (_have_lower) { |
756 if (_has_lower) { |
758 for (int i = 0; i != _root; ++i) { |
757 for (int i = 0; i != _root; ++i) { |
759 last_out = _first_out[i+1]; |
758 last_out = _first_out[i+1]; |
760 for (int j = _first_out[i]; j != last_out; ++j) { |
759 for (int j = _first_out[i]; j != last_out; ++j) { |
761 if (_forward[j]) { |
760 if (_forward[j]) { |
762 Value c = _lower[j]; |
761 Value c = _lower[j]; |
837 } |
836 } |
838 |
837 |
839 return OPTIMAL; |
838 return OPTIMAL; |
840 } |
839 } |
841 |
840 |
842 // Check if the upper bound is greater or equal to the lower bound |
841 // Check if the upper bound is greater than or equal to the lower bound |
843 // on each arc. |
842 // on each forward arc. |
844 bool checkBoundMaps() { |
843 bool checkBoundMaps() { |
845 for (int j = 0; j != _res_arc_num; ++j) { |
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 return true; |
847 return true; |
849 } |
848 } |
850 |
849 |
851 ProblemType start() { |
850 ProblemType start() { |
855 pt = startWithScaling(); |
854 pt = startWithScaling(); |
856 else |
855 else |
857 pt = startWithoutScaling(); |
856 pt = startWithoutScaling(); |
858 |
857 |
859 // Handle non-zero lower bounds |
858 // Handle non-zero lower bounds |
860 if (_have_lower) { |
859 if (_has_lower) { |
861 int limit = _first_out[_root]; |
860 int limit = _first_out[_root]; |
862 for (int j = 0; j != limit; ++j) { |
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 } |
866 |
865 |
867 // Shift potentials if necessary |
866 // Shift potentials if necessary |
868 Cost pr = _pi[_root]; |
867 Cost pr = _pi[_root]; |