r937:1226290a9b7d
Tue, 15 Mar 2011 19:52:31
[Not Reviewed]
0 comments (0 inline)
0
1
0
50
22
| ... | ... |
@@ -232,17 +232,16 @@ |
| 232 | 232 |
void set(const Key& key, const Value& val) {
|
| 233 | 233 |
_v[StaticDigraph::id(key)] = val; |
| 234 | 234 |
} |
| 235 | 235 |
|
| 236 | 236 |
private: |
| 237 | 237 |
std::vector<Value>& _v; |
| 238 | 238 |
}; |
| 239 | 239 |
|
| 240 |
typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap; |
|
| 241 | 240 |
typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap; |
| 242 | 241 |
|
| 243 | 242 |
private: |
| 244 | 243 |
|
| 245 | 244 |
// Data related to the underlying digraph |
| 246 | 245 |
const GR &_graph; |
| 247 | 246 |
int _node_num; |
| 248 | 247 |
int _arc_num; |
| ... | ... |
@@ -283,24 +282,16 @@ |
| 283 | 282 |
int _alpha; |
| 284 | 283 |
|
| 285 | 284 |
IntVector _buckets; |
| 286 | 285 |
IntVector _bucket_next; |
| 287 | 286 |
IntVector _bucket_prev; |
| 288 | 287 |
IntVector _rank; |
| 289 | 288 |
int _max_rank; |
| 290 | 289 |
|
| 291 |
// Data for a StaticDigraph structure |
|
| 292 |
typedef std::pair<int, int> IntPair; |
|
| 293 |
StaticDigraph _sgr; |
|
| 294 |
std::vector<IntPair> _arc_vec; |
|
| 295 |
std::vector<LargeCost> _cost_vec; |
|
| 296 |
LargeCostArcMap _cost_map; |
|
| 297 |
LargeCostNodeMap _pi_map; |
|
| 298 |
|
|
| 299 | 290 |
public: |
| 300 | 291 |
|
| 301 | 292 |
/// \brief Constant for infinite upper bounds (capacities). |
| 302 | 293 |
/// |
| 303 | 294 |
/// Constant for infinite upper bounds (capacities). |
| 304 | 295 |
/// It is \c std::numeric_limits<Value>::infinity() if available, |
| 305 | 296 |
/// \c std::numeric_limits<Value>::max() otherwise. |
| 306 | 297 |
const Value INF; |
| ... | ... |
@@ -337,17 +328,16 @@ |
| 337 | 328 |
|
| 338 | 329 |
/// \brief Constructor. |
| 339 | 330 |
/// |
| 340 | 331 |
/// The constructor of the class. |
| 341 | 332 |
/// |
| 342 | 333 |
/// \param graph The digraph the algorithm runs on. |
| 343 | 334 |
CostScaling(const GR& graph) : |
| 344 | 335 |
_graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph), |
| 345 |
_cost_map(_cost_vec), _pi_map(_pi), |
|
| 346 | 336 |
INF(std::numeric_limits<Value>::has_infinity ? |
| 347 | 337 |
std::numeric_limits<Value>::infinity() : |
| 348 | 338 |
std::numeric_limits<Value>::max()) |
| 349 | 339 |
{
|
| 350 | 340 |
// Check the number types |
| 351 | 341 |
LEMON_ASSERT(std::numeric_limits<Value>::is_signed, |
| 352 | 342 |
"The flow type of CostScaling must be signed"); |
| 353 | 343 |
LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, |
| ... | ... |
@@ -614,19 +604,16 @@ |
| 614 | 604 |
_supply.resize(_res_node_num); |
| 615 | 605 |
|
| 616 | 606 |
_res_cap.resize(_res_arc_num); |
| 617 | 607 |
_cost.resize(_res_arc_num); |
| 618 | 608 |
_pi.resize(_res_node_num); |
| 619 | 609 |
_excess.resize(_res_node_num); |
| 620 | 610 |
_next_out.resize(_res_node_num); |
| 621 | 611 |
|
| 622 |
_arc_vec.reserve(_res_arc_num); |
|
| 623 |
_cost_vec.reserve(_res_arc_num); |
|
| 624 |
|
|
| 625 | 612 |
// Copy the graph |
| 626 | 613 |
int i = 0, j = 0, k = 2 * _arc_num + _node_num; |
| 627 | 614 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
| 628 | 615 |
_node_id[n] = i; |
| 629 | 616 |
} |
| 630 | 617 |
i = 0; |
| 631 | 618 |
for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
|
| 632 | 619 |
_first_out[i] = j; |
| ... | ... |
@@ -918,33 +905,74 @@ |
| 918 | 905 |
case AUGMENT: |
| 919 | 906 |
startAugment(_res_node_num - 1); |
| 920 | 907 |
break; |
| 921 | 908 |
case PARTIAL_AUGMENT: |
| 922 | 909 |
startAugment(MAX_PARTIAL_PATH_LENGTH); |
| 923 | 910 |
break; |
| 924 | 911 |
} |
| 925 | 912 |
|
| 926 |
// Compute node potentials for the original costs |
|
| 927 |
_arc_vec.clear(); |
|
| 928 |
|
|
| 913 |
// Compute node potentials (dual solution) |
|
| 914 |
for (int i = 0; i != _res_node_num; ++i) {
|
|
| 915 |
_pi[i] = static_cast<Cost>(_pi[i] / (_res_node_num * _alpha)); |
|
| 916 |
} |
|
| 917 |
bool optimal = true; |
|
| 918 |
for (int i = 0; optimal && i != _res_node_num; ++i) {
|
|
| 919 |
LargeCost pi_i = _pi[i]; |
|
| 920 |
int last_out = _first_out[i+1]; |
|
| 921 |
for (int j = _first_out[i]; j != last_out; ++j) {
|
|
| 922 |
if (_res_cap[j] > 0 && _scost[j] + pi_i - _pi[_target[j]] < 0) {
|
|
| 923 |
optimal = false; |
|
| 924 |
break; |
|
| 925 |
} |
|
| 926 |
} |
|
| 927 |
} |
|
| 928 |
|
|
| 929 |
if (!optimal) {
|
|
| 930 |
// Compute node potentials for the original costs with BellmanFord |
|
| 931 |
// (if it is necessary) |
|
| 932 |
typedef std::pair<int, int> IntPair; |
|
| 933 |
StaticDigraph sgr; |
|
| 934 |
std::vector<IntPair> arc_vec; |
|
| 935 |
std::vector<LargeCost> cost_vec; |
|
| 936 |
LargeCostArcMap cost_map(cost_vec); |
|
| 937 |
|
|
| 938 |
arc_vec.clear(); |
|
| 939 |
cost_vec.clear(); |
|
| 929 | 940 |
for (int j = 0; j != _res_arc_num; ++j) {
|
| 930 | 941 |
if (_res_cap[j] > 0) {
|
| 931 |
_arc_vec.push_back(IntPair(_source[j], _target[j])); |
|
| 932 |
_cost_vec.push_back(_scost[j]); |
|
| 942 |
int u = _source[j], v = _target[j]; |
|
| 943 |
arc_vec.push_back(IntPair(u, v)); |
|
| 944 |
cost_vec.push_back(_scost[j] + _pi[u] - _pi[v]); |
|
| 933 | 945 |
} |
| 934 | 946 |
} |
| 935 |
|
|
| 947 |
sgr.build(_res_node_num, arc_vec.begin(), arc_vec.end()); |
|
| 936 | 948 |
|
| 937 |
typename BellmanFord<StaticDigraph, LargeCostArcMap> |
|
| 938 |
::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map); |
|
| 939 |
|
|
| 949 |
typename BellmanFord<StaticDigraph, LargeCostArcMap>::Create |
|
| 950 |
bf(sgr, cost_map); |
|
| 940 | 951 |
bf.init(0); |
| 941 | 952 |
bf.start(); |
| 942 | 953 |
|
| 954 |
for (int i = 0; i != _res_node_num; ++i) {
|
|
| 955 |
_pi[i] += bf.dist(sgr.node(i)); |
|
| 956 |
} |
|
| 957 |
} |
|
| 958 |
|
|
| 959 |
// Shift potentials to meet the requirements of the GEQ type |
|
| 960 |
// optimality conditions |
|
| 961 |
LargeCost max_pot = _pi[_root]; |
|
| 962 |
for (int i = 0; i != _res_node_num; ++i) {
|
|
| 963 |
if (_pi[i] > max_pot) max_pot = _pi[i]; |
|
| 964 |
} |
|
| 965 |
if (max_pot != 0) {
|
|
| 966 |
for (int i = 0; i != _res_node_num; ++i) {
|
|
| 967 |
_pi[i] -= max_pot; |
|
| 968 |
} |
|
| 969 |
} |
|
| 970 |
|
|
| 943 | 971 |
// Handle non-zero lower bounds |
| 944 | 972 |
if (_have_lower) {
|
| 945 | 973 |
int limit = _first_out[_root]; |
| 946 | 974 |
for (int j = 0; j != limit; ++j) {
|
| 947 | 975 |
if (!_forward[j]) _res_cap[j] += _lower[j]; |
| 948 | 976 |
} |
| 949 | 977 |
} |
| 950 | 978 |
} |
0 comments (0 inline)