1.1 --- a/src/lemon/unionfind.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,724 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/unionfind.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, 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 Inserts 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 element \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 Inserts 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 Inserts the given element into the component of the others.
1.294 - *
1.295 - * This methods inserts 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 Finds 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 element \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 Splits 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 Sets the given element to the leader element of its component.
1.412 - *
1.413 - * Sets 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 Moves 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 Removes the given element from the structure.
1.490 - *
1.491 - * Removes 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