r427:01c443515ad2
Tue, 02 Dec 2008 08:21:47
[Not Reviewed]
0 comments (0 inline)
0
1
0
47
66
| ... | ... |
@@ -180,147 +180,137 @@ |
| 180 | 180 |
_first[bucket] = i; |
| 181 | 181 |
} |
| 182 | 182 |
|
| 183 | 183 |
void deactivate(const Node& i) {
|
| 184 | 184 |
_active->set(i, false); |
| 185 | 185 |
int bucket = (*_bucket)[i]; |
| 186 | 186 |
|
| 187 | 187 |
if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; |
| 188 | 188 |
|
| 189 | 189 |
//unlace |
| 190 | 190 |
_prev->set((*_next)[i], (*_prev)[i]); |
| 191 | 191 |
if ((*_prev)[i] != INVALID) {
|
| 192 | 192 |
_next->set((*_prev)[i], (*_next)[i]); |
| 193 | 193 |
} else {
|
| 194 | 194 |
_first[bucket] = (*_next)[i]; |
| 195 | 195 |
} |
| 196 | 196 |
//lace |
| 197 | 197 |
_prev->set(i, _last[bucket]); |
| 198 | 198 |
_next->set(_last[bucket], i); |
| 199 | 199 |
_next->set(i, INVALID); |
| 200 | 200 |
_last[bucket] = i; |
| 201 | 201 |
} |
| 202 | 202 |
|
| 203 | 203 |
void addItem(const Node& i, int bucket) {
|
| 204 | 204 |
(*_bucket)[i] = bucket; |
| 205 | 205 |
if (_last[bucket] != INVALID) {
|
| 206 | 206 |
_prev->set(i, _last[bucket]); |
| 207 | 207 |
_next->set(_last[bucket], i); |
| 208 | 208 |
_next->set(i, INVALID); |
| 209 | 209 |
_last[bucket] = i; |
| 210 | 210 |
} else {
|
| 211 | 211 |
_prev->set(i, INVALID); |
| 212 | 212 |
_first[bucket] = i; |
| 213 | 213 |
_next->set(i, INVALID); |
| 214 | 214 |
_last[bucket] = i; |
| 215 | 215 |
} |
| 216 | 216 |
} |
| 217 | 217 |
|
| 218 | 218 |
void findMinCutOut() {
|
| 219 | 219 |
|
| 220 | 220 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 221 | 221 |
_excess->set(n, 0); |
| 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 |
|
|
| 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; |
|
| 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 |
} |
|
| 258 | 253 |
|
| 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 |
} |
|
| 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; |
|
| 269 | 262 |
} |
| 270 | 263 |
} |
| 271 |
queue.swap(nqueue); |
|
| 272 |
++bucket_num; |
|
| 273 | 264 |
} |
| 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()]; |
| 285 | 275 |
{
|
| 286 | 276 |
for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
|
| 287 | 277 |
if (_tolerance.positive((*_capacity)[a])) {
|
| 288 | 278 |
Node u = _graph.target(a); |
| 289 | 279 |
_flow->set(a, (*_capacity)[a]); |
| 290 | 280 |
_excess->set(u, (*_excess)[u] + (*_capacity)[a]); |
| 291 | 281 |
if (!(*_active)[u] && u != _source) {
|
| 292 | 282 |
activate(u); |
| 293 | 283 |
} |
| 294 | 284 |
} |
| 295 | 285 |
} |
| 296 | 286 |
|
| 297 | 287 |
if ((*_active)[target]) {
|
| 298 | 288 |
deactivate(target); |
| 299 | 289 |
} |
| 300 | 290 |
|
| 301 | 291 |
_highest = _sets.back().begin(); |
| 302 | 292 |
while (_highest != _sets.back().end() && |
| 303 | 293 |
!(*_active)[_first[*_highest]]) {
|
| 304 | 294 |
++_highest; |
| 305 | 295 |
} |
| 306 | 296 |
} |
| 307 | 297 |
|
| 308 | 298 |
while (true) {
|
| 309 | 299 |
while (_highest != _sets.back().end()) {
|
| 310 | 300 |
Node n = _first[*_highest]; |
| 311 | 301 |
Value excess = (*_excess)[n]; |
| 312 | 302 |
int next_bucket = _node_num; |
| 313 | 303 |
|
| 314 | 304 |
int under_bucket; |
| 315 | 305 |
if (++std::list<int>::iterator(_highest) == _sets.back().end()) {
|
| 316 | 306 |
under_bucket = -1; |
| 317 | 307 |
} else {
|
| 318 | 308 |
under_bucket = *(++std::list<int>::iterator(_highest)); |
| 319 | 309 |
} |
| 320 | 310 |
|
| 321 | 311 |
for (OutArcIt a(_graph, n); a != INVALID; ++a) {
|
| 322 | 312 |
Node v = _graph.target(a); |
| 323 | 313 |
if (_dormant[(*_bucket)[v]]) continue; |
| 324 | 314 |
Value rem = (*_capacity)[a] - (*_flow)[a]; |
| 325 | 315 |
if (!_tolerance.positive(rem)) continue; |
| 326 | 316 |
if ((*_bucket)[v] == under_bucket) {
|
| ... | ... |
@@ -489,147 +479,138 @@ |
| 489 | 479 |
|
| 490 | 480 |
_source_set->set(target, true); |
| 491 | 481 |
for (OutArcIt a(_graph, target); a != INVALID; ++a) {
|
| 492 | 482 |
Value rem = (*_capacity)[a] - (*_flow)[a]; |
| 493 | 483 |
if (!_tolerance.positive(rem)) continue; |
| 494 | 484 |
Node v = _graph.target(a); |
| 495 | 485 |
if (!(*_active)[v] && !(*_source_set)[v]) {
|
| 496 | 486 |
activate(v); |
| 497 | 487 |
} |
| 498 | 488 |
_excess->set(v, (*_excess)[v] + rem); |
| 499 | 489 |
_flow->set(a, (*_capacity)[a]); |
| 500 | 490 |
} |
| 501 | 491 |
|
| 502 | 492 |
for (InArcIt a(_graph, target); a != INVALID; ++a) {
|
| 503 | 493 |
Value rem = (*_flow)[a]; |
| 504 | 494 |
if (!_tolerance.positive(rem)) continue; |
| 505 | 495 |
Node v = _graph.source(a); |
| 506 | 496 |
if (!(*_active)[v] && !(*_source_set)[v]) {
|
| 507 | 497 |
activate(v); |
| 508 | 498 |
} |
| 509 | 499 |
_excess->set(v, (*_excess)[v] + rem); |
| 510 | 500 |
_flow->set(a, 0); |
| 511 | 501 |
} |
| 512 | 502 |
|
| 513 | 503 |
target = new_target; |
| 514 | 504 |
if ((*_active)[target]) {
|
| 515 | 505 |
deactivate(target); |
| 516 | 506 |
} |
| 517 | 507 |
|
| 518 | 508 |
_highest = _sets.back().begin(); |
| 519 | 509 |
while (_highest != _sets.back().end() && |
| 520 | 510 |
!(*_active)[_first[*_highest]]) {
|
| 521 | 511 |
++_highest; |
| 522 | 512 |
} |
| 523 | 513 |
} |
| 524 | 514 |
} |
| 525 | 515 |
} |
| 526 | 516 |
|
| 527 | 517 |
void findMinCutIn() {
|
| 528 | 518 |
|
| 529 | 519 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 530 | 520 |
_excess->set(n, 0); |
| 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 |
|
|
| 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; |
|
| 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 |
} |
|
| 567 | 553 |
|
| 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 |
} |
|
| 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; |
|
| 578 | 562 |
} |
| 579 | 563 |
} |
| 580 |
queue.swap(nqueue); |
|
| 581 |
++bucket_num; |
|
| 582 | 564 |
} |
| 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()]; |
| 594 | 575 |
{
|
| 595 | 576 |
for (InArcIt a(_graph, _source); a != INVALID; ++a) {
|
| 596 | 577 |
if (_tolerance.positive((*_capacity)[a])) {
|
| 597 | 578 |
Node u = _graph.source(a); |
| 598 | 579 |
_flow->set(a, (*_capacity)[a]); |
| 599 | 580 |
_excess->set(u, (*_excess)[u] + (*_capacity)[a]); |
| 600 | 581 |
if (!(*_active)[u] && u != _source) {
|
| 601 | 582 |
activate(u); |
| 602 | 583 |
} |
| 603 | 584 |
} |
| 604 | 585 |
} |
| 605 | 586 |
if ((*_active)[target]) {
|
| 606 | 587 |
deactivate(target); |
| 607 | 588 |
} |
| 608 | 589 |
|
| 609 | 590 |
_highest = _sets.back().begin(); |
| 610 | 591 |
while (_highest != _sets.back().end() && |
| 611 | 592 |
!(*_active)[_first[*_highest]]) {
|
| 612 | 593 |
++_highest; |
| 613 | 594 |
} |
| 614 | 595 |
} |
| 615 | 596 |
|
| 616 | 597 |
|
| 617 | 598 |
while (true) {
|
| 618 | 599 |
while (_highest != _sets.back().end()) {
|
| 619 | 600 |
Node n = _first[*_highest]; |
| 620 | 601 |
Value excess = (*_excess)[n]; |
| 621 | 602 |
int next_bucket = _node_num; |
| 622 | 603 |
|
| 623 | 604 |
int under_bucket; |
| 624 | 605 |
if (++std::list<int>::iterator(_highest) == _sets.back().end()) {
|
| 625 | 606 |
under_bucket = -1; |
| 626 | 607 |
} else {
|
| 627 | 608 |
under_bucket = *(++std::list<int>::iterator(_highest)); |
| 628 | 609 |
} |
| 629 | 610 |
|
| 630 | 611 |
for (InArcIt a(_graph, n); a != INVALID; ++a) {
|
| 631 | 612 |
Node v = _graph.source(a); |
| 632 | 613 |
if (_dormant[(*_bucket)[v]]) continue; |
| 633 | 614 |
Value rem = (*_capacity)[a] - (*_flow)[a]; |
| 634 | 615 |
if (!_tolerance.positive(rem)) continue; |
| 635 | 616 |
if ((*_bucket)[v] == under_bucket) {
|
| ... | ... |
@@ -819,100 +800,100 @@ |
| 819 | 800 |
} |
| 820 | 801 |
|
| 821 | 802 |
target = new_target; |
| 822 | 803 |
if ((*_active)[target]) {
|
| 823 | 804 |
deactivate(target); |
| 824 | 805 |
} |
| 825 | 806 |
|
| 826 | 807 |
_highest = _sets.back().begin(); |
| 827 | 808 |
while (_highest != _sets.back().end() && |
| 828 | 809 |
!(*_active)[_first[*_highest]]) {
|
| 829 | 810 |
++_highest; |
| 830 | 811 |
} |
| 831 | 812 |
} |
| 832 | 813 |
} |
| 833 | 814 |
} |
| 834 | 815 |
|
| 835 | 816 |
public: |
| 836 | 817 |
|
| 837 | 818 |
/// \name Execution control |
| 838 | 819 |
/// The simplest way to execute the algorithm is to use |
| 839 | 820 |
/// one of the member functions called \c run(...). |
| 840 | 821 |
/// \n |
| 841 | 822 |
/// If you need more control on the execution, |
| 842 | 823 |
/// first you must call \ref init(), then the \ref calculateIn() or |
| 843 | 824 |
/// \ref calculateIn() functions. |
| 844 | 825 |
|
| 845 | 826 |
/// @{
|
| 846 | 827 |
|
| 847 | 828 |
/// \brief Initializes the internal data structures. |
| 848 | 829 |
/// |
| 849 | 830 |
/// Initializes the internal data structures. It creates |
| 850 | 831 |
/// the maps, residual graph adaptors and some bucket structures |
| 851 | 832 |
/// for the algorithm. |
| 852 | 833 |
void init() {
|
| 853 | 834 |
init(NodeIt(_graph)); |
| 854 | 835 |
} |
| 855 | 836 |
|
| 856 | 837 |
/// \brief Initializes the internal data structures. |
| 857 | 838 |
/// |
| 858 | 839 |
/// Initializes the internal data structures. It creates |
| 859 | 840 |
/// the maps, residual graph adaptor and some bucket structures |
| 860 | 841 |
/// for the algorithm. Node \c source is used as the push-relabel |
| 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); |
| 877 | 858 |
} |
| 878 | 859 |
if (!_prev) {
|
| 879 | 860 |
_prev = new typename Digraph::template NodeMap<Node>(_graph); |
| 880 | 861 |
} |
| 881 | 862 |
if (!_active) {
|
| 882 | 863 |
_active = new typename Digraph::template NodeMap<bool>(_graph); |
| 883 | 864 |
} |
| 884 | 865 |
if (!_bucket) {
|
| 885 | 866 |
_bucket = new typename Digraph::template NodeMap<int>(_graph); |
| 886 | 867 |
} |
| 887 | 868 |
if (!_excess) {
|
| 888 | 869 |
_excess = new ExcessMap(_graph); |
| 889 | 870 |
} |
| 890 | 871 |
if (!_source_set) {
|
| 891 | 872 |
_source_set = new SourceSetMap(_graph); |
| 892 | 873 |
} |
| 893 | 874 |
if (!_min_cut_map) {
|
| 894 | 875 |
_min_cut_map = new MinCutMap(_graph); |
| 895 | 876 |
} |
| 896 | 877 |
|
| 897 | 878 |
_min_cut = std::numeric_limits<Value>::max(); |
| 898 | 879 |
} |
| 899 | 880 |
|
| 900 | 881 |
|
| 901 | 882 |
/// \brief Calculates a minimum cut with \f$ source \f$ on the |
| 902 | 883 |
/// source-side. |
| 903 | 884 |
/// |
| 904 | 885 |
/// Calculates a minimum cut with \f$ source \f$ on the |
| 905 | 886 |
/// source-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source |
| 906 | 887 |
/// \in X \f$ and minimal out-degree). |
| 907 | 888 |
void calculateOut() {
|
| 908 | 889 |
findMinCutOut(); |
| 909 | 890 |
} |
| 910 | 891 |
|
| 911 | 892 |
/// \brief Calculates a minimum cut with \f$ source \f$ on the |
| 912 | 893 |
/// target-side. |
| 913 | 894 |
/// |
| 914 | 895 |
/// Calculates a minimum cut with \f$ source \f$ on the |
| 915 | 896 |
/// target-side (i.e. a set \f$ X\subsetneq V \f$ with \f$ source |
| 916 | 897 |
/// \in X \f$ and minimal out-degree). |
| 917 | 898 |
void calculateIn() {
|
| 918 | 899 |
findMinCutIn(); |
0 comments (0 inline)