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