[906] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
[1956] | 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2006 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
[1359] | 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
[906] | 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
[921] | 19 | #ifndef LEMON_UNION_FIND_H |
---|
| 20 | #define LEMON_UNION_FIND_H |
---|
[483] | 21 | |
---|
[491] | 22 | //!\ingroup auxdat |
---|
[483] | 23 | //!\file |
---|
| 24 | //!\brief Union-Find data structures. |
---|
[774] | 25 | //! |
---|
[483] | 26 | |
---|
| 27 | #include <vector> |
---|
| 28 | #include <list> |
---|
| 29 | #include <utility> |
---|
| 30 | #include <algorithm> |
---|
| 31 | |
---|
[921] | 32 | #include <lemon/invalid.h> |
---|
[483] | 33 | |
---|
[921] | 34 | namespace lemon { |
---|
[483] | 35 | |
---|
| 36 | //! \addtogroup auxdat |
---|
| 37 | //! @{ |
---|
| 38 | |
---|
| 39 | /** |
---|
| 40 | * \brief A \e Union-Find data structure implementation |
---|
| 41 | * |
---|
| 42 | * The class implements the \e Union-Find data structure. |
---|
| 43 | * The union operation uses rank heuristic, while |
---|
[649] | 44 | * the find operation uses path compression. |
---|
[483] | 45 | * This is a very simple but efficient implementation, providing |
---|
| 46 | * only four methods: join (union), find, insert and size. |
---|
| 47 | * For more features see the \ref UnionFindEnum class. |
---|
| 48 | * |
---|
[810] | 49 | * It is primarily used in Kruskal algorithm for finding minimal |
---|
| 50 | * cost spanning tree in a graph. |
---|
| 51 | * \sa kruskal() |
---|
| 52 | * |
---|
[483] | 53 | * \pre The elements are automatically added only if the map |
---|
| 54 | * given to the constructor was filled with -1's. Otherwise you |
---|
| 55 | * need to add all the elements by the \ref insert() method. |
---|
[810] | 56 | * \bug It is not clear what the constructor parameter is used for. |
---|
[483] | 57 | */ |
---|
| 58 | |
---|
| 59 | template <typename T, typename TIntMap> |
---|
| 60 | class UnionFind { |
---|
| 61 | |
---|
| 62 | public: |
---|
| 63 | typedef T ElementType; |
---|
| 64 | typedef std::pair<int,int> PairType; |
---|
| 65 | |
---|
| 66 | private: |
---|
| 67 | std::vector<PairType> data; |
---|
| 68 | TIntMap& map; |
---|
| 69 | |
---|
| 70 | public: |
---|
| 71 | UnionFind(TIntMap& m) : map(m) {} |
---|
| 72 | |
---|
| 73 | /** |
---|
| 74 | * \brief Returns the index of the element's component. |
---|
| 75 | * |
---|
| 76 | * The method returns the index of the element's component. |
---|
| 77 | * This is an integer between zero and the number of inserted elements. |
---|
| 78 | */ |
---|
| 79 | |
---|
| 80 | int find(T a) |
---|
| 81 | { |
---|
| 82 | int comp0 = map[a]; |
---|
| 83 | if (comp0 < 0) { |
---|
| 84 | return insert(a); |
---|
| 85 | } |
---|
| 86 | int comp = comp0; |
---|
| 87 | int next; |
---|
| 88 | while ( (next = data[comp].first) != comp) { |
---|
| 89 | comp = next; |
---|
| 90 | } |
---|
| 91 | while ( (next = data[comp0].first) != comp) { |
---|
| 92 | data[comp0].first = comp; |
---|
| 93 | comp0 = next; |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | return comp; |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | /** |
---|
[1266] | 100 | * \brief Inserts a new element into the structure. |
---|
[483] | 101 | * |
---|
| 102 | * This method inserts a new element into the data structure. |
---|
| 103 | * |
---|
| 104 | * It is not required to use this method: |
---|
| 105 | * if the map given to the constructor was filled |
---|
| 106 | * with -1's then it is called automatically |
---|
| 107 | * on the first \ref find or \ref join. |
---|
| 108 | * |
---|
| 109 | * The method returns the index of the new component. |
---|
| 110 | */ |
---|
| 111 | |
---|
| 112 | int insert(T a) |
---|
| 113 | { |
---|
| 114 | int n = data.size(); |
---|
| 115 | data.push_back(std::make_pair(n, 1)); |
---|
| 116 | map.set(a,n); |
---|
| 117 | return n; |
---|
| 118 | } |
---|
| 119 | |
---|
| 120 | /** |
---|
| 121 | * \brief Joining the components of element \e a and element \e b. |
---|
| 122 | * |
---|
| 123 | * This is the \e union operation of the Union-Find structure. |
---|
[1266] | 124 | * Joins the component of element \e a and component of |
---|
[483] | 125 | * element \e b. If \e a and \e b are in the same component then |
---|
| 126 | * it returns false otherwise it returns true. |
---|
| 127 | */ |
---|
| 128 | |
---|
| 129 | bool join(T a, T b) |
---|
| 130 | { |
---|
| 131 | int ca = find(a); |
---|
| 132 | int cb = find(b); |
---|
| 133 | |
---|
| 134 | if ( ca == cb ) |
---|
| 135 | return false; |
---|
| 136 | |
---|
| 137 | if ( data[ca].second > data[cb].second ) { |
---|
| 138 | data[cb].first = ca; |
---|
| 139 | data[ca].second += data[cb].second; |
---|
| 140 | } |
---|
| 141 | else { |
---|
| 142 | data[ca].first = cb; |
---|
| 143 | data[cb].second += data[ca].second; |
---|
| 144 | } |
---|
| 145 | return true; |
---|
| 146 | } |
---|
| 147 | |
---|
| 148 | /** |
---|
| 149 | * \brief Returns the size of the component of element \e a. |
---|
| 150 | * |
---|
| 151 | * Returns the size of the component of element \e a. |
---|
| 152 | */ |
---|
| 153 | |
---|
| 154 | int size(T a) |
---|
| 155 | { |
---|
| 156 | int ca = find(a); |
---|
| 157 | return data[ca].second; |
---|
| 158 | } |
---|
| 159 | |
---|
| 160 | }; |
---|
| 161 | |
---|
| 162 | |
---|
| 163 | |
---|
| 164 | |
---|
| 165 | /*******************************************************/ |
---|
| 166 | |
---|
| 167 | |
---|
| 168 | #ifdef DEVELOPMENT_DOCS |
---|
| 169 | |
---|
| 170 | /** |
---|
| 171 | * \brief The auxiliary class for the \ref UnionFindEnum class. |
---|
| 172 | * |
---|
| 173 | * In the \ref UnionFindEnum class all components are represented as |
---|
| 174 | * a std::list. |
---|
| 175 | * Items of these lists are UnionFindEnumItem structures. |
---|
| 176 | * |
---|
| 177 | * The class has four fields: |
---|
| 178 | * - T me - the actual element |
---|
| 179 | * - IIter parent - the parent of the element in the union-find structure |
---|
| 180 | * - int size - the size of the component of the element. |
---|
| 181 | * Only valid if the element |
---|
| 182 | * is the leader of the component. |
---|
| 183 | * - CIter my_class - pointer into the list of components |
---|
| 184 | * pointing to the component of the element. |
---|
| 185 | * Only valid if the element is the leader of the component. |
---|
| 186 | */ |
---|
| 187 | |
---|
| 188 | #endif |
---|
| 189 | |
---|
| 190 | template <typename T> |
---|
| 191 | struct UnionFindEnumItem { |
---|
| 192 | |
---|
| 193 | typedef std::list<UnionFindEnumItem> ItemList; |
---|
| 194 | typedef std::list<ItemList> ClassList; |
---|
| 195 | typedef typename ItemList::iterator IIter; |
---|
| 196 | typedef typename ClassList::iterator CIter; |
---|
| 197 | |
---|
| 198 | T me; |
---|
| 199 | IIter parent; |
---|
| 200 | int size; |
---|
| 201 | CIter my_class; |
---|
| 202 | |
---|
| 203 | UnionFindEnumItem() {} |
---|
| 204 | UnionFindEnumItem(const T &_me, CIter _my_class): |
---|
| 205 | me(_me), size(1), my_class(_my_class) {} |
---|
| 206 | }; |
---|
| 207 | |
---|
| 208 | |
---|
| 209 | /** |
---|
| 210 | * \brief A \e Union-Find data structure implementation which |
---|
| 211 | * is able to enumerate the components. |
---|
| 212 | * |
---|
[649] | 213 | * The class implements a \e Union-Find data structure |
---|
[483] | 214 | * which is able to enumerate the components and the items in |
---|
| 215 | * a component. If you don't need this feature then perhaps it's |
---|
| 216 | * better to use the \ref UnionFind class which is more efficient. |
---|
| 217 | * |
---|
| 218 | * The union operation uses rank heuristic, while |
---|
[649] | 219 | * the find operation uses path compression. |
---|
[483] | 220 | * |
---|
| 221 | * \pre You |
---|
| 222 | * need to add all the elements by the \ref insert() method. |
---|
| 223 | */ |
---|
| 224 | |
---|
| 225 | |
---|
| 226 | template <typename T, template <typename Item> class Map> |
---|
| 227 | class UnionFindEnum { |
---|
| 228 | |
---|
| 229 | typedef std::list<UnionFindEnumItem<T> > ItemList; |
---|
| 230 | typedef std::list<ItemList> ClassList; |
---|
| 231 | typedef typename ItemList::iterator IIter; |
---|
| 232 | typedef typename ItemList::const_iterator IcIter; |
---|
| 233 | typedef typename ClassList::iterator CIter; |
---|
| 234 | typedef typename ClassList::const_iterator CcIter; |
---|
| 235 | |
---|
| 236 | public: |
---|
| 237 | typedef T ElementType; |
---|
| 238 | typedef UnionFindEnumItem<T> ItemType; |
---|
| 239 | typedef Map< IIter > MapType; |
---|
| 240 | |
---|
| 241 | private: |
---|
| 242 | MapType& m; |
---|
| 243 | ClassList classes; |
---|
| 244 | |
---|
| 245 | IIter _find(IIter a) const { |
---|
| 246 | IIter comp = a; |
---|
| 247 | IIter next; |
---|
| 248 | while( (next = comp->parent) != comp ) { |
---|
| 249 | comp = next; |
---|
| 250 | } |
---|
| 251 | |
---|
| 252 | IIter comp1 = a; |
---|
| 253 | while( (next = comp1->parent) != comp ) { |
---|
| 254 | comp1->parent = comp->parent; |
---|
| 255 | comp1 = next; |
---|
| 256 | } |
---|
| 257 | return comp; |
---|
| 258 | } |
---|
| 259 | |
---|
| 260 | public: |
---|
| 261 | UnionFindEnum(MapType& _m) : m(_m) {} |
---|
| 262 | |
---|
| 263 | |
---|
| 264 | /** |
---|
[1266] | 265 | * \brief Inserts the given element into a new component. |
---|
[483] | 266 | * |
---|
| 267 | * This method creates a new component consisting only of the |
---|
| 268 | * given element. |
---|
| 269 | */ |
---|
| 270 | |
---|
| 271 | void insert(const T &a) |
---|
| 272 | { |
---|
| 273 | |
---|
| 274 | |
---|
| 275 | classes.push_back(ItemList()); |
---|
| 276 | CIter aclass = classes.end(); |
---|
| 277 | --aclass; |
---|
| 278 | |
---|
| 279 | ItemList &alist = *aclass; |
---|
| 280 | alist.push_back(ItemType(a, aclass)); |
---|
| 281 | IIter ai = alist.begin(); |
---|
| 282 | |
---|
| 283 | ai->parent = ai; |
---|
| 284 | m.set(a, ai); |
---|
| 285 | |
---|
| 286 | } |
---|
| 287 | |
---|
| 288 | /** |
---|
[1266] | 289 | * \brief Inserts the given element into the component of the others. |
---|
[483] | 290 | * |
---|
[1266] | 291 | * This methods inserts the element \e a into the component of the |
---|
[483] | 292 | * element \e comp. |
---|
| 293 | */ |
---|
| 294 | |
---|
| 295 | void insert(const T &a, const T &comp) { |
---|
| 296 | |
---|
| 297 | IIter clit = _find(m[comp]); |
---|
| 298 | ItemList &c = *clit->my_class; |
---|
| 299 | c.push_back(ItemType(a,0)); |
---|
| 300 | IIter ai = c.end(); |
---|
| 301 | --ai; |
---|
| 302 | ai->parent = clit; |
---|
| 303 | m.set(a, ai); |
---|
| 304 | ++clit->size; |
---|
| 305 | } |
---|
| 306 | |
---|
| 307 | |
---|
| 308 | /** |
---|
[1266] | 309 | * \brief Finds the leader of the component of the given element. |
---|
[483] | 310 | * |
---|
| 311 | * The method returns the leader of the component of the given element. |
---|
| 312 | */ |
---|
| 313 | |
---|
| 314 | T find(const T &a) const { |
---|
| 315 | return _find(m[a])->me; |
---|
| 316 | } |
---|
| 317 | |
---|
| 318 | |
---|
| 319 | /** |
---|
| 320 | * \brief Joining the component of element \e a and element \e b. |
---|
| 321 | * |
---|
| 322 | * This is the \e union operation of the Union-Find structure. |
---|
[1266] | 323 | * Joins the component of element \e a and component of |
---|
[483] | 324 | * element \e b. If \e a and \e b are in the same component then |
---|
| 325 | * returns false else returns true. |
---|
| 326 | */ |
---|
| 327 | |
---|
| 328 | bool join(T a, T b) { |
---|
| 329 | |
---|
| 330 | IIter ca = _find(m[a]); |
---|
| 331 | IIter cb = _find(m[b]); |
---|
| 332 | |
---|
| 333 | if ( ca == cb ) { |
---|
| 334 | return false; |
---|
| 335 | } |
---|
| 336 | |
---|
| 337 | if ( ca->size > cb->size ) { |
---|
| 338 | |
---|
| 339 | cb->parent = ca->parent; |
---|
| 340 | ca->size += cb->size; |
---|
| 341 | |
---|
| 342 | ItemList &alist = *ca->my_class; |
---|
| 343 | alist.splice(alist.end(),*cb->my_class); |
---|
| 344 | |
---|
| 345 | classes.erase(cb->my_class); |
---|
| 346 | cb->my_class = 0; |
---|
| 347 | } |
---|
| 348 | else { |
---|
| 349 | |
---|
| 350 | ca->parent = cb->parent; |
---|
| 351 | cb->size += ca->size; |
---|
| 352 | |
---|
| 353 | ItemList &blist = *cb->my_class; |
---|
| 354 | blist.splice(blist.end(),*ca->my_class); |
---|
| 355 | |
---|
| 356 | classes.erase(ca->my_class); |
---|
| 357 | ca->my_class = 0; |
---|
| 358 | } |
---|
| 359 | |
---|
| 360 | return true; |
---|
| 361 | } |
---|
| 362 | |
---|
| 363 | |
---|
| 364 | /** |
---|
| 365 | * \brief Returns the size of the component of element \e a. |
---|
| 366 | * |
---|
| 367 | * Returns the size of the component of element \e a. |
---|
| 368 | */ |
---|
| 369 | |
---|
| 370 | int size(const T &a) const { |
---|
| 371 | return _find(m[a])->size; |
---|
| 372 | } |
---|
| 373 | |
---|
| 374 | |
---|
| 375 | /** |
---|
[1266] | 376 | * \brief Splits up the component of the element. |
---|
[483] | 377 | * |
---|
| 378 | * Splitting the component of the element into sigleton |
---|
| 379 | * components (component of size one). |
---|
| 380 | */ |
---|
| 381 | |
---|
| 382 | void split(const T &a) { |
---|
| 383 | |
---|
| 384 | IIter ca = _find(m[a]); |
---|
| 385 | |
---|
| 386 | if ( ca->size == 1 ) |
---|
| 387 | return; |
---|
| 388 | |
---|
| 389 | CIter aclass = ca->my_class; |
---|
| 390 | |
---|
| 391 | for(IIter curr = ca; ++curr != aclass->end(); curr=ca) { |
---|
| 392 | classes.push_back(ItemList()); |
---|
| 393 | CIter nl = --classes.end(); |
---|
| 394 | nl->splice(nl->end(), *aclass, curr); |
---|
| 395 | |
---|
| 396 | curr->size=1; |
---|
| 397 | curr->parent=curr; |
---|
| 398 | curr->my_class = nl; |
---|
| 399 | } |
---|
| 400 | |
---|
| 401 | ca->size=1; |
---|
| 402 | return; |
---|
| 403 | } |
---|
| 404 | |
---|
| 405 | |
---|
| 406 | /** |
---|
[1266] | 407 | * \brief Sets the given element to the leader element of its component. |
---|
[483] | 408 | * |
---|
[1266] | 409 | * Sets the given element to the leader element of its component. |
---|
[483] | 410 | */ |
---|
| 411 | |
---|
| 412 | void makeRep(const T &a) { |
---|
| 413 | |
---|
| 414 | IIter ia = m[a]; |
---|
| 415 | IIter la = _find(ia); |
---|
| 416 | if (la == ia) return; |
---|
| 417 | |
---|
| 418 | ia->my_class = la->my_class; |
---|
| 419 | la->my_class = 0; |
---|
| 420 | |
---|
| 421 | ia->size = la->size; |
---|
| 422 | |
---|
| 423 | CIter l = ia->my_class; |
---|
| 424 | l->splice(l->begin(),*l,ia); |
---|
| 425 | |
---|
| 426 | ia->parent = ia; |
---|
| 427 | la->parent = ia; |
---|
| 428 | } |
---|
| 429 | |
---|
| 430 | /** |
---|
[1266] | 431 | * \brief Moves the given element to an other component. |
---|
[483] | 432 | * |
---|
| 433 | * This method moves the element \e a from its component |
---|
| 434 | * to the component of \e comp. |
---|
| 435 | * If \e a and \e comp are in the same component then |
---|
| 436 | * it returns false otherwise it returns true. |
---|
| 437 | */ |
---|
| 438 | |
---|
| 439 | bool move(const T &a, const T &comp) { |
---|
| 440 | |
---|
| 441 | IIter ai = m[a]; |
---|
| 442 | IIter lai = _find(ai); |
---|
| 443 | IIter clit = _find(m[comp]); |
---|
| 444 | |
---|
| 445 | if (lai == clit) |
---|
| 446 | return false; |
---|
| 447 | |
---|
[914] | 448 | ItemList &cl = *clit->my_class, |
---|
| 449 | &al = *lai->my_class; |
---|
[483] | 450 | |
---|
| 451 | bool is_leader = (lai == ai); |
---|
| 452 | bool singleton = false; |
---|
| 453 | |
---|
| 454 | if (is_leader) { |
---|
| 455 | ++lai; |
---|
| 456 | } |
---|
| 457 | |
---|
[914] | 458 | cl.splice(cl.end(), al, ai); |
---|
[483] | 459 | |
---|
| 460 | if (is_leader) { |
---|
| 461 | if (ai->size == 1) { |
---|
| 462 | classes.erase(ai->my_class); |
---|
| 463 | singleton = true; |
---|
| 464 | } |
---|
| 465 | else { |
---|
| 466 | lai->size = ai->size; |
---|
| 467 | lai->my_class = ai->my_class; |
---|
| 468 | } |
---|
| 469 | } |
---|
| 470 | if (!singleton) { |
---|
[914] | 471 | for (IIter i = lai; i != al.end(); ++i) |
---|
[483] | 472 | i->parent = lai; |
---|
| 473 | --lai->size; |
---|
| 474 | } |
---|
| 475 | |
---|
| 476 | ai->parent = clit; |
---|
| 477 | ai->my_class = 0; |
---|
| 478 | ++clit->size; |
---|
| 479 | |
---|
| 480 | return true; |
---|
| 481 | } |
---|
| 482 | |
---|
| 483 | |
---|
| 484 | /** |
---|
[1266] | 485 | * \brief Removes the given element from the structure. |
---|
[483] | 486 | * |
---|
[1266] | 487 | * Removes the given element from the structure. |
---|
[483] | 488 | * |
---|
| 489 | * Removes the element from its component and if the component becomes |
---|
| 490 | * empty then removes that component from the component list. |
---|
| 491 | */ |
---|
| 492 | void erase(const T &a) { |
---|
| 493 | |
---|
| 494 | IIter ma = m[a]; |
---|
| 495 | if (ma == 0) return; |
---|
| 496 | |
---|
| 497 | IIter la = _find(ma); |
---|
| 498 | if (la == ma) { |
---|
| 499 | if (ma -> size == 1){ |
---|
| 500 | classes.erase(ma->my_class); |
---|
| 501 | m.set(a,0); |
---|
| 502 | return; |
---|
| 503 | } |
---|
| 504 | ++la; |
---|
| 505 | la->size = ma->size; |
---|
| 506 | la->my_class = ma->my_class; |
---|
| 507 | } |
---|
| 508 | |
---|
| 509 | for (IIter i = la; i != la->my_class->end(); ++i) { |
---|
| 510 | i->parent = la; |
---|
| 511 | } |
---|
| 512 | |
---|
| 513 | la->size--; |
---|
| 514 | la->my_class->erase(ma); |
---|
| 515 | m.set(a,0); |
---|
| 516 | } |
---|
| 517 | |
---|
| 518 | /** |
---|
| 519 | * \brief Removes the component of the given element from the structure. |
---|
| 520 | * |
---|
| 521 | * Removes the component of the given element from the structure. |
---|
| 522 | */ |
---|
| 523 | |
---|
| 524 | void eraseClass(const T &a) { |
---|
| 525 | IIter ma = m[a]; |
---|
| 526 | if (ma == 0) return; |
---|
| 527 | # ifdef DEBUG |
---|
| 528 | CIter c = _find(ma)->my_class; |
---|
| 529 | for (IIter i=c->begin(); i!=c->end(); ++i) |
---|
| 530 | m.set(i->me, 0); |
---|
| 531 | # endif |
---|
| 532 | classes.erase(_find(ma)->my_class); |
---|
| 533 | } |
---|
| 534 | |
---|
| 535 | |
---|
| 536 | class ClassIt { |
---|
| 537 | friend class UnionFindEnum; |
---|
| 538 | |
---|
| 539 | CcIter i; |
---|
| 540 | public: |
---|
| 541 | ClassIt(Invalid): i(0) {} |
---|
| 542 | ClassIt() {} |
---|
| 543 | |
---|
| 544 | operator const T& () const { |
---|
| 545 | ItemList const &ll = *i; |
---|
| 546 | return (ll.begin())->me; } |
---|
| 547 | bool operator == (ClassIt it) const { |
---|
| 548 | return (i == it.i); |
---|
| 549 | } |
---|
| 550 | bool operator != (ClassIt it) const { |
---|
| 551 | return (i != it.i); |
---|
| 552 | } |
---|
| 553 | bool operator < (ClassIt it) const { |
---|
| 554 | return (i < it.i); |
---|
| 555 | } |
---|
| 556 | |
---|
| 557 | bool valid() const { return i != 0; } |
---|
| 558 | private: |
---|
| 559 | void first(const ClassList &l) { i = l.begin(); validate(l); } |
---|
| 560 | void next(const ClassList &l) { |
---|
| 561 | ++i; |
---|
| 562 | validate(l); |
---|
| 563 | } |
---|
| 564 | void validate(const ClassList &l) { |
---|
| 565 | if ( i == l.end() ) |
---|
| 566 | i = 0; |
---|
| 567 | } |
---|
| 568 | }; |
---|
| 569 | |
---|
| 570 | /** |
---|
| 571 | * \brief Sets the iterator to point to the first component. |
---|
| 572 | * |
---|
| 573 | * Sets the iterator to point to the first component. |
---|
| 574 | * |
---|
| 575 | * With the \ref first, \ref valid and \ref next methods you can |
---|
| 576 | * iterate through the components. For example: |
---|
| 577 | * \code |
---|
| 578 | * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G); |
---|
| 579 | * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map); |
---|
| 580 | * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter; |
---|
| 581 | * for (U.first(iter); U.valid(iter); U.next(iter)) { |
---|
| 582 | * // iter is convertible to Graph::Node |
---|
| 583 | * cout << iter << endl; |
---|
| 584 | * } |
---|
| 585 | * \endcode |
---|
| 586 | */ |
---|
| 587 | |
---|
| 588 | ClassIt& first(ClassIt& it) const { |
---|
| 589 | it.first(classes); |
---|
| 590 | return it; |
---|
| 591 | } |
---|
| 592 | |
---|
| 593 | /** |
---|
| 594 | * \brief Returns whether the iterator is valid. |
---|
| 595 | * |
---|
| 596 | * Returns whether the iterator is valid. |
---|
| 597 | * |
---|
| 598 | * With the \ref first, \ref valid and \ref next methods you can |
---|
| 599 | * iterate through the components. See the example here: \ref first. |
---|
| 600 | */ |
---|
| 601 | |
---|
| 602 | bool valid(ClassIt const &it) const { |
---|
| 603 | return it.valid(); |
---|
| 604 | } |
---|
| 605 | |
---|
| 606 | /** |
---|
| 607 | * \brief Steps the iterator to the next component. |
---|
| 608 | * |
---|
| 609 | * Steps the iterator to the next component. |
---|
| 610 | * |
---|
| 611 | * With the \ref first, \ref valid and \ref next methods you can |
---|
| 612 | * iterate through the components. See the example here: \ref first. |
---|
| 613 | */ |
---|
| 614 | |
---|
| 615 | ClassIt& next(ClassIt& it) const { |
---|
| 616 | it.next(classes); |
---|
| 617 | return it; |
---|
| 618 | } |
---|
| 619 | |
---|
| 620 | |
---|
| 621 | class ItemIt { |
---|
| 622 | friend class UnionFindEnum; |
---|
| 623 | |
---|
| 624 | IcIter i; |
---|
| 625 | const ItemList *l; |
---|
| 626 | public: |
---|
| 627 | ItemIt(Invalid): i(0) {} |
---|
| 628 | ItemIt() {} |
---|
| 629 | |
---|
| 630 | operator const T& () const { return i->me; } |
---|
| 631 | bool operator == (ItemIt it) const { |
---|
| 632 | return (i == it.i); |
---|
| 633 | } |
---|
| 634 | bool operator != (ItemIt it) const { |
---|
| 635 | return (i != it.i); |
---|
| 636 | } |
---|
| 637 | bool operator < (ItemIt it) const { |
---|
| 638 | return (i < it.i); |
---|
| 639 | } |
---|
| 640 | |
---|
| 641 | bool valid() const { return i != 0; } |
---|
| 642 | private: |
---|
| 643 | void first(const ItemList &il) { l=&il; i = l->begin(); validate(); } |
---|
| 644 | void next() { |
---|
| 645 | ++i; |
---|
| 646 | validate(); |
---|
| 647 | } |
---|
| 648 | void validate() { |
---|
| 649 | if ( i == l->end() ) |
---|
| 650 | i = 0; |
---|
| 651 | } |
---|
| 652 | }; |
---|
| 653 | |
---|
| 654 | |
---|
| 655 | |
---|
| 656 | /** |
---|
| 657 | * \brief Sets the iterator to point to the first element of the component. |
---|
| 658 | * |
---|
| 659 | * \anchor first2 |
---|
| 660 | * Sets the iterator to point to the first element of the component. |
---|
| 661 | * |
---|
| 662 | * With the \ref first2 "first", \ref valid2 "valid" |
---|
| 663 | * and \ref next2 "next" methods you can |
---|
| 664 | * iterate through the elements of a component. For example |
---|
| 665 | * (iterating through the component of the node \e node): |
---|
| 666 | * \code |
---|
| 667 | * Graph::Node node = ...; |
---|
| 668 | * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G); |
---|
| 669 | * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map); |
---|
| 670 | * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter; |
---|
| 671 | * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) { |
---|
| 672 | * // iiter is convertible to Graph::Node |
---|
| 673 | * cout << iiter << endl; |
---|
| 674 | * } |
---|
| 675 | * \endcode |
---|
| 676 | */ |
---|
| 677 | |
---|
| 678 | ItemIt& first(ItemIt& it, const T& a) const { |
---|
| 679 | it.first( * _find(m[a])->my_class ); |
---|
| 680 | return it; |
---|
| 681 | } |
---|
| 682 | |
---|
| 683 | /** |
---|
| 684 | * \brief Returns whether the iterator is valid. |
---|
| 685 | * |
---|
| 686 | * \anchor valid2 |
---|
| 687 | * Returns whether the iterator is valid. |
---|
| 688 | * |
---|
| 689 | * With the \ref first2 "first", \ref valid2 "valid" |
---|
| 690 | * and \ref next2 "next" methods you can |
---|
| 691 | * iterate through the elements of a component. |
---|
| 692 | * See the example here: \ref first2 "first". |
---|
| 693 | */ |
---|
| 694 | |
---|
| 695 | bool valid(ItemIt const &it) const { |
---|
| 696 | return it.valid(); |
---|
| 697 | } |
---|
| 698 | |
---|
| 699 | /** |
---|
| 700 | * \brief Steps the iterator to the next component. |
---|
| 701 | * |
---|
| 702 | * \anchor next2 |
---|
| 703 | * Steps the iterator to the next component. |
---|
| 704 | * |
---|
| 705 | * With the \ref first2 "first", \ref valid2 "valid" |
---|
| 706 | * and \ref next2 "next" methods you can |
---|
| 707 | * iterate through the elements of a component. |
---|
| 708 | * See the example here: \ref first2 "first". |
---|
| 709 | */ |
---|
| 710 | |
---|
| 711 | ItemIt& next(ItemIt& it) const { |
---|
| 712 | it.next(); |
---|
| 713 | return it; |
---|
| 714 | } |
---|
| 715 | |
---|
| 716 | }; |
---|
| 717 | |
---|
| 718 | |
---|
| 719 | //! @} |
---|
| 720 | |
---|
[921] | 721 | } //namespace lemon |
---|
[483] | 722 | |
---|
[921] | 723 | #endif //LEMON_UNION_FIND_H |
---|