Changeset 2023:f34f044a043c in lemon0.x for lemon/max_matching.h
 Timestamp:
 03/30/06 17:02:11 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2661
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/max_matching.h
r1993 r2023 115 115 void runEdmonds( int heur = 1 ) { 116 116 117 //each vertex is put to C 117 118 for(NodeIt v(g); v!=INVALID; ++v) 118 119 position.set(v,C); … … 129 130 //blossom_base and tree_base should be a member. 130 131 132 //We build only one tree and the other vertices uncovered by the 133 //matching belong to C. (They can be considered as singleton 134 //trees.) If this tree can be augmented or no more 135 //grow/augmentation/shrink is possible then we return to this 136 //"for" cycle. 131 137 for(NodeIt v(g); v!=INVALID; ++v) { 132 138 if ( position[v]==C && _mate[v]==INVALID ) { … … 224 230 template<typename NMapE> 225 231 void readNMapEdge(NMapE& map) { 226 for(NodeIt v(g); v!=INVALID; ++v) {227 232 for(NodeIt v(g); v!=INVALID; ++v) { 233 UEdge e=map[v]; 228 234 if ( e!=INVALID ) 229 235 _mate.set(v,g.oppositeNode(v,e)); … … 324 330 UFE& blossom, UFE& tree); 325 331 326 bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,327 UFE& blossom, UFE& tree,std::queue<Node>& Q);332 void shrink(Node x,Node y, typename Graph::template NodeMap<Node>& ear, 333 UFE& blossom, UFE& tree,std::queue<Node>& Q); 328 334 329 335 void shrinkStep(Node& top, Node& middle, Node& bottom, … … 331 337 UFE& blossom, UFE& tree, std::queue<Node>& Q); 332 338 339 bool growOrAugment(Node& y, Node& x, typename Graph::template 340 NodeMap<Node>& ear, UFE& blossom, UFE& tree, 341 std::queue<Node>& Q); 342 333 343 void augment(Node x, typename Graph::template NodeMap<Node>& ear, 334 344 UFE& blossom, UFE& tree); … … 343 353 344 354 template <typename Graph> 345 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 346 UFE& blossom, UFE& tree) { 355 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template 356 NodeMap<Node>& ear, UFE& blossom, UFE& tree) { 357 //We have one tree which we grow, and also shrink but only if it cannot be 358 //postponed. If we augment then we return to the "for" cycle of 359 //runEdmonds(). 347 360 348 361 std::queue<Node> Q; //queue of the totally unscanned nodes … … 354 367 Node x=Q.front(); 355 368 Q.pop(); 356 if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return; 357 else R.push(x); 369 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { 370 Node y=g.runningNode(e); 371 //growOrAugment grows if y is covered by the matching and 372 //augments if not. In this latter case it returns 1. 373 if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; 374 } 375 R.push(x); 358 376 } 359 377 … … 365 383 Node y=g.runningNode(e); 366 384 367 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 368 //x and y must be in the same tree 385 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) 386 //Recall that we have only one tree. 387 shrink( x, y, ear, blossom, tree, Q); 369 388 370 typename Graph::template NodeMap<bool> path(g,false);371 372 Node b=blossom.find(x);373 path.set(b,true);374 b=_mate[b];375 while ( b!=INVALID ) {376 b=blossom.find(ear[b]);377 path.set(b,true);378 b=_mate[b];379 } //going till the root380 381 Node top=y;382 Node middle=blossom.find(top);383 Node bottom=x;384 while ( !path[middle] )385 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);386 387 Node base=middle;388 top=x;389 middle=blossom.find(top);390 bottom=y;391 Node blossom_base=blossom.find(base);392 while ( middle!=blossom_base )393 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);394 395 blossom.makeRep(base);396 } // if shrink is needed397 398 389 while ( !Q.empty() ) { 399 390 Node x=Q.front(); 400 391 Q.pop(); 401 if ( noShrinkStep(x, ear, blossom, tree, Q) ) return; 402 else R.push(x); 392 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { 393 Node y=g.runningNode(e); 394 //growOrAugment grows if y is covered by the matching and 395 //augments if not. In this latter case it returns 1. 396 if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; 397 } 398 R.push(x); 403 399 } 404 400 } //for e … … 412 408 NodeMap<Node>& ear, 413 409 UFE& blossom, UFE& tree) { 410 //We have one tree, which we grow and shrink. If we augment then we 411 //return to the "for" cycle of runEdmonds(). 412 414 413 std::queue<Node> Q; //queue of the unscanned nodes 415 414 Q.push(v); … … 424 423 switch ( position[y] ) { 425 424 case D: //x and y must be in the same tree 426 427 if ( blossom.find(x) != blossom.find(y) ) { //shrink 428 typename Graph::template NodeMap<bool> path(g,false); 429 430 Node b=blossom.find(x); 431 path.set(b,true); 432 b=_mate[b]; 433 while ( b!=INVALID ) { 434 b=blossom.find(ear[b]); 435 path.set(b,true); 436 b=_mate[b]; 437 } //going till the root 438 439 Node top=y; 440 Node middle=blossom.find(top); 441 Node bottom=x; 442 while ( !path[middle] ) 443 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); 444 445 Node base=middle; 446 top=x; 447 middle=blossom.find(top); 448 bottom=y; 449 Node blossom_base=blossom.find(base); 450 while ( middle!=blossom_base ) 451 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); 452 453 blossom.makeRep(base); 454 } 425 if ( blossom.find(x) != blossom.find(y) ) 426 //x and y are in the same tree 427 shrink( x, y, ear, blossom, tree, Q); 455 428 break; 456 429 case C: 457 if ( _mate[y]!=INVALID ) { //grow 458 459 ear.set(y,x); 460 Node w=_mate[y]; 461 blossom.insert(w); 462 position.set(y,A); 463 position.set(w,D); 464 tree.insert(y); 465 tree.insert(w); 466 tree.join(y,blossom.find(x)); 467 tree.join(w,y); 468 Q.push(w); 469 } else { //augment 470 augment(x, ear, blossom, tree); 471 _mate.set(x,y); 472 _mate.set(y,x); 473 return; 474 } //if 430 //growOrAugment grows if y is covered by the matching and 431 //augments if not. In this latter case it returns 1. 432 if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return; 475 433 break; 476 434 default: break; 477 }435 } 478 436 } 479 437 } 480 438 } 481 482 template <typename Graph> 483 bool MaxMatching<Graph>::noShrinkStep(Node x, 484 typename Graph::template 485 NodeMap<Node>& ear, 486 UFE& blossom, UFE& tree, 487 std::queue<Node>& Q) { 488 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { 489 Node y=g.runningNode(e); 490 491 if ( position[y]==C ) { 492 if ( _mate[y]!=INVALID ) { //grow 493 ear.set(y,x); 494 Node w=_mate[y]; 495 blossom.insert(w); 496 position.set(y,A); 497 position.set(w,D); 498 tree.insert(y); 499 tree.insert(w); 500 tree.join(y,blossom.find(x)); 501 tree.join(w,y); 502 Q.push(w); 503 } else { //augment 504 augment(x, ear, blossom, tree); 505 _mate.set(x,y); 506 _mate.set(y,x); 507 return true; 508 } 509 } 510 } 511 return false; 439 440 441 template <typename Graph> 442 void MaxMatching<Graph>::shrink(Node x,Node y, typename 443 Graph::template NodeMap<Node>& ear, 444 UFE& blossom, UFE& tree, std::queue<Node>& Q) { 445 //x and y are the two adjacent vertices in two blossoms. 446 447 typename Graph::template NodeMap<bool> path(g,false); 448 449 Node b=blossom.find(x); 450 path.set(b,true); 451 b=_mate[b]; 452 while ( b!=INVALID ) { 453 b=blossom.find(ear[b]); 454 path.set(b,true); 455 b=_mate[b]; 456 } //we go until the root through bases of blossoms and odd vertices 457 458 Node top=y; 459 Node middle=blossom.find(top); 460 Node bottom=x; 461 while ( !path[middle] ) 462 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); 463 //Until we arrive to a node on the path, we update blossom, tree 464 //and the positions of the odd nodes. 465 466 Node base=middle; 467 top=x; 468 middle=blossom.find(top); 469 bottom=y; 470 Node blossom_base=blossom.find(base); 471 while ( middle!=blossom_base ) 472 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); 473 //Until we arrive to a node on the path, we update blossom, tree 474 //and the positions of the odd nodes. 475 476 blossom.makeRep(base); 512 477 } 478 479 513 480 514 481 template <typename Graph> … … 518 485 UFE& blossom, UFE& tree, 519 486 std::queue<Node>& Q) { 487 //We traverse a blossom and update everything. 488 520 489 ear.set(top,bottom); 521 490 Node t=top; … … 538 507 } 539 508 509 510 template <typename Graph> 511 bool MaxMatching<Graph>::growOrAugment(Node& y, Node& x, typename Graph::template 512 NodeMap<Node>& ear, UFE& blossom, UFE& tree, 513 std::queue<Node>& Q) { 514 //x is in a blossom in the tree, y is outside. If y is covered by 515 //the matching we grow, otherwise we augment. In this case we 516 //return 1. 517 518 if ( _mate[y]!=INVALID ) { //grow 519 ear.set(y,x); 520 Node w=_mate[y]; 521 blossom.insert(w); 522 position.set(y,A); 523 position.set(w,D); 524 tree.insert(y); 525 tree.insert(w); 526 tree.join(y,blossom.find(x)); 527 tree.join(w,y); 528 Q.push(w); 529 } else { //augment 530 augment(x, ear, blossom, tree); 531 _mate.set(x,y); 532 _mate.set(y,x); 533 return true; 534 } 535 return false; 536 } 537 538 540 539 template <typename Graph> 541 540 void MaxMatching<Graph>::augment(Node x, … … 551 550 _mate.set(u,tmp); 552 551 } 552 Node y=blossom.find(x); 553 553 typename UFE::ItemIt it; 554 554 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) { … … 561 561 } else position.set( it ,C); 562 562 } 563 tree.eraseClass( x);563 tree.eraseClass(y); 564 564 565 565 }
Note: See TracChangeset
for help on using the changeset viewer.