r427:01c443515ad2
Tue, 02 Dec 2008 08:21:47
[Not Reviewed]
0 comments (0 inline)
0
1
0
31
50
| ... | ... |
@@ -222,63 +222,53 @@ |
| 222 | 222 |
} |
| 223 | 223 |
|
| 224 | 224 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
| 225 | 225 |
_flow->set(a, 0); |
| 226 | 226 |
} |
| 227 | 227 |
|
| 228 |
int bucket_num = |
|
| 228 |
int bucket_num = 0; |
|
| 229 |
std::vector<Node> queue(_node_num); |
|
| 230 |
int qfirst = 0, qlast = 0, qsep = 0; |
|
| 229 | 231 |
|
| 230 | 232 |
{
|
| 231 | 233 |
typename Digraph::template NodeMap<bool> reached(_graph, false); |
| 232 | 234 |
|
| 233 | 235 |
reached.set(_source, true); |
| 234 |
|
|
| 235 | 236 |
bool first_set = true; |
| 236 | 237 |
|
| 237 | 238 |
for (NodeIt t(_graph); t != INVALID; ++t) {
|
| 238 | 239 |
if (reached[t]) continue; |
| 239 | 240 |
_sets.push_front(std::list<int>()); |
| 240 |
_sets.front().push_front(bucket_num); |
|
| 241 |
_dormant[bucket_num] = !first_set; |
|
| 242 | 241 |
|
| 243 |
_bucket->set(t, bucket_num); |
|
| 244 |
_first[bucket_num] = _last[bucket_num] = t; |
|
| 245 |
_next->set(t, INVALID); |
|
| 246 |
_prev->set(t, INVALID); |
|
| 247 |
|
|
| 248 |
++bucket_num; |
|
| 249 |
|
|
| 250 |
std::vector<Node> queue; |
|
| 251 |
queue |
|
| 242 |
queue[qlast++] = t; |
|
| 252 | 243 |
reached.set(t, true); |
| 253 | 244 |
|
| 254 |
while (! |
|
| 245 |
while (qfirst != qlast) {
|
|
| 246 |
if (qsep == qfirst) {
|
|
| 247 |
++bucket_num; |
|
| 255 | 248 |
_sets.front().push_front(bucket_num); |
| 256 | 249 |
_dormant[bucket_num] = !first_set; |
| 257 | 250 |
_first[bucket_num] = _last[bucket_num] = INVALID; |
| 251 |
qsep = qlast; |
|
| 252 |
} |
|
| 258 | 253 |
|
| 259 |
std::vector<Node> nqueue; |
|
| 260 |
for (int i = 0; i < int(queue.size()); ++i) {
|
|
| 261 |
|
|
| 254 |
Node n = queue[qfirst++]; |
|
| 255 |
addItem(n, bucket_num); |
|
| 256 |
|
|
| 262 | 257 |
for (InArcIt a(_graph, n); a != INVALID; ++a) {
|
| 263 | 258 |
Node u = _graph.source(a); |
| 264 | 259 |
if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
|
| 265 | 260 |
reached.set(u, true); |
| 266 |
addItem(u, bucket_num); |
|
| 267 |
nqueue.push_back(u); |
|
| 261 |
queue[qlast++] = u; |
|
| 268 | 262 |
} |
| 269 | 263 |
} |
| 270 | 264 |
} |
| 271 |
queue.swap(nqueue); |
|
| 272 |
++bucket_num; |
|
| 273 |
} |
|
| 274 |
_sets.front().pop_front(); |
|
| 275 |
--bucket_num; |
|
| 276 | 265 |
first_set = false; |
| 277 | 266 |
} |
| 278 | 267 |
|
| 268 |
++bucket_num; |
|
| 279 | 269 |
_bucket->set(_source, 0); |
| 280 | 270 |
_dormant[0] = true; |
| 281 | 271 |
} |
| 282 | 272 |
_source_set->set(_source, true); |
| 283 | 273 |
|
| 284 | 274 |
Node target = _last[_sets.back().back()]; |
| ... | ... |
@@ -531,63 +521,54 @@ |
| 531 | 521 |
} |
| 532 | 522 |
|
| 533 | 523 |
for (ArcIt a(_graph); a != INVALID; ++a) {
|
| 534 | 524 |
_flow->set(a, 0); |
| 535 | 525 |
} |
| 536 | 526 |
|
| 537 |
int bucket_num = |
|
| 527 |
int bucket_num = 0; |
|
| 528 |
std::vector<Node> queue(_node_num); |
|
| 529 |
int qfirst = 0, qlast = 0, qsep = 0; |
|
| 538 | 530 |
|
| 539 | 531 |
{
|
| 540 | 532 |
typename Digraph::template NodeMap<bool> reached(_graph, false); |
| 541 | 533 |
|
| 542 | 534 |
reached.set(_source, true); |
| 543 | 535 |
|
| 544 | 536 |
bool first_set = true; |
| 545 | 537 |
|
| 546 | 538 |
for (NodeIt t(_graph); t != INVALID; ++t) {
|
| 547 | 539 |
if (reached[t]) continue; |
| 548 | 540 |
_sets.push_front(std::list<int>()); |
| 549 |
_sets.front().push_front(bucket_num); |
|
| 550 |
_dormant[bucket_num] = !first_set; |
|
| 551 | 541 |
|
| 552 |
_bucket->set(t, bucket_num); |
|
| 553 |
_first[bucket_num] = _last[bucket_num] = t; |
|
| 554 |
_next->set(t, INVALID); |
|
| 555 |
_prev->set(t, INVALID); |
|
| 556 |
|
|
| 557 |
++bucket_num; |
|
| 558 |
|
|
| 559 |
std::vector<Node> queue; |
|
| 560 |
queue |
|
| 542 |
queue[qlast++] = t; |
|
| 561 | 543 |
reached.set(t, true); |
| 562 | 544 |
|
| 563 |
while (! |
|
| 545 |
while (qfirst != qlast) {
|
|
| 546 |
if (qsep == qfirst) {
|
|
| 547 |
++bucket_num; |
|
| 564 | 548 |
_sets.front().push_front(bucket_num); |
| 565 | 549 |
_dormant[bucket_num] = !first_set; |
| 566 | 550 |
_first[bucket_num] = _last[bucket_num] = INVALID; |
| 551 |
qsep = qlast; |
|
| 552 |
} |
|
| 567 | 553 |
|
| 568 |
std::vector<Node> nqueue; |
|
| 569 |
for (int i = 0; i < int(queue.size()); ++i) {
|
|
| 570 |
|
|
| 554 |
Node n = queue[qfirst++]; |
|
| 555 |
addItem(n, bucket_num); |
|
| 556 |
|
|
| 571 | 557 |
for (OutArcIt a(_graph, n); a != INVALID; ++a) {
|
| 572 | 558 |
Node u = _graph.target(a); |
| 573 | 559 |
if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
|
| 574 | 560 |
reached.set(u, true); |
| 575 |
addItem(u, bucket_num); |
|
| 576 |
nqueue.push_back(u); |
|
| 561 |
queue[qlast++] = u; |
|
| 577 | 562 |
} |
| 578 | 563 |
} |
| 579 | 564 |
} |
| 580 |
queue.swap(nqueue); |
|
| 581 |
++bucket_num; |
|
| 582 |
} |
|
| 583 |
_sets.front().pop_front(); |
|
| 584 |
--bucket_num; |
|
| 585 | 565 |
first_set = false; |
| 586 | 566 |
} |
| 587 | 567 |
|
| 568 |
++bucket_num; |
|
| 588 | 569 |
_bucket->set(_source, 0); |
| 589 | 570 |
_dormant[0] = true; |
| 590 | 571 |
} |
| 591 | 572 |
_source_set->set(_source, true); |
| 592 | 573 |
|
| 593 | 574 |
Node target = _last[_sets.back().back()]; |
| ... | ... |
@@ -861,16 +842,16 @@ |
| 861 | 842 |
/// algorithm's source. |
| 862 | 843 |
void init(const Node& source) {
|
| 863 | 844 |
_source = source; |
| 864 | 845 |
|
| 865 | 846 |
_node_num = countNodes(_graph); |
| 866 | 847 |
|
| 867 |
_first.resize(_node_num + 1); |
|
| 868 |
_last.resize(_node_num + 1); |
|
| 848 |
_first.resize(_node_num); |
|
| 849 |
_last.resize(_node_num); |
|
| 869 | 850 |
|
| 870 |
_dormant.resize(_node_num |
|
| 851 |
_dormant.resize(_node_num); |
|
| 871 | 852 |
|
| 872 | 853 |
if (!_flow) {
|
| 873 | 854 |
_flow = new FlowMap(_graph); |
| 874 | 855 |
} |
| 875 | 856 |
if (!_next) {
|
| 876 | 857 |
_next = new typename Digraph::template NodeMap<Node>(_graph); |
0 comments (0 inline)