Changeset 1423:8c567e298d7f in lemon
- Timestamp:
- 10/27/18 13:00:48 (6 years ago)
- Branch:
- default
- Children:
- 1426:736a341e604b, 1427:57abff252556, 1430:c6aa2cc1af04
- Phase:
- public
- Files:
-
- 2 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 Gallai-Edmonds 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 Gallai-Edmonds 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 Gallai-Edmonds 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 } -
test/matching_test.cc
r1270 r1423 135 135 mat_test.startDense(); 136 136 mat_test.run(); 137 mat_test.startSparse(false); 138 mat_test.startDense(false); 139 mat_test.run(false); 137 140 138 141 const_mat_test.matchingSize(); … … 403 406 edgeMap("weight", weight).run(); 404 407 408 int size; 405 409 bool perfect; 406 410 { … … 408 412 mm.run(); 409 413 checkMatching(graph, mm); 414 size = mm.matchingSize(); 410 415 perfect = 2 * mm.matchingSize() == countNodes(graph); 416 } 417 418 { 419 MaxMatching<SmartGraph> mm(graph); 420 mm.init(); 421 mm.startSparse(); 422 checkMatching(graph, mm); 423 check(size == mm.matchingSize(), "Inconsistent matching size"); 424 } 425 426 { 427 MaxMatching<SmartGraph> mm(graph); 428 mm.init(); 429 mm.startDense(); 430 checkMatching(graph, mm); 431 check(size == mm.matchingSize(), "Inconsistent matching size"); 432 } 433 434 { 435 MaxMatching<SmartGraph> mm(graph); 436 mm.greedyInit(); 437 mm.startSparse(); 438 checkMatching(graph, mm); 439 check(size == mm.matchingSize(), "Inconsistent matching size"); 440 } 441 442 { 443 MaxMatching<SmartGraph> mm(graph); 444 mm.greedyInit(); 445 mm.startDense(); 446 checkMatching(graph, mm); 447 check(size == mm.matchingSize(), "Inconsistent matching size"); 448 } 449 450 { 451 MaxMatching<SmartGraph> mm(graph); 452 mm.run(false); 453 check(size == mm.matchingSize(), "Inconsistent max cardinality matching"); 454 } 455 456 { 457 MaxMatching<SmartGraph> mm(graph); 458 mm.init(); 459 mm.startSparse(false); 460 check(size == mm.matchingSize(), "Inconsistent matching size"); 461 } 462 463 { 464 MaxMatching<SmartGraph> mm(graph); 465 mm.init(); 466 mm.startDense(false); 467 check(size == mm.matchingSize(), "Inconsistent matching size"); 468 } 469 470 { 471 MaxMatching<SmartGraph> mm(graph); 472 mm.greedyInit(); 473 mm.startSparse(false); 474 check(size == mm.matchingSize(), "Inconsistent matching size"); 475 } 476 477 { 478 MaxMatching<SmartGraph> mm(graph); 479 mm.greedyInit(); 480 mm.startDense(false); 481 check(size == mm.matchingSize(), "Inconsistent matching size"); 411 482 } 412 483
Note: See TracChangeset
for help on using the changeset viewer.