1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/unionfind.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,724 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/unionfind.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_UNION_FIND_H
1.21 +#define LEMON_UNION_FIND_H
1.22 +
1.23 +//!\ingroup auxdat
1.24 +//!\file
1.25 +//!\brief Union-Find data structures.
1.26 +//!
1.27 +//!\bug unionfind_test.cc doesn't work with Intel compiler. It compiles but
1.28 +//!fails to run (Segmentation fault).
1.29 +
1.30 +
1.31 +#include <vector>
1.32 +#include <list>
1.33 +#include <utility>
1.34 +#include <algorithm>
1.35 +
1.36 +#include <lemon/invalid.h>
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + //! \addtogroup auxdat
1.41 + //! @{
1.42 +
1.43 + /**
1.44 + * \brief A \e Union-Find data structure implementation
1.45 + *
1.46 + * The class implements the \e Union-Find data structure.
1.47 + * The union operation uses rank heuristic, while
1.48 + * the find operation uses path compression.
1.49 + * This is a very simple but efficient implementation, providing
1.50 + * only four methods: join (union), find, insert and size.
1.51 + * For more features see the \ref UnionFindEnum class.
1.52 + *
1.53 + * It is primarily used in Kruskal algorithm for finding minimal
1.54 + * cost spanning tree in a graph.
1.55 + * \sa kruskal()
1.56 + *
1.57 + * \pre The elements are automatically added only if the map
1.58 + * given to the constructor was filled with -1's. Otherwise you
1.59 + * need to add all the elements by the \ref insert() method.
1.60 + * \bug It is not clear what the constructor parameter is used for.
1.61 + */
1.62 +
1.63 + template <typename T, typename TIntMap>
1.64 + class UnionFind {
1.65 +
1.66 + public:
1.67 + typedef T ElementType;
1.68 + typedef std::pair<int,int> PairType;
1.69 +
1.70 + private:
1.71 + std::vector<PairType> data;
1.72 + TIntMap& map;
1.73 +
1.74 + public:
1.75 + UnionFind(TIntMap& m) : map(m) {}
1.76 +
1.77 + /**
1.78 + * \brief Returns the index of the element's component.
1.79 + *
1.80 + * The method returns the index of the element's component.
1.81 + * This is an integer between zero and the number of inserted elements.
1.82 + */
1.83 +
1.84 + int find(T a)
1.85 + {
1.86 + int comp0 = map[a];
1.87 + if (comp0 < 0) {
1.88 + return insert(a);
1.89 + }
1.90 + int comp = comp0;
1.91 + int next;
1.92 + while ( (next = data[comp].first) != comp) {
1.93 + comp = next;
1.94 + }
1.95 + while ( (next = data[comp0].first) != comp) {
1.96 + data[comp0].first = comp;
1.97 + comp0 = next;
1.98 + }
1.99 +
1.100 + return comp;
1.101 + }
1.102 +
1.103 + /**
1.104 + * \brief Insert a new element into the structure.
1.105 + *
1.106 + * This method inserts a new element into the data structure.
1.107 + *
1.108 + * It is not required to use this method:
1.109 + * if the map given to the constructor was filled
1.110 + * with -1's then it is called automatically
1.111 + * on the first \ref find or \ref join.
1.112 + *
1.113 + * The method returns the index of the new component.
1.114 + */
1.115 +
1.116 + int insert(T a)
1.117 + {
1.118 + int n = data.size();
1.119 + data.push_back(std::make_pair(n, 1));
1.120 + map.set(a,n);
1.121 + return n;
1.122 + }
1.123 +
1.124 + /**
1.125 + * \brief Joining the components of element \e a and element \e b.
1.126 + *
1.127 + * This is the \e union operation of the Union-Find structure.
1.128 + * Joins the component of elemenent \e a and component of
1.129 + * element \e b. If \e a and \e b are in the same component then
1.130 + * it returns false otherwise it returns true.
1.131 + */
1.132 +
1.133 + bool join(T a, T b)
1.134 + {
1.135 + int ca = find(a);
1.136 + int cb = find(b);
1.137 +
1.138 + if ( ca == cb )
1.139 + return false;
1.140 +
1.141 + if ( data[ca].second > data[cb].second ) {
1.142 + data[cb].first = ca;
1.143 + data[ca].second += data[cb].second;
1.144 + }
1.145 + else {
1.146 + data[ca].first = cb;
1.147 + data[cb].second += data[ca].second;
1.148 + }
1.149 + return true;
1.150 + }
1.151 +
1.152 + /**
1.153 + * \brief Returns the size of the component of element \e a.
1.154 + *
1.155 + * Returns the size of the component of element \e a.
1.156 + */
1.157 +
1.158 + int size(T a)
1.159 + {
1.160 + int ca = find(a);
1.161 + return data[ca].second;
1.162 + }
1.163 +
1.164 + };
1.165 +
1.166 +
1.167 +
1.168 +
1.169 + /*******************************************************/
1.170 +
1.171 +
1.172 +#ifdef DEVELOPMENT_DOCS
1.173 +
1.174 + /**
1.175 + * \brief The auxiliary class for the \ref UnionFindEnum class.
1.176 + *
1.177 + * In the \ref UnionFindEnum class all components are represented as
1.178 + * a std::list.
1.179 + * Items of these lists are UnionFindEnumItem structures.
1.180 + *
1.181 + * The class has four fields:
1.182 + * - T me - the actual element
1.183 + * - IIter parent - the parent of the element in the union-find structure
1.184 + * - int size - the size of the component of the element.
1.185 + * Only valid if the element
1.186 + * is the leader of the component.
1.187 + * - CIter my_class - pointer into the list of components
1.188 + * pointing to the component of the element.
1.189 + * Only valid if the element is the leader of the component.
1.190 + */
1.191 +
1.192 +#endif
1.193 +
1.194 + template <typename T>
1.195 + struct UnionFindEnumItem {
1.196 +
1.197 + typedef std::list<UnionFindEnumItem> ItemList;
1.198 + typedef std::list<ItemList> ClassList;
1.199 + typedef typename ItemList::iterator IIter;
1.200 + typedef typename ClassList::iterator CIter;
1.201 +
1.202 + T me;
1.203 + IIter parent;
1.204 + int size;
1.205 + CIter my_class;
1.206 +
1.207 + UnionFindEnumItem() {}
1.208 + UnionFindEnumItem(const T &_me, CIter _my_class):
1.209 + me(_me), size(1), my_class(_my_class) {}
1.210 + };
1.211 +
1.212 +
1.213 + /**
1.214 + * \brief A \e Union-Find data structure implementation which
1.215 + * is able to enumerate the components.
1.216 + *
1.217 + * The class implements a \e Union-Find data structure
1.218 + * which is able to enumerate the components and the items in
1.219 + * a component. If you don't need this feature then perhaps it's
1.220 + * better to use the \ref UnionFind class which is more efficient.
1.221 + *
1.222 + * The union operation uses rank heuristic, while
1.223 + * the find operation uses path compression.
1.224 + *
1.225 + * \pre You
1.226 + * need to add all the elements by the \ref insert() method.
1.227 + */
1.228 +
1.229 +
1.230 + template <typename T, template <typename Item> class Map>
1.231 + class UnionFindEnum {
1.232 +
1.233 + typedef std::list<UnionFindEnumItem<T> > ItemList;
1.234 + typedef std::list<ItemList> ClassList;
1.235 + typedef typename ItemList::iterator IIter;
1.236 + typedef typename ItemList::const_iterator IcIter;
1.237 + typedef typename ClassList::iterator CIter;
1.238 + typedef typename ClassList::const_iterator CcIter;
1.239 +
1.240 + public:
1.241 + typedef T ElementType;
1.242 + typedef UnionFindEnumItem<T> ItemType;
1.243 + typedef Map< IIter > MapType;
1.244 +
1.245 + private:
1.246 + MapType& m;
1.247 + ClassList classes;
1.248 +
1.249 + IIter _find(IIter a) const {
1.250 + IIter comp = a;
1.251 + IIter next;
1.252 + while( (next = comp->parent) != comp ) {
1.253 + comp = next;
1.254 + }
1.255 +
1.256 + IIter comp1 = a;
1.257 + while( (next = comp1->parent) != comp ) {
1.258 + comp1->parent = comp->parent;
1.259 + comp1 = next;
1.260 + }
1.261 + return comp;
1.262 + }
1.263 +
1.264 + public:
1.265 + UnionFindEnum(MapType& _m) : m(_m) {}
1.266 +
1.267 +
1.268 + /**
1.269 + * \brief Insert the given element into a new component.
1.270 + *
1.271 + * This method creates a new component consisting only of the
1.272 + * given element.
1.273 + */
1.274 +
1.275 + void insert(const T &a)
1.276 + {
1.277 +
1.278 +
1.279 + classes.push_back(ItemList());
1.280 + CIter aclass = classes.end();
1.281 + --aclass;
1.282 +
1.283 + ItemList &alist = *aclass;
1.284 + alist.push_back(ItemType(a, aclass));
1.285 + IIter ai = alist.begin();
1.286 +
1.287 + ai->parent = ai;
1.288 + m.set(a, ai);
1.289 +
1.290 + }
1.291 +
1.292 + /**
1.293 + * \brief Insert the given element into the component of the others.
1.294 + *
1.295 + * This methods insert the element \e a into the component of the
1.296 + * element \e comp.
1.297 + */
1.298 +
1.299 + void insert(const T &a, const T &comp) {
1.300 +
1.301 + IIter clit = _find(m[comp]);
1.302 + ItemList &c = *clit->my_class;
1.303 + c.push_back(ItemType(a,0));
1.304 + IIter ai = c.end();
1.305 + --ai;
1.306 + ai->parent = clit;
1.307 + m.set(a, ai);
1.308 + ++clit->size;
1.309 + }
1.310 +
1.311 +
1.312 + /**
1.313 + * \brief Find the leader of the component of the given element.
1.314 + *
1.315 + * The method returns the leader of the component of the given element.
1.316 + */
1.317 +
1.318 + T find(const T &a) const {
1.319 + return _find(m[a])->me;
1.320 + }
1.321 +
1.322 +
1.323 + /**
1.324 + * \brief Joining the component of element \e a and element \e b.
1.325 + *
1.326 + * This is the \e union operation of the Union-Find structure.
1.327 + * Joins the component of elemenent \e a and component of
1.328 + * element \e b. If \e a and \e b are in the same component then
1.329 + * returns false else returns true.
1.330 + */
1.331 +
1.332 + bool join(T a, T b) {
1.333 +
1.334 + IIter ca = _find(m[a]);
1.335 + IIter cb = _find(m[b]);
1.336 +
1.337 + if ( ca == cb ) {
1.338 + return false;
1.339 + }
1.340 +
1.341 + if ( ca->size > cb->size ) {
1.342 +
1.343 + cb->parent = ca->parent;
1.344 + ca->size += cb->size;
1.345 +
1.346 + ItemList &alist = *ca->my_class;
1.347 + alist.splice(alist.end(),*cb->my_class);
1.348 +
1.349 + classes.erase(cb->my_class);
1.350 + cb->my_class = 0;
1.351 + }
1.352 + else {
1.353 +
1.354 + ca->parent = cb->parent;
1.355 + cb->size += ca->size;
1.356 +
1.357 + ItemList &blist = *cb->my_class;
1.358 + blist.splice(blist.end(),*ca->my_class);
1.359 +
1.360 + classes.erase(ca->my_class);
1.361 + ca->my_class = 0;
1.362 + }
1.363 +
1.364 + return true;
1.365 + }
1.366 +
1.367 +
1.368 + /**
1.369 + * \brief Returns the size of the component of element \e a.
1.370 + *
1.371 + * Returns the size of the component of element \e a.
1.372 + */
1.373 +
1.374 + int size(const T &a) const {
1.375 + return _find(m[a])->size;
1.376 + }
1.377 +
1.378 +
1.379 + /**
1.380 + * \brief Split up the component of the element.
1.381 + *
1.382 + * Splitting the component of the element into sigleton
1.383 + * components (component of size one).
1.384 + */
1.385 +
1.386 + void split(const T &a) {
1.387 +
1.388 + IIter ca = _find(m[a]);
1.389 +
1.390 + if ( ca->size == 1 )
1.391 + return;
1.392 +
1.393 + CIter aclass = ca->my_class;
1.394 +
1.395 + for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
1.396 + classes.push_back(ItemList());
1.397 + CIter nl = --classes.end();
1.398 + nl->splice(nl->end(), *aclass, curr);
1.399 +
1.400 + curr->size=1;
1.401 + curr->parent=curr;
1.402 + curr->my_class = nl;
1.403 + }
1.404 +
1.405 + ca->size=1;
1.406 + return;
1.407 + }
1.408 +
1.409 +
1.410 + /**
1.411 + * \brief Set the given element to the leader element of its component.
1.412 + *
1.413 + * Set the given element to the leader element of its component.
1.414 + */
1.415 +
1.416 + void makeRep(const T &a) {
1.417 +
1.418 + IIter ia = m[a];
1.419 + IIter la = _find(ia);
1.420 + if (la == ia) return;
1.421 +
1.422 + ia->my_class = la->my_class;
1.423 + la->my_class = 0;
1.424 +
1.425 + ia->size = la->size;
1.426 +
1.427 + CIter l = ia->my_class;
1.428 + l->splice(l->begin(),*l,ia);
1.429 +
1.430 + ia->parent = ia;
1.431 + la->parent = ia;
1.432 + }
1.433 +
1.434 + /**
1.435 + * \brief Move the given element to an other component.
1.436 + *
1.437 + * This method moves the element \e a from its component
1.438 + * to the component of \e comp.
1.439 + * If \e a and \e comp are in the same component then
1.440 + * it returns false otherwise it returns true.
1.441 + */
1.442 +
1.443 + bool move(const T &a, const T &comp) {
1.444 +
1.445 + IIter ai = m[a];
1.446 + IIter lai = _find(ai);
1.447 + IIter clit = _find(m[comp]);
1.448 +
1.449 + if (lai == clit)
1.450 + return false;
1.451 +
1.452 + ItemList &cl = *clit->my_class,
1.453 + &al = *lai->my_class;
1.454 +
1.455 + bool is_leader = (lai == ai);
1.456 + bool singleton = false;
1.457 +
1.458 + if (is_leader) {
1.459 + ++lai;
1.460 + }
1.461 +
1.462 + cl.splice(cl.end(), al, ai);
1.463 +
1.464 + if (is_leader) {
1.465 + if (ai->size == 1) {
1.466 + classes.erase(ai->my_class);
1.467 + singleton = true;
1.468 + }
1.469 + else {
1.470 + lai->size = ai->size;
1.471 + lai->my_class = ai->my_class;
1.472 + }
1.473 + }
1.474 + if (!singleton) {
1.475 + for (IIter i = lai; i != al.end(); ++i)
1.476 + i->parent = lai;
1.477 + --lai->size;
1.478 + }
1.479 +
1.480 + ai->parent = clit;
1.481 + ai->my_class = 0;
1.482 + ++clit->size;
1.483 +
1.484 + return true;
1.485 + }
1.486 +
1.487 +
1.488 + /**
1.489 + * \brief Remove the given element from the structure.
1.490 + *
1.491 + * Remove the given element from the structure.
1.492 + *
1.493 + * Removes the element from its component and if the component becomes
1.494 + * empty then removes that component from the component list.
1.495 + */
1.496 + void erase(const T &a) {
1.497 +
1.498 + IIter ma = m[a];
1.499 + if (ma == 0) return;
1.500 +
1.501 + IIter la = _find(ma);
1.502 + if (la == ma) {
1.503 + if (ma -> size == 1){
1.504 + classes.erase(ma->my_class);
1.505 + m.set(a,0);
1.506 + return;
1.507 + }
1.508 + ++la;
1.509 + la->size = ma->size;
1.510 + la->my_class = ma->my_class;
1.511 + }
1.512 +
1.513 + for (IIter i = la; i != la->my_class->end(); ++i) {
1.514 + i->parent = la;
1.515 + }
1.516 +
1.517 + la->size--;
1.518 + la->my_class->erase(ma);
1.519 + m.set(a,0);
1.520 + }
1.521 +
1.522 + /**
1.523 + * \brief Removes the component of the given element from the structure.
1.524 + *
1.525 + * Removes the component of the given element from the structure.
1.526 + */
1.527 +
1.528 + void eraseClass(const T &a) {
1.529 + IIter ma = m[a];
1.530 + if (ma == 0) return;
1.531 +# ifdef DEBUG
1.532 + CIter c = _find(ma)->my_class;
1.533 + for (IIter i=c->begin(); i!=c->end(); ++i)
1.534 + m.set(i->me, 0);
1.535 +# endif
1.536 + classes.erase(_find(ma)->my_class);
1.537 + }
1.538 +
1.539 +
1.540 + class ClassIt {
1.541 + friend class UnionFindEnum;
1.542 +
1.543 + CcIter i;
1.544 + public:
1.545 + ClassIt(Invalid): i(0) {}
1.546 + ClassIt() {}
1.547 +
1.548 + operator const T& () const {
1.549 + ItemList const &ll = *i;
1.550 + return (ll.begin())->me; }
1.551 + bool operator == (ClassIt it) const {
1.552 + return (i == it.i);
1.553 + }
1.554 + bool operator != (ClassIt it) const {
1.555 + return (i != it.i);
1.556 + }
1.557 + bool operator < (ClassIt it) const {
1.558 + return (i < it.i);
1.559 + }
1.560 +
1.561 + bool valid() const { return i != 0; }
1.562 + private:
1.563 + void first(const ClassList &l) { i = l.begin(); validate(l); }
1.564 + void next(const ClassList &l) {
1.565 + ++i;
1.566 + validate(l);
1.567 + }
1.568 + void validate(const ClassList &l) {
1.569 + if ( i == l.end() )
1.570 + i = 0;
1.571 + }
1.572 + };
1.573 +
1.574 + /**
1.575 + * \brief Sets the iterator to point to the first component.
1.576 + *
1.577 + * Sets the iterator to point to the first component.
1.578 + *
1.579 + * With the \ref first, \ref valid and \ref next methods you can
1.580 + * iterate through the components. For example:
1.581 + * \code
1.582 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
1.583 + * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
1.584 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
1.585 + * for (U.first(iter); U.valid(iter); U.next(iter)) {
1.586 + * // iter is convertible to Graph::Node
1.587 + * cout << iter << endl;
1.588 + * }
1.589 + * \endcode
1.590 + */
1.591 +
1.592 + ClassIt& first(ClassIt& it) const {
1.593 + it.first(classes);
1.594 + return it;
1.595 + }
1.596 +
1.597 + /**
1.598 + * \brief Returns whether the iterator is valid.
1.599 + *
1.600 + * Returns whether the iterator is valid.
1.601 + *
1.602 + * With the \ref first, \ref valid and \ref next methods you can
1.603 + * iterate through the components. See the example here: \ref first.
1.604 + */
1.605 +
1.606 + bool valid(ClassIt const &it) const {
1.607 + return it.valid();
1.608 + }
1.609 +
1.610 + /**
1.611 + * \brief Steps the iterator to the next component.
1.612 + *
1.613 + * Steps the iterator to the next component.
1.614 + *
1.615 + * With the \ref first, \ref valid and \ref next methods you can
1.616 + * iterate through the components. See the example here: \ref first.
1.617 + */
1.618 +
1.619 + ClassIt& next(ClassIt& it) const {
1.620 + it.next(classes);
1.621 + return it;
1.622 + }
1.623 +
1.624 +
1.625 + class ItemIt {
1.626 + friend class UnionFindEnum;
1.627 +
1.628 + IcIter i;
1.629 + const ItemList *l;
1.630 + public:
1.631 + ItemIt(Invalid): i(0) {}
1.632 + ItemIt() {}
1.633 +
1.634 + operator const T& () const { return i->me; }
1.635 + bool operator == (ItemIt it) const {
1.636 + return (i == it.i);
1.637 + }
1.638 + bool operator != (ItemIt it) const {
1.639 + return (i != it.i);
1.640 + }
1.641 + bool operator < (ItemIt it) const {
1.642 + return (i < it.i);
1.643 + }
1.644 +
1.645 + bool valid() const { return i != 0; }
1.646 + private:
1.647 + void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
1.648 + void next() {
1.649 + ++i;
1.650 + validate();
1.651 + }
1.652 + void validate() {
1.653 + if ( i == l->end() )
1.654 + i = 0;
1.655 + }
1.656 + };
1.657 +
1.658 +
1.659 +
1.660 + /**
1.661 + * \brief Sets the iterator to point to the first element of the component.
1.662 + *
1.663 + * \anchor first2
1.664 + * Sets the iterator to point to the first element of the component.
1.665 + *
1.666 + * With the \ref first2 "first", \ref valid2 "valid"
1.667 + * and \ref next2 "next" methods you can
1.668 + * iterate through the elements of a component. For example
1.669 + * (iterating through the component of the node \e node):
1.670 + * \code
1.671 + * Graph::Node node = ...;
1.672 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
1.673 + * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
1.674 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
1.675 + * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
1.676 + * // iiter is convertible to Graph::Node
1.677 + * cout << iiter << endl;
1.678 + * }
1.679 + * \endcode
1.680 + */
1.681 +
1.682 + ItemIt& first(ItemIt& it, const T& a) const {
1.683 + it.first( * _find(m[a])->my_class );
1.684 + return it;
1.685 + }
1.686 +
1.687 + /**
1.688 + * \brief Returns whether the iterator is valid.
1.689 + *
1.690 + * \anchor valid2
1.691 + * Returns whether the iterator is valid.
1.692 + *
1.693 + * With the \ref first2 "first", \ref valid2 "valid"
1.694 + * and \ref next2 "next" methods you can
1.695 + * iterate through the elements of a component.
1.696 + * See the example here: \ref first2 "first".
1.697 + */
1.698 +
1.699 + bool valid(ItemIt const &it) const {
1.700 + return it.valid();
1.701 + }
1.702 +
1.703 + /**
1.704 + * \brief Steps the iterator to the next component.
1.705 + *
1.706 + * \anchor next2
1.707 + * Steps the iterator to the next component.
1.708 + *
1.709 + * With the \ref first2 "first", \ref valid2 "valid"
1.710 + * and \ref next2 "next" methods you can
1.711 + * iterate through the elements of a component.
1.712 + * See the example here: \ref first2 "first".
1.713 + */
1.714 +
1.715 + ItemIt& next(ItemIt& it) const {
1.716 + it.next();
1.717 + return it;
1.718 + }
1.719 +
1.720 + };
1.721 +
1.722 +
1.723 + //! @}
1.724 +
1.725 +} //namespace lemon
1.726 +
1.727 +#endif //LEMON_UNION_FIND_H