equal
deleted
inserted
replaced
254 int _res_node_num; |
254 int _res_node_num; |
255 int _res_arc_num; |
255 int _res_arc_num; |
256 int _root; |
256 int _root; |
257 |
257 |
258 // Parameters of the problem |
258 // Parameters of the problem |
259 bool _have_lower; |
259 bool _has_lower; |
260 Value _sum_supply; |
260 Value _sum_supply; |
261 int _sup_node_num; |
261 int _sup_node_num; |
262 |
262 |
263 // Data structures for storing the digraph |
263 // Data structures for storing the digraph |
264 IntNodeMap _node_id; |
264 IntNodeMap _node_id; |
370 /// of the algorithm. |
370 /// of the algorithm. |
371 /// |
371 /// |
372 /// \return <tt>(*this)</tt> |
372 /// \return <tt>(*this)</tt> |
373 template <typename LowerMap> |
373 template <typename LowerMap> |
374 CostScaling& lowerMap(const LowerMap& map) { |
374 CostScaling& lowerMap(const LowerMap& map) { |
375 _have_lower = true; |
375 _has_lower = true; |
376 for (ArcIt a(_graph); a != INVALID; ++a) { |
376 for (ArcIt a(_graph); a != INVALID; ++a) { |
377 _lower[_arc_idf[a]] = map[a]; |
377 _lower[_arc_idf[a]] = map[a]; |
378 _lower[_arc_idb[a]] = map[a]; |
|
379 } |
378 } |
380 return *this; |
379 return *this; |
381 } |
380 } |
382 |
381 |
383 /// \brief Set the upper bounds (capacities) on the arcs. |
382 /// \brief Set the upper bounds (capacities) on the arcs. |
566 _lower[j] = 0; |
565 _lower[j] = 0; |
567 _upper[j] = INF; |
566 _upper[j] = INF; |
568 _scost[j] = 0; |
567 _scost[j] = 0; |
569 _scost[_reverse[j]] = 0; |
568 _scost[_reverse[j]] = 0; |
570 } |
569 } |
571 _have_lower = false; |
570 _has_lower = false; |
572 return *this; |
571 return *this; |
573 } |
572 } |
574 |
573 |
575 /// \brief Reset the internal data structures and all the parameters |
574 /// \brief Reset the internal data structures and all the parameters |
576 /// that have been given before. |
575 /// that have been given before. |
778 } |
777 } |
779 |
778 |
780 // Remove infinite upper bounds and check negative arcs |
779 // Remove infinite upper bounds and check negative arcs |
781 const Value MAX = std::numeric_limits<Value>::max(); |
780 const Value MAX = std::numeric_limits<Value>::max(); |
782 int last_out; |
781 int last_out; |
783 if (_have_lower) { |
782 if (_has_lower) { |
784 for (int i = 0; i != _root; ++i) { |
783 for (int i = 0; i != _root; ++i) { |
785 last_out = _first_out[i+1]; |
784 last_out = _first_out[i+1]; |
786 for (int j = _first_out[i]; j != last_out; ++j) { |
785 for (int j = _first_out[i]; j != last_out; ++j) { |
787 if (_forward[j]) { |
786 if (_forward[j]) { |
788 Value c = _scost[j] < 0 ? _upper[j] : _lower[j]; |
787 Value c = _scost[j] < 0 ? _upper[j] : _lower[j]; |
835 ValueArcMap cap(_graph), flow(_graph); |
834 ValueArcMap cap(_graph), flow(_graph); |
836 ValueNodeMap sup(_graph); |
835 ValueNodeMap sup(_graph); |
837 for (NodeIt n(_graph); n != INVALID; ++n) { |
836 for (NodeIt n(_graph); n != INVALID; ++n) { |
838 sup[n] = _supply[_node_id[n]]; |
837 sup[n] = _supply[_node_id[n]]; |
839 } |
838 } |
840 if (_have_lower) { |
839 if (_has_lower) { |
841 for (ArcIt a(_graph); a != INVALID; ++a) { |
840 for (ArcIt a(_graph); a != INVALID; ++a) { |
842 int j = _arc_idf[a]; |
841 int j = _arc_idf[a]; |
843 Value c = _lower[j]; |
842 Value c = _lower[j]; |
844 cap[a] = _upper[j] - c; |
843 cap[a] = _upper[j] - c; |
845 sup[_graph.source(a)] -= c; |
844 sup[_graph.source(a)] -= c; |
905 _rank.resize(_res_node_num + 1); |
904 _rank.resize(_res_node_num + 1); |
906 |
905 |
907 return OPTIMAL; |
906 return OPTIMAL; |
908 } |
907 } |
909 |
908 |
910 // Check if the upper bound is greater or equal to the lower bound |
909 // Check if the upper bound is greater than or equal to the lower bound |
911 // on each arc. |
910 // on each forward arc. |
912 bool checkBoundMaps() { |
911 bool checkBoundMaps() { |
913 for (int j = 0; j != _res_arc_num; ++j) { |
912 for (int j = 0; j != _res_arc_num; ++j) { |
914 if (_upper[j] < _lower[j]) return false; |
913 if (_forward[j] && _upper[j] < _lower[j]) return false; |
915 } |
914 } |
916 return true; |
915 return true; |
917 } |
916 } |
918 |
917 |
919 // Execute the algorithm and transform the results |
918 // Execute the algorithm and transform the results |
989 _pi[i] -= max_pot; |
988 _pi[i] -= max_pot; |
990 } |
989 } |
991 } |
990 } |
992 |
991 |
993 // Handle non-zero lower bounds |
992 // Handle non-zero lower bounds |
994 if (_have_lower) { |
993 if (_has_lower) { |
995 int limit = _first_out[_root]; |
994 int limit = _first_out[_root]; |
996 for (int j = 0; j != limit; ++j) { |
995 for (int j = 0; j != limit; ++j) { |
997 if (!_forward[j]) _res_cap[j] += _lower[j]; |
996 if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; |
998 } |
997 } |
999 } |
998 } |
1000 } |
999 } |
1001 |
1000 |
1002 // Initialize a cost scaling phase |
1001 // Initialize a cost scaling phase |