Changeset 411:01c443515ad2 in lemon1.2
 Timestamp:
 12/02/08 08:21:47 (16 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/hao_orlin.h
r409 r411 226 226 } 227 227 228 int bucket_num = 1; 228 int bucket_num = 0; 229 std::vector<Node> queue(_node_num); 230 int qfirst = 0, qlast = 0, qsep = 0; 229 231 230 232 { … … 232 234 233 235 reached.set(_source, true); 234 235 236 bool first_set = true; 236 237 … … 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 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.push_back(t); 241 242 queue[qlast++] = t; 252 243 reached.set(t, true); 253 244 254 while (!queue.empty()) { 255 _sets.front().push_front(bucket_num); 256 _dormant[bucket_num] = !first_set; 257 _first[bucket_num] = _last[bucket_num] = INVALID; 258 259 std::vector<Node> nqueue; 260 for (int i = 0; i < int(queue.size()); ++i) { 261 Node n = queue[i]; 262 for (InArcIt a(_graph, n); a != INVALID; ++a) { 263 Node u = _graph.source(a); 264 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 265 reached.set(u, true); 266 addItem(u, bucket_num); 267 nqueue.push_back(u); 268 } 269 } 270 } 271 queue.swap(nqueue); 272 ++bucket_num; 273 } 274 _sets.front().pop_front(); 275 bucket_num; 245 while (qfirst != qlast) { 246 if (qsep == qfirst) { 247 ++bucket_num; 248 _sets.front().push_front(bucket_num); 249 _dormant[bucket_num] = !first_set; 250 _first[bucket_num] = _last[bucket_num] = INVALID; 251 qsep = qlast; 252 } 253 254 Node n = queue[qfirst++]; 255 addItem(n, bucket_num); 256 257 for (InArcIt a(_graph, n); a != INVALID; ++a) { 258 Node u = _graph.source(a); 259 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 260 reached.set(u, true); 261 queue[qlast++] = u; 262 } 263 } 264 } 276 265 first_set = false; 277 266 } 278 267 268 ++bucket_num; 279 269 _bucket>set(_source, 0); 280 270 _dormant[0] = true; … … 535 525 } 536 526 537 int bucket_num = 1; 527 int bucket_num = 0; 528 std::vector<Node> queue(_node_num); 529 int qfirst = 0, qlast = 0, qsep = 0; 538 530 539 531 { … … 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 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.push_back(t); 541 542 queue[qlast++] = t; 561 543 reached.set(t, true); 562 544 563 while (!queue.empty()) { 564 _sets.front().push_front(bucket_num); 565 _dormant[bucket_num] = !first_set; 566 _first[bucket_num] = _last[bucket_num] = INVALID; 567 568 std::vector<Node> nqueue; 569 for (int i = 0; i < int(queue.size()); ++i) { 570 Node n = queue[i]; 571 for (OutArcIt a(_graph, n); a != INVALID; ++a) { 572 Node u = _graph.target(a); 573 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 574 reached.set(u, true); 575 addItem(u, bucket_num); 576 nqueue.push_back(u); 577 } 578 } 579 } 580 queue.swap(nqueue); 581 ++bucket_num; 582 } 583 _sets.front().pop_front(); 584 bucket_num; 545 while (qfirst != qlast) { 546 if (qsep == qfirst) { 547 ++bucket_num; 548 _sets.front().push_front(bucket_num); 549 _dormant[bucket_num] = !first_set; 550 _first[bucket_num] = _last[bucket_num] = INVALID; 551 qsep = qlast; 552 } 553 554 Node n = queue[qfirst++]; 555 addItem(n, bucket_num); 556 557 for (OutArcIt a(_graph, n); a != INVALID; ++a) { 558 Node u = _graph.target(a); 559 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 560 reached.set(u, true); 561 queue[qlast++] = u; 562 } 563 } 564 } 585 565 first_set = false; 586 566 } 587 567 568 ++bucket_num; 588 569 _bucket>set(_source, 0); 589 570 _dormant[0] = true; … … 865 846 _node_num = countNodes(_graph); 866 847 867 _first.resize(_node_num + 1);868 _last.resize(_node_num + 1);869 870 _dormant.resize(_node_num + 1);848 _first.resize(_node_num); 849 _last.resize(_node_num); 850 851 _dormant.resize(_node_num); 871 852 872 853 if (!_flow) {
Note: See TracChangeset
for help on using the changeset viewer.