Changeset 1423:8c567e298d7f in lemon for lemon/matching.h
 Timestamp:
 10/27/18 13:00:48 (15 months ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/matching.h
r1270 r1423 116 116 int _process, _postpone, _last; 117 117 118 int _node_num ;118 int _node_num, _unmatched; 119 119 120 120 private: … … 180 180 } else if ((*_status)[v] == UNMATCHED) { 181 181 augmentOnArc(a); 182 _unmatched; 182 183 return; 183 184 } … … 205 206 } else if ((*_status)[x] == UNMATCHED) { 206 207 augmentOnArc(b); 208 _unmatched; 207 209 return; 208 210 } … … 229 231 } else if ((*_status)[v] == UNMATCHED) { 230 232 augmentOnArc(a); 233 _unmatched; 231 234 return; 232 235 } … … 438 441 (*_status)[n] = UNMATCHED; 439 442 } 443 _unmatched = _node_num; 440 444 } 441 445 … … 449 453 (*_status)[n] = UNMATCHED; 450 454 } 455 _unmatched = _node_num; 451 456 for (NodeIt n(_graph); n != INVALID; ++n) { 452 457 if ((*_matching)[n] == INVALID) { … … 458 463 (*_matching)[v] = _graph.oppositeArc(a); 459 464 (*_status)[v] = MATCHED; 465 _unmatched = 2; 460 466 break; 461 467 } … … 480 486 (*_status)[n] = UNMATCHED; 481 487 } 488 _unmatched = _node_num; 482 489 for(EdgeIt e(_graph); e!=INVALID; ++e) { 483 490 if (matching[e]) { … … 492 499 (*_matching)[v] = _graph.direct(e, false); 493 500 (*_status)[v] = MATCHED; 501 502 _unmatched = 2; 494 503 } 495 504 } … … 499 508 /// \brief Start Edmonds' algorithm 500 509 /// 501 /// This function runs the original Edmonds' algorithm. 510 /// This function runs the original Edmonds' algorithm. If the 511 /// \c decomposition parameter is set to false, then the GallaiEdmonds 512 /// decomposition is not computed. 502 513 /// 503 514 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be 504 515 /// called before using this function. 505 void startSparse() { 506 for(NodeIt n(_graph); n != INVALID; ++n) { 516 void startSparse(bool decomposition = true) { 517 int _unmatched_limit = decomposition ? 0 : 1; 518 for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) { 507 519 if ((*_status)[n] == UNMATCHED) { 508 520 (*_blossom_rep)[_blossom_set>insert(n)] = n; 509 521 _tree_set>insert(n); 510 522 (*_status)[n] = EVEN; 523 _unmatched; 511 524 processSparse(n); 512 525 } … … 518 531 /// 519 532 /// This function runs Edmonds' algorithm with a heuristic of postponing 520 /// shrinks, therefore resulting in a faster algorithm for dense graphs. 533 /// shrinks, therefore resulting in a faster algorithm for dense graphs. If 534 /// the \c decomposition parameter is set to false, then the GallaiEdmonds 535 /// decomposition is not computed. 521 536 /// 522 537 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be 523 538 /// called before using this function. 524 void startDense() { 525 for(NodeIt n(_graph); n != INVALID; ++n) { 539 void startDense(bool decomposition = true) { 540 int _unmatched_limit = decomposition ? 0 : 1; 541 for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) { 526 542 if ((*_status)[n] == UNMATCHED) { 527 543 (*_blossom_rep)[_blossom_set>insert(n)] = n; 528 544 _tree_set>insert(n); 529 545 (*_status)[n] = EVEN; 546 _unmatched; 530 547 processDense(n); 531 548 } … … 537 554 /// 538 555 /// This function runs Edmonds' algorithm. An additional heuristic of 539 /// postponing shrinks is used for relatively dense graphs 540 /// (for which <tt>m>=2*n</tt> holds). 541 void run() { 556 /// postponing shrinks is used for relatively dense graphs (for which 557 /// <tt>m>=2*n</tt> holds). If the \c decomposition parameter is set to 558 /// false, then the GallaiEdmonds decomposition is not computed. In some 559 /// cases, this can speed up the algorithm significantly, especially when a 560 /// maximum matching is computed in a dense graph with odd number of nodes. 561 void run(bool decomposition = true) { 542 562 if (countEdges(_graph) < 2 * countNodes(_graph)) { 543 563 greedyInit(); 544 startSparse( );564 startSparse(decomposition); 545 565 } else { 546 566 init(); 547 startDense( );567 startDense(decomposition); 548 568 } 549 569 }
Note: See TracChangeset
for help on using the changeset viewer.