Changeset 481:54d8feda437b in lemon-0.x
- Timestamp:
- 04/29/04 18:45:40 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@638
- Location:
- src/work/johanna
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/johanna/unionfind.h
r462 r481 265 265 266 266 /** 267 * \brief Insert the given element into the component of the others. 268 * 269 * This methods insert the element \e a into the component of the 270 * element \e comp. 271 */ 272 273 void insert(const T &a, const T &comp) { 274 275 IIter clit = _find(m[comp]); 276 ItemList &c = *clit->my_class; 277 c.push_back(ItemType(a,0)); 278 IIter ai = c.end(); 279 --ai; 280 ai->parent = clit; 281 m.set(a, ai); 282 ++clit->size; 283 } 284 285 286 /** 267 287 * \brief Find the leader of the component of the given element. 268 288 * … … 384 404 ia->parent = ia; 385 405 la->parent = ia; 406 } 407 408 /** 409 * \brief Move the given element to an other component. 410 * 411 * This method moves the element \e a from its component 412 * to the component of \e comp. 413 * If \e a and \e comp are in the same component then 414 * it returns false otherwise it returns true. 415 */ 416 417 bool move(const T &a, const T &comp) { 418 419 IIter ai = m[a]; 420 IIter lai = _find(ai); 421 IIter clit = _find(m[comp]); 422 423 if (lai == clit) 424 return false; 425 426 ItemList &c = *clit->my_class; 427 428 bool is_leader = (lai == ai); 429 bool singleton = false; 430 431 if (is_leader) { 432 ++lai; 433 } 434 435 c.splice(c.end(), *lai->my_class, ai); 436 437 if (is_leader) { 438 if (ai->size == 1) { 439 classes.erase(ai->my_class); 440 singleton = true; 441 } 442 else { 443 lai->size = ai->size; 444 lai->my_class = ai->my_class; 445 } 446 } 447 if (!singleton) { 448 for (IIter i = lai; i != lai->my_class->end(); ++i) 449 i->parent = lai; 450 --lai->size; 451 } 452 453 ai->parent = clit; 454 ai->my_class = 0; 455 ++clit->size; 456 457 return true; 386 458 } 387 459 -
src/work/johanna/unionfind_test.cc
r462 r481 70 70 print(U); 71 71 72 cout << "Inserting 8 to the component of 5 ..." << endl; 73 U.insert(8,5); 74 print(U); 75 72 76 cout << "size of the class of 4: " << U.size(4) << endl; 73 77 check(U.size(4) == 3); 74 78 cout << "size of the class of 5: " << U.size(5) << endl; 75 check(U.size(5) == 2);79 check(U.size(5) == 3); 76 80 cout << "size of the class of 6: " << U.size(6) << endl; 77 81 check(U.size(6) == 1); … … 79 83 check(U.size(2) == 3); 80 84 85 cout << "Inserting 9 ..." << endl; 86 U.insert(9); 87 print(U); 88 cout << "Inserting 10 to the component of 9 ..." << endl; 89 U.insert(10,9); 90 print(U); 91 92 cout << "Joining 8 and 10..." << endl; 93 check(U.join(8,10)); 94 print(U); 95 96 cout << "Move 9 to the class of 4 ..." << endl; 97 check(U.move(9,4)); 98 print(U); 99 100 cout << "Move 9 to the class of 2 ..." << endl; 101 check(!U.move(9,2)); 102 print(U); 103 104 cout << "size of the class of 4: " << U.size(4) << endl; 105 check(U.size(4) == 4); 106 cout << "size of the class of 9: " << U.size(9) << endl; 107 check(U.size(9) == 4); 108 109 cout << "Move 5 to the class of 6 ..." << endl; 110 check(U.move(5,6)); 111 print(U); 112 113 cout << "size of the class of 5: " << U.size(5) << endl; 114 check(U.size(5) == 2); 115 cout << "size of the class of 8: " << U.size(8) << endl; 116 check(U.size(8) == 3); 117 118 cout << "Move 7 to the class of 10 ..." << endl; 119 check(U.move(7,10)); 120 print(U); 121 122 cout << "size of the class of 7: " << U.size(7) << endl; 123 check(U.size(7) == 4); 124 125 cout <<"erase 9: " << endl; 126 U.erase(9); 127 print(U); 128 81 129 cout <<"erase 1: " << endl; 82 130 U.erase(1); … … 97 145 print(U); 98 146 99 cout << "split the class of 5: " << endl;100 U.split( 5);147 cout << "split the class of 8: " << endl; 148 U.split(8); 101 149 print(U); 102 150
Note: See TracChangeset
for help on using the changeset viewer.