Changeset 2386:81b47fc5c444 in lemon-0.x for lemon/max_matching.h
- Timestamp:
- 03/02/07 19:04:28 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3217
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/max_matching.h
r2308 r2386 356 356 template <typename Graph> 357 357 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template 358 NodeMap<Node>& ear, UFE& blossom, UFE& tree) { 358 NodeMap<Node>& ear, UFE& blossom, 359 UFE& tree) { 359 360 //We have one tree which we grow, and also shrink but only if it cannot be 360 361 //postponed. If we augment then we return to the "for" cycle of … … 373 374 //growOrAugment grows if y is covered by the matching and 374 375 //augments if not. In this latter case it returns 1. 375 if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; 376 if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) 377 return; 376 378 } 377 379 R.push(x); … … 390 392 391 393 while ( !Q.empty() ) { 392 Node x=Q.front();394 Node z=Q.front(); 393 395 Q.pop(); 394 for( IncEdgeIt e(g,x); e!= INVALID; ++e) {395 Node y=g.runningNode(e);396 for( IncEdgeIt f(g,z); f!= INVALID; ++f ) { 397 Node w=g.runningNode(f); 396 398 //growOrAugment grows if y is covered by the matching and 397 399 //augments if not. In this latter case it returns 1. 398 if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return; 400 if ( position[w]==C && growOrAugment(w, z, ear, blossom, tree, Q) ) 401 return; 399 402 } 400 R.push( x);403 R.push(z); 401 404 } 402 405 } //for e
Note: See TracChangeset
for help on using the changeset viewer.