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