Changeset 581:aa1804409f29 in lemon1.2 for lemon/hao_orlin.h
 Timestamp:
 04/14/09 10:35:38 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/hao_orlin.h
r559 r581 162 162 163 163 void activate(const Node& i) { 164 _active>set(i, true);164 (*_active)[i] = true; 165 165 166 166 int bucket = (*_bucket)[i]; … … 168 168 if ((*_prev)[i] == INVALID  (*_active)[(*_prev)[i]]) return; 169 169 //unlace 170 _next>set((*_prev)[i], (*_next)[i]);170 (*_next)[(*_prev)[i]] = (*_next)[i]; 171 171 if ((*_next)[i] != INVALID) { 172 _prev>set((*_next)[i], (*_prev)[i]);172 (*_prev)[(*_next)[i]] = (*_prev)[i]; 173 173 } else { 174 174 _last[bucket] = (*_prev)[i]; 175 175 } 176 176 //lace 177 _next>set(i, _first[bucket]);178 _prev>set(_first[bucket], i);179 _prev>set(i, INVALID);177 (*_next)[i] = _first[bucket]; 178 (*_prev)[_first[bucket]] = i; 179 (*_prev)[i] = INVALID; 180 180 _first[bucket] = i; 181 181 } 182 182 183 183 void deactivate(const Node& i) { 184 _active>set(i, false);184 (*_active)[i] = false; 185 185 int bucket = (*_bucket)[i]; 186 186 … … 188 188 189 189 //unlace 190 _prev>set((*_next)[i], (*_prev)[i]);190 (*_prev)[(*_next)[i]] = (*_prev)[i]; 191 191 if ((*_prev)[i] != INVALID) { 192 _next>set((*_prev)[i], (*_next)[i]);192 (*_next)[(*_prev)[i]] = (*_next)[i]; 193 193 } else { 194 194 _first[bucket] = (*_next)[i]; 195 195 } 196 196 //lace 197 _prev>set(i, _last[bucket]);198 _next>set(_last[bucket], i);199 _next>set(i, INVALID);197 (*_prev)[i] = _last[bucket]; 198 (*_next)[_last[bucket]] = i; 199 (*_next)[i] = INVALID; 200 200 _last[bucket] = i; 201 201 } … … 204 204 (*_bucket)[i] = bucket; 205 205 if (_last[bucket] != INVALID) { 206 _prev>set(i, _last[bucket]);207 _next>set(_last[bucket], i);208 _next>set(i, INVALID);206 (*_prev)[i] = _last[bucket]; 207 (*_next)[_last[bucket]] = i; 208 (*_next)[i] = INVALID; 209 209 _last[bucket] = i; 210 210 } else { 211 _prev>set(i, INVALID);211 (*_prev)[i] = INVALID; 212 212 _first[bucket] = i; 213 _next>set(i, INVALID);213 (*_next)[i] = INVALID; 214 214 _last[bucket] = i; 215 215 } … … 219 219 220 220 for (NodeIt n(_graph); n != INVALID; ++n) { 221 _excess>set(n, 0);221 (*_excess)[n] = 0; 222 222 } 223 223 224 224 for (ArcIt a(_graph); a != INVALID; ++a) { 225 _flow>set(a, 0);225 (*_flow)[a] = 0; 226 226 } 227 227 … … 233 233 typename Digraph::template NodeMap<bool> reached(_graph, false); 234 234 235 reached .set(_source, true);235 reached[_source] = true; 236 236 bool first_set = true; 237 237 … … 241 241 242 242 queue[qlast++] = t; 243 reached .set(t, true);243 reached[t] = true; 244 244 245 245 while (qfirst != qlast) { … … 258 258 Node u = _graph.source(a); 259 259 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 260 reached .set(u, true);260 reached[u] = true; 261 261 queue[qlast++] = u; 262 262 } … … 267 267 268 268 ++bucket_num; 269 _bucket>set(_source, 0);269 (*_bucket)[_source] = 0; 270 270 _dormant[0] = true; 271 271 } 272 _source_set>set(_source, true);272 (*_source_set)[_source] = true; 273 273 274 274 Node target = _last[_sets.back().back()]; … … 277 277 if (_tolerance.positive((*_capacity)[a])) { 278 278 Node u = _graph.target(a); 279 _flow>set(a, (*_capacity)[a]);280 _excess>set(u, (*_excess)[u] + (*_capacity)[a]);279 (*_flow)[a] = (*_capacity)[a]; 280 (*_excess)[u] += (*_capacity)[a]; 281 281 if (!(*_active)[u] && u != _source) { 282 282 activate(u); … … 319 319 } 320 320 if (!_tolerance.less(rem, excess)) { 321 _flow>set(a, (*_flow)[a] + excess);322 _excess>set(v, (*_excess)[v] + excess);321 (*_flow)[a] += excess; 322 (*_excess)[v] += excess; 323 323 excess = 0; 324 324 goto no_more_push; 325 325 } else { 326 326 excess = rem; 327 _excess>set(v, (*_excess)[v] + rem);328 _flow>set(a, (*_capacity)[a]);327 (*_excess)[v] += rem; 328 (*_flow)[a] = (*_capacity)[a]; 329 329 } 330 330 } else if (next_bucket > (*_bucket)[v]) { … … 343 343 } 344 344 if (!_tolerance.less(rem, excess)) { 345 _flow>set(a, (*_flow)[a]  excess);346 _excess>set(v, (*_excess)[v] + excess);345 (*_flow)[a] = excess; 346 (*_excess)[v] += excess; 347 347 excess = 0; 348 348 goto no_more_push; 349 349 } else { 350 350 excess = rem; 351 _excess>set(v, (*_excess)[v] + rem);352 _flow>set(a, 0);351 (*_excess)[v] += rem; 352 (*_flow)[a] = 0; 353 353 } 354 354 } else if (next_bucket > (*_bucket)[v]) { … … 359 359 no_more_push: 360 360 361 _excess>set(n, excess);361 (*_excess)[n] = excess; 362 362 363 363 if (excess != 0) { … … 377 377 } else if (next_bucket == _node_num) { 378 378 _first[(*_bucket)[n]] = (*_next)[n]; 379 _prev>set((*_next)[n], INVALID);379 (*_prev)[(*_next)[n]] = INVALID; 380 380 381 381 std::list<std::list<int> >::iterator new_set = … … 383 383 384 384 new_set>push_front(bucket_num); 385 _bucket>set(n, bucket_num);385 (*_bucket)[n] = bucket_num; 386 386 _first[bucket_num] = _last[bucket_num] = n; 387 _next>set(n, INVALID);388 _prev>set(n, INVALID);387 (*_next)[n] = INVALID; 388 (*_prev)[n] = INVALID; 389 389 _dormant[bucket_num] = true; 390 390 ++bucket_num; … … 396 396 } else { 397 397 _first[*_highest] = (*_next)[n]; 398 _prev>set((*_next)[n], INVALID);398 (*_prev)[(*_next)[n]] = INVALID; 399 399 400 400 while (next_bucket != *_highest) { … … 410 410 _highest; 411 411 412 _bucket>set(n, *_highest);413 _next>set(n, _first[*_highest]);412 (*_bucket)[n] = *_highest; 413 (*_next)[n] = _first[*_highest]; 414 414 if (_first[*_highest] != INVALID) { 415 _prev>set(_first[*_highest], n);415 (*_prev)[_first[*_highest]] = n; 416 416 } else { 417 417 _last[*_highest] = n; … … 435 435 _min_cut = (*_excess)[target]; 436 436 for (NodeIt i(_graph); i != INVALID; ++i) { 437 _min_cut_map>set(i, true);437 (*_min_cut_map)[i] = true; 438 438 } 439 439 for (std::list<int>::iterator it = _sets.back().begin(); … … 441 441 Node n = _first[*it]; 442 442 while (n != INVALID) { 443 _min_cut_map>set(n, false);443 (*_min_cut_map)[n] = false; 444 444 n = (*_next)[n]; 445 445 } … … 454 454 new_target = (*_prev)[target]; 455 455 } else { 456 _prev>set((*_next)[target], (*_prev)[target]);456 (*_prev)[(*_next)[target]] = (*_prev)[target]; 457 457 new_target = (*_next)[target]; 458 458 } … … 460 460 _first[(*_bucket)[target]] = (*_next)[target]; 461 461 } else { 462 _next>set((*_prev)[target], (*_next)[target]);462 (*_next)[(*_prev)[target]] = (*_next)[target]; 463 463 } 464 464 } else { … … 476 476 } 477 477 478 _bucket>set(target, 0);479 480 _source_set>set(target, true);478 (*_bucket)[target] = 0; 479 480 (*_source_set)[target] = true; 481 481 for (OutArcIt a(_graph, target); a != INVALID; ++a) { 482 482 Value rem = (*_capacity)[a]  (*_flow)[a]; … … 486 486 activate(v); 487 487 } 488 _excess>set(v, (*_excess)[v] + rem);489 _flow>set(a, (*_capacity)[a]);488 (*_excess)[v] += rem; 489 (*_flow)[a] = (*_capacity)[a]; 490 490 } 491 491 … … 497 497 activate(v); 498 498 } 499 _excess>set(v, (*_excess)[v] + rem);500 _flow>set(a, 0);499 (*_excess)[v] += rem; 500 (*_flow)[a] = 0; 501 501 } 502 502 … … 518 518 519 519 for (NodeIt n(_graph); n != INVALID; ++n) { 520 _excess>set(n, 0);520 (*_excess)[n] = 0; 521 521 } 522 522 523 523 for (ArcIt a(_graph); a != INVALID; ++a) { 524 _flow>set(a, 0);524 (*_flow)[a] = 0; 525 525 } 526 526 … … 532 532 typename Digraph::template NodeMap<bool> reached(_graph, false); 533 533 534 reached .set(_source, true);534 reached[_source] = true; 535 535 536 536 bool first_set = true; … … 541 541 542 542 queue[qlast++] = t; 543 reached .set(t, true);543 reached[t] = true; 544 544 545 545 while (qfirst != qlast) { … … 558 558 Node u = _graph.target(a); 559 559 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { 560 reached .set(u, true);560 reached[u] = true; 561 561 queue[qlast++] = u; 562 562 } … … 567 567 568 568 ++bucket_num; 569 _bucket>set(_source, 0);569 (*_bucket)[_source] = 0; 570 570 _dormant[0] = true; 571 571 } 572 _source_set>set(_source, true);572 (*_source_set)[_source] = true; 573 573 574 574 Node target = _last[_sets.back().back()]; … … 577 577 if (_tolerance.positive((*_capacity)[a])) { 578 578 Node u = _graph.source(a); 579 _flow>set(a, (*_capacity)[a]);580 _excess>set(u, (*_excess)[u] + (*_capacity)[a]);579 (*_flow)[a] = (*_capacity)[a]; 580 (*_excess)[u] += (*_capacity)[a]; 581 581 if (!(*_active)[u] && u != _source) { 582 582 activate(u); … … 619 619 } 620 620 if (!_tolerance.less(rem, excess)) { 621 _flow>set(a, (*_flow)[a] + excess);622 _excess>set(v, (*_excess)[v] + excess);621 (*_flow)[a] += excess; 622 (*_excess)[v] += excess; 623 623 excess = 0; 624 624 goto no_more_push; 625 625 } else { 626 626 excess = rem; 627 _excess>set(v, (*_excess)[v] + rem);628 _flow>set(a, (*_capacity)[a]);627 (*_excess)[v] += rem; 628 (*_flow)[a] = (*_capacity)[a]; 629 629 } 630 630 } else if (next_bucket > (*_bucket)[v]) { … … 643 643 } 644 644 if (!_tolerance.less(rem, excess)) { 645 _flow>set(a, (*_flow)[a]  excess);646 _excess>set(v, (*_excess)[v] + excess);645 (*_flow)[a] = excess; 646 (*_excess)[v] += excess; 647 647 excess = 0; 648 648 goto no_more_push; 649 649 } else { 650 650 excess = rem; 651 _excess>set(v, (*_excess)[v] + rem);652 _flow>set(a, 0);651 (*_excess)[v] += rem; 652 (*_flow)[a] = 0; 653 653 } 654 654 } else if (next_bucket > (*_bucket)[v]) { … … 659 659 no_more_push: 660 660 661 _excess>set(n, excess);661 (*_excess)[n] = excess; 662 662 663 663 if (excess != 0) { … … 677 677 } else if (next_bucket == _node_num) { 678 678 _first[(*_bucket)[n]] = (*_next)[n]; 679 _prev>set((*_next)[n], INVALID);679 (*_prev)[(*_next)[n]] = INVALID; 680 680 681 681 std::list<std::list<int> >::iterator new_set = … … 683 683 684 684 new_set>push_front(bucket_num); 685 _bucket>set(n, bucket_num);685 (*_bucket)[n] = bucket_num; 686 686 _first[bucket_num] = _last[bucket_num] = n; 687 _next>set(n, INVALID);688 _prev>set(n, INVALID);687 (*_next)[n] = INVALID; 688 (*_prev)[n] = INVALID; 689 689 _dormant[bucket_num] = true; 690 690 ++bucket_num; … … 696 696 } else { 697 697 _first[*_highest] = (*_next)[n]; 698 _prev>set((*_next)[n], INVALID);698 (*_prev)[(*_next)[n]] = INVALID; 699 699 700 700 while (next_bucket != *_highest) { … … 709 709 _highest; 710 710 711 _bucket>set(n, *_highest);712 _next>set(n, _first[*_highest]);711 (*_bucket)[n] = *_highest; 712 (*_next)[n] = _first[*_highest]; 713 713 if (_first[*_highest] != INVALID) { 714 _prev>set(_first[*_highest], n);714 (*_prev)[_first[*_highest]] = n; 715 715 } else { 716 716 _last[*_highest] = n; … … 734 734 _min_cut = (*_excess)[target]; 735 735 for (NodeIt i(_graph); i != INVALID; ++i) { 736 _min_cut_map>set(i, false);736 (*_min_cut_map)[i] = false; 737 737 } 738 738 for (std::list<int>::iterator it = _sets.back().begin(); … … 740 740 Node n = _first[*it]; 741 741 while (n != INVALID) { 742 _min_cut_map>set(n, true);742 (*_min_cut_map)[n] = true; 743 743 n = (*_next)[n]; 744 744 } … … 753 753 new_target = (*_prev)[target]; 754 754 } else { 755 _prev>set((*_next)[target], (*_prev)[target]);755 (*_prev)[(*_next)[target]] = (*_prev)[target]; 756 756 new_target = (*_next)[target]; 757 757 } … … 759 759 _first[(*_bucket)[target]] = (*_next)[target]; 760 760 } else { 761 _next>set((*_prev)[target], (*_next)[target]);761 (*_next)[(*_prev)[target]] = (*_next)[target]; 762 762 } 763 763 } else { … … 775 775 } 776 776 777 _bucket>set(target, 0);778 779 _source_set>set(target, true);777 (*_bucket)[target] = 0; 778 779 (*_source_set)[target] = true; 780 780 for (InArcIt a(_graph, target); a != INVALID; ++a) { 781 781 Value rem = (*_capacity)[a]  (*_flow)[a]; … … 785 785 activate(v); 786 786 } 787 _excess>set(v, (*_excess)[v] + rem);788 _flow>set(a, (*_capacity)[a]);787 (*_excess)[v] += rem; 788 (*_flow)[a] = (*_capacity)[a]; 789 789 } 790 790 … … 796 796 activate(v); 797 797 } 798 _excess>set(v, (*_excess)[v] + rem);799 _flow>set(a, 0);798 (*_excess)[v] += rem; 799 (*_flow)[a] = 0; 800 800 } 801 801
Note: See TracChangeset
for help on using the changeset viewer.