260 |
260 |
261 |
261 |
262 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
262 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
263 UFE& blossom, UFE& tree); |
263 UFE& blossom, UFE& tree); |
264 |
264 |
265 void normShrink(Node v, typename Graph::NodeMap<Node>& ear, |
265 void normShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
266 UFE& blossom, UFE& tree); |
266 UFE& blossom, UFE& tree); |
267 |
267 |
268 bool noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear, |
268 bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear, |
269 UFE& blossom, UFE& tree, std::queue<Node>& Q); |
269 UFE& blossom, UFE& tree, std::queue<Node>& Q); |
270 |
270 |
271 void shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear, |
271 void shrinkStep(Node& top, Node& middle, Node& bottom, |
|
272 typename Graph::template NodeMap<Node>& ear, |
272 UFE& blossom, UFE& tree, std::queue<Node>& Q); |
273 UFE& blossom, UFE& tree, std::queue<Node>& Q); |
273 |
274 |
274 void augment(Node x, typename Graph::NodeMap<Node>& ear, |
275 void augment(Node x, typename Graph::template NodeMap<Node>& ear, |
275 UFE& blossom, UFE& tree); |
276 UFE& blossom, UFE& tree); |
276 |
277 |
277 }; |
278 }; |
278 |
279 |
279 |
280 |
384 } // while ( !R.empty() ) |
385 } // while ( !R.empty() ) |
385 } |
386 } |
386 |
387 |
387 |
388 |
388 template <typename Graph> |
389 template <typename Graph> |
389 void MaxMatching<Graph>::normShrink(Node v, typename Graph::NodeMap<Node>& ear, |
390 void MaxMatching<Graph>::normShrink(Node v, |
|
391 typename Graph::template |
|
392 NodeMap<Node>& ear, |
390 UFE& blossom, UFE& tree) { |
393 UFE& blossom, UFE& tree) { |
391 |
|
392 std::queue<Node> Q; //queue of the unscanned nodes |
394 std::queue<Node> Q; //queue of the unscanned nodes |
393 Q.push(v); |
395 Q.push(v); |
394 while ( !Q.empty() ) { |
396 while ( !Q.empty() ) { |
395 |
397 |
396 Node x=Q.front(); |
398 Node x=Q.front(); |
488 for(NodeIt v(g); v!=INVALID; ++v) |
490 for(NodeIt v(g); v!=INVALID; ++v) |
489 _mate.set(v,INVALID); |
491 _mate.set(v,INVALID); |
490 } |
492 } |
491 |
493 |
492 template <typename Graph> |
494 template <typename Graph> |
493 bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear, |
495 bool MaxMatching<Graph>::noShrinkStep(Node x, |
494 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
496 typename Graph::template |
|
497 NodeMap<Node>& ear, |
|
498 UFE& blossom, UFE& tree, |
|
499 std::queue<Node>& Q) { |
495 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
500 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
496 Node y=g.runningNode(e); |
501 Node y=g.runningNode(e); |
497 |
502 |
498 if ( position[y]==C ) { |
503 if ( position[y]==C ) { |
499 if ( _mate[y]!=INVALID ) { //grow |
504 if ( _mate[y]!=INVALID ) { //grow |
517 } |
522 } |
518 return false; |
523 return false; |
519 } |
524 } |
520 |
525 |
521 template <typename Graph> |
526 template <typename Graph> |
522 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear, |
527 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, |
523 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
528 typename Graph::template |
|
529 NodeMap<Node>& ear, |
|
530 UFE& blossom, UFE& tree, |
|
531 std::queue<Node>& Q) { |
524 ear.set(top,bottom); |
532 ear.set(top,bottom); |
525 Node t=top; |
533 Node t=top; |
526 while ( t!=middle ) { |
534 while ( t!=middle ) { |
527 Node u=_mate[t]; |
535 Node u=_mate[t]; |
528 t=ear[u]; |
536 t=ear[u]; |
540 blossom.join(bottom, oldmiddle); |
548 blossom.join(bottom, oldmiddle); |
541 blossom.join(top, oldmiddle); |
549 blossom.join(top, oldmiddle); |
542 } |
550 } |
543 |
551 |
544 template <typename Graph> |
552 template <typename Graph> |
545 void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear, |
553 void MaxMatching<Graph>::augment(Node x, |
|
554 typename Graph::template NodeMap<Node>& ear, |
546 UFE& blossom, UFE& tree) { |
555 UFE& blossom, UFE& tree) { |
547 Node v=_mate[x]; |
556 Node v=_mate[x]; |
548 while ( v!=INVALID ) { |
557 while ( v!=INVALID ) { |
549 |
558 |
550 Node u=ear[v]; |
559 Node u=ear[v]; |