353 // ********************************************************************** |
353 // ********************************************************************** |
354 |
354 |
355 |
355 |
356 template <typename Graph> |
356 template <typename Graph> |
357 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template |
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 //We have one tree which we grow, and also shrink but only if it cannot be |
360 //We have one tree which we grow, and also shrink but only if it cannot be |
360 //postponed. If we augment then we return to the "for" cycle of |
361 //postponed. If we augment then we return to the "for" cycle of |
361 //runEdmonds(). |
362 //runEdmonds(). |
362 |
363 |
363 std::queue<Node> Q; //queue of the totally unscanned nodes |
364 std::queue<Node> Q; //queue of the totally unscanned nodes |
370 Q.pop(); |
371 Q.pop(); |
371 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
372 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
372 Node y=g.runningNode(e); |
373 Node y=g.runningNode(e); |
373 //growOrAugment grows if y is covered by the matching and |
374 //growOrAugment grows if y is covered by the matching and |
374 //augments if not. In this latter case it returns 1. |
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 R.push(x); |
379 R.push(x); |
378 } |
380 } |
379 |
381 |
380 while ( !R.empty() ) { |
382 while ( !R.empty() ) { |
387 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) |
389 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) |
388 //Recall that we have only one tree. |
390 //Recall that we have only one tree. |
389 shrink( x, y, ear, blossom, tree, Q); |
391 shrink( x, y, ear, blossom, tree, Q); |
390 |
392 |
391 while ( !Q.empty() ) { |
393 while ( !Q.empty() ) { |
392 Node x=Q.front(); |
394 Node z=Q.front(); |
393 Q.pop(); |
395 Q.pop(); |
394 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
396 for( IncEdgeIt f(g,z); f!= INVALID; ++f ) { |
395 Node y=g.runningNode(e); |
397 Node w=g.runningNode(f); |
396 //growOrAugment grows if y is covered by the matching and |
398 //growOrAugment grows if y is covered by the matching and |
397 //augments if not. In this latter case it returns 1. |
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 } //for e |
405 } //for e |
403 } // while ( !R.empty() ) |
406 } // while ( !R.empty() ) |
404 } |
407 } |
405 |
408 |