Changeset 1093:31834bad3e84 in lemon0.x
 Timestamp:
 01/25/05 18:40:22 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1491
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/max_matching.h
r1090 r1093 19 19 20 20 #include <queue> 21 #include < invalid.h>22 #include < unionfind.h>21 #include <lemon/invalid.h> 22 #include <lemon/unionfind.h> 23 23 #include <lemon/graph_utils.h> 24 24 … … 82 82 static const int HEUR_density=2; 83 83 const Graph& g; 84 typename Graph::template NodeMap<Node> mate;84 typename Graph::template NodeMap<Node> _mate; 85 85 typename Graph::template NodeMap<pos_enum> position; 86 86 87 87 public: 88 88 89 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {}89 MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {} 90 90 91 91 ///Runs Edmonds' algorithm. … … 120 120 /// 121 121 void resetMatching(); 122 123 ///Returns the mate of a node in the actual matching. 124 125 ///Returns the mate of a \c node in the actual matching. 126 ///Returns INVALID if the \c node is not covered by the actual matching. 127 Node mate(Node& node) const { 128 return _mate[node]; 129 } 122 130 123 131 ///Reads a matching from a \c Node map of \c Nodes. … … 129 137 void readNMapNode(NMapN& map) { 130 138 for(NodeIt v(g); v!=INVALID; ++v) { 131 mate.set(v,map[v]);139 _mate.set(v,map[v]); 132 140 } 133 141 } … … 141 149 void writeNMapNode (NMapN& map) const { 142 150 for(NodeIt v(g); v!=INVALID; ++v) { 143 map.set(v, mate[v]);151 map.set(v,_mate[v]); 144 152 } 145 153 } … … 156 164 Edge e=map[v]; 157 165 if ( g.valid(e) ) 158 g.source(e) == v ? mate.set(v,g.target(e)) :mate.set(v,g.source(e));166 g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e)); 159 167 } 160 168 } … … 170 178 typename Graph::template NodeMap<bool> todo(g,true); 171 179 for(NodeIt v(g); v!=INVALID; ++v) { 172 if ( todo[v] && mate[v]!=INVALID ) {173 Node u= mate[v];180 if ( todo[v] && _mate[v]!=INVALID ) { 181 Node u=_mate[v]; 174 182 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { 175 183 if ( g.target(e) == u ) { … … 198 206 Node u=g.source(e); 199 207 Node v=g.target(e); 200 mate.set(u,v);201 mate.set(v,u);208 _mate.set(u,v); 209 _mate.set(v,u); 202 210 } 203 211 } … … 217 225 typename Graph::template NodeMap<bool> todo(g,true); 218 226 for(NodeIt v(g); v!=INVALID; ++v) { 219 if ( todo[v] && mate[v]!=INVALID ) {220 Node u= mate[v];227 if ( todo[v] && _mate[v]!=INVALID ) { 228 Node u=_mate[v]; 221 229 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { 222 230 if ( g.target(e) == u ) { … … 293 301 294 302 for(NodeIt v(g); v!=INVALID; ++v) { 295 if ( position[v]==C && mate[v]==INVALID ) {303 if ( position[v]==C && _mate[v]==INVALID ) { 296 304 blossom.insert(v); 297 305 tree.insert(v); … … 334 342 Node b=blossom.find(x); 335 343 path.set(b,true); 336 b= mate[b];344 b=_mate[b]; 337 345 while ( b!=INVALID ) { 338 346 b=blossom.find(ear[b]); 339 347 path.set(b,true); 340 b= mate[b];348 b=_mate[b]; 341 349 } //going till the root 342 350 … … 391 399 Node b=blossom.find(x); 392 400 path.set(b,true); 393 b= mate[b];401 b=_mate[b]; 394 402 while ( b!=INVALID ) { 395 403 b=blossom.find(ear[b]); 396 404 path.set(b,true); 397 b= mate[b];405 b=_mate[b]; 398 406 } //going till the root 399 407 … … 416 424 break; 417 425 case C: 418 if ( mate[y]!=INVALID ) { //grow426 if ( _mate[y]!=INVALID ) { //grow 419 427 420 428 ear.set(y,x); 421 Node w= mate[y];429 Node w=_mate[y]; 422 430 blossom.insert(w); 423 431 position.set(y,A); … … 430 438 } else { //augment 431 439 augment(x, ear, blossom, tree); 432 mate.set(x,y);433 mate.set(y,x);440 _mate.set(x,y); 441 _mate.set(y,x); 434 442 return; 435 443 } //if … … 444 452 void MaxMatching<Graph>::greedyMatching() { 445 453 for(NodeIt v(g); v!=INVALID; ++v) 446 if ( mate[v]==INVALID ) {454 if ( _mate[v]==INVALID ) { 447 455 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { 448 456 Node y=g.target(e); 449 if ( mate[y]==INVALID && y!=v ) {450 mate.set(v,y);451 mate.set(y,v);457 if ( _mate[y]==INVALID && y!=v ) { 458 _mate.set(v,y); 459 _mate.set(y,v); 452 460 break; 453 461 } … … 460 468 int s=0; 461 469 for(NodeIt v(g); v!=INVALID; ++v) { 462 if ( mate[v]!=INVALID ) {470 if ( _mate[v]!=INVALID ) { 463 471 ++s; 464 472 } … … 470 478 void MaxMatching<Graph>::resetMatching() { 471 479 for(NodeIt v(g); v!=INVALID; ++v) 472 mate.set(v,INVALID);480 _mate.set(v,INVALID); 473 481 } 474 482 … … 480 488 481 489 if ( position[y]==C ) { 482 if ( mate[y]!=INVALID ) { //grow490 if ( _mate[y]!=INVALID ) { //grow 483 491 ear.set(y,x); 484 Node w= mate[y];492 Node w=_mate[y]; 485 493 blossom.insert(w); 486 494 position.set(y,A); … … 493 501 } else { //augment 494 502 augment(x, ear, blossom, tree); 495 mate.set(x,y);496 mate.set(y,x);503 _mate.set(x,y); 504 _mate.set(y,x); 497 505 return true; 498 506 } … … 508 516 Node t=top; 509 517 while ( t!=middle ) { 510 Node u= mate[t];518 Node u=_mate[t]; 511 519 t=ear[u]; 512 520 ear.set(t,u); 513 521 } 514 bottom= mate[middle];522 bottom=_mate[middle]; 515 523 position.set(bottom,D); 516 524 Q.push(bottom); … … 528 536 void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear, 529 537 UFE& blossom, UFE& tree) { 530 Node v= mate[x];538 Node v=_mate[x]; 531 539 while ( v!=INVALID ) { 532 540 533 541 Node u=ear[v]; 534 mate.set(v,u);542 _mate.set(v,u); 535 543 Node tmp=v; 536 v= mate[u];537 mate.set(u,tmp);544 v=_mate[u]; 545 _mate.set(u,tmp); 538 546 } 539 547 typename UFE::ItemIt it;
Note: See TracChangeset
for help on using the changeset viewer.