r937:1226290a9b7d
Tue, 15 Mar 2011 19:52:31
[Not Reviewed]
0 comments (0 inline)
0
1
0
50
22
| ... | ... |
@@ -228,25 +228,24 @@ |
| 228 | 228 |
Value& operator[](const Key& key) {
|
| 229 | 229 |
return _v[StaticDigraph::id(key)]; |
| 230 | 230 |
} |
| 231 | 231 |
|
| 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; |
| 249 | 248 |
int _res_node_num; |
| 250 | 249 |
int _res_arc_num; |
| 251 | 250 |
int _root; |
| 252 | 251 |
|
| ... | ... |
@@ -279,32 +278,24 @@ |
| 279 | 278 |
std::deque<int> _active_nodes; |
| 280 | 279 |
|
| 281 | 280 |
// Data for scaling |
| 282 | 281 |
LargeCost _epsilon; |
| 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; |
| 307 | 298 |
|
| 308 | 299 |
public: |
| 309 | 300 |
|
| 310 | 301 |
/// \name Named Template Parameters |
| ... | ... |
@@ -333,25 +324,24 @@ |
| 333 | 324 |
|
| 334 | 325 |
CostScaling() {}
|
| 335 | 326 |
|
| 336 | 327 |
public: |
| 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, |
| 354 | 344 |
"The cost type of CostScaling must be signed"); |
| 355 | 345 |
|
| 356 | 346 |
// Reset data structures |
| 357 | 347 |
reset(); |
| ... | ... |
@@ -610,27 +600,24 @@ |
| 610 | 600 |
|
| 611 | 601 |
_lower.resize(_res_arc_num); |
| 612 | 602 |
_upper.resize(_res_arc_num); |
| 613 | 603 |
_scost.resize(_res_arc_num); |
| 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; |
| 633 | 620 |
for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
|
| 634 | 621 |
_arc_idf[a] = j; |
| 635 | 622 |
_forward[j] = true; |
| 636 | 623 |
_source[j] = i; |
| ... | ... |
@@ -914,41 +901,82 @@ |
| 914 | 901 |
switch (method) {
|
| 915 | 902 |
case PUSH: |
| 916 | 903 |
startPush(); |
| 917 | 904 |
break; |
| 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 |
} |
| 951 | 979 |
|
| 952 | 980 |
// Initialize a cost scaling phase |
| 953 | 981 |
void initPhase() {
|
| 954 | 982 |
// Saturate arcs not satisfying the optimality condition |
0 comments (0 inline)