equal
deleted
inserted
replaced
178 typename Graph::template NodeMap<bool> todo(g,true); |
178 typename Graph::template NodeMap<bool> todo(g,true); |
179 for(NodeIt v(g); v!=INVALID; ++v) { |
179 for(NodeIt v(g); v!=INVALID; ++v) { |
180 if ( todo[v] && _mate[v]!=INVALID ) { |
180 if ( todo[v] && _mate[v]!=INVALID ) { |
181 Node u=_mate[v]; |
181 Node u=_mate[v]; |
182 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
182 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
183 if ( g.target(e) == u ) { |
183 if ( g.runningNode(e) == u ) { |
184 map.set(u,e); |
184 map.set(u,e); |
185 map.set(v,e); |
185 map.set(v,e); |
186 todo.set(u,false); |
186 todo.set(u,false); |
187 todo.set(v,false); |
187 todo.set(v,false); |
188 break; |
188 break; |
225 typename Graph::template NodeMap<bool> todo(g,true); |
225 typename Graph::template NodeMap<bool> todo(g,true); |
226 for(NodeIt v(g); v!=INVALID; ++v) { |
226 for(NodeIt v(g); v!=INVALID; ++v) { |
227 if ( todo[v] && _mate[v]!=INVALID ) { |
227 if ( todo[v] && _mate[v]!=INVALID ) { |
228 Node u=_mate[v]; |
228 Node u=_mate[v]; |
229 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
229 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
230 if ( g.target(e) == u ) { |
230 if ( g.runningNode(e) == u ) { |
231 map.set(e,true); |
231 map.set(e,true); |
232 todo.set(u,false); |
232 todo.set(u,false); |
233 todo.set(v,false); |
233 todo.set(v,false); |
234 break; |
234 break; |
235 } |
235 } |
330 while ( !R.empty() ) { |
330 while ( !R.empty() ) { |
331 Node x=R.front(); |
331 Node x=R.front(); |
332 R.pop(); |
332 R.pop(); |
333 |
333 |
334 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) { |
334 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) { |
335 Node y=g.target(e); |
335 Node y=g.runningNode(e); |
336 |
336 |
337 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { |
337 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { |
338 //x and y must be in the same tree |
338 //x and y must be in the same tree |
339 |
339 |
340 typename Graph::template NodeMap<bool> path(g,false); |
340 typename Graph::template NodeMap<bool> path(g,false); |
386 |
386 |
387 Node x=Q.front(); |
387 Node x=Q.front(); |
388 Q.pop(); |
388 Q.pop(); |
389 |
389 |
390 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) { |
390 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) { |
391 Node y=g.target(e); |
391 Node y=g.runningNode(e); |
392 |
392 |
393 switch ( position[y] ) { |
393 switch ( position[y] ) { |
394 case D: //x and y must be in the same tree |
394 case D: //x and y must be in the same tree |
395 |
395 |
396 if ( blossom.find(x) != blossom.find(y) ) { //shrink |
396 if ( blossom.find(x) != blossom.find(y) ) { //shrink |
451 template <typename Graph> |
451 template <typename Graph> |
452 void MaxMatching<Graph>::greedyMatching() { |
452 void MaxMatching<Graph>::greedyMatching() { |
453 for(NodeIt v(g); v!=INVALID; ++v) |
453 for(NodeIt v(g); v!=INVALID; ++v) |
454 if ( _mate[v]==INVALID ) { |
454 if ( _mate[v]==INVALID ) { |
455 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { |
455 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { |
456 Node y=g.target(e); |
456 Node y=g.runningNode(e); |
457 if ( _mate[y]==INVALID && y!=v ) { |
457 if ( _mate[y]==INVALID && y!=v ) { |
458 _mate.set(v,y); |
458 _mate.set(v,y); |
459 _mate.set(y,v); |
459 _mate.set(y,v); |
460 break; |
460 break; |
461 } |
461 } |
482 |
482 |
483 template <typename Graph> |
483 template <typename Graph> |
484 bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear, |
484 bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear, |
485 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
485 UFE& blossom, UFE& tree, std::queue<Node>& Q) { |
486 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
486 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
487 Node y=g.target(e); |
487 Node y=g.runningNode(e); |
488 |
488 |
489 if ( position[y]==C ) { |
489 if ( position[y]==C ) { |
490 if ( _mate[y]!=INVALID ) { //grow |
490 if ( _mate[y]!=INVALID ) { //grow |
491 ear.set(y,x); |
491 ear.set(y,x); |
492 Node w=_mate[y]; |
492 Node w=_mate[y]; |