UnionFind moved to include. Test compiles and runs cleanly.
* test/makefile:
minor cleanups
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
2.1 --- a/src/test/makefile Thu Apr 29 16:59:00 2004 +0000
2.2 +++ b/src/test/makefile Thu Apr 29 17:00:44 2004 +0000
2.3 @@ -1,18 +1,21 @@
2.4 -#CXX3 := $(shell type -p g++-3.4 || shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.5 -CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.6 -CXX2 = g++-2.95
2.7 -CXX=$(CXX3)
2.8 +INCLUDEDIRS ?= -I../include
2.9 +CXXFLAGS += -Wall -O3 -ansi -pedantic $(INCLUDEDIRS)
2.10 +#LEDAROOT ?= /ledasrc/LEDA-4.1
2.11 +
2.12 +BINARIES = dijkstra_heap_test unionfind_test
2.13 +
2.14 +ifdef GCCVER
2.15 +CXX := g++-$(GCCVER)
2.16 +else
2.17 +CXX := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
2.18 +endif
2.19 +
2.20 CC=$(CXX)
2.21 -INCLUDEDIRS ?= -I../include -I.. -I../work/{marci,jacint,alpar,klao,akos,athos}
2.22 -CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS)
2.23 -LEDAROOT ?= /ledasrc/LEDA-4.1
2.24 -
2.25 -BINARIES = dijkstra_heap_test
2.26
2.27 all: $(BINARIES)
2.28
2.29 .depend dep depend:
2.30 - -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
2.31 + $(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend
2.32
2.33 makefile: .depend
2.34 sinclude .depend
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/test/unionfind_test.cc Thu Apr 29 17:00:44 2004 +0000
3.3 @@ -0,0 +1,205 @@
3.4 +#include <iostream>
3.5 +
3.6 +#include <maps.h>
3.7 +#include <unionfind.h>
3.8 +
3.9 +using namespace hugo;
3.10 +using namespace std;
3.11 +
3.12 +bool passed = true;
3.13 +
3.14 +void check(bool rc) {
3.15 + passed = passed && rc;
3.16 + if(!rc) {
3.17 + cout << "Test failed!" << endl;
3.18 + }
3.19 +}
3.20 +
3.21 +template <typename T>
3.22 +class BaseMap : public StdMap<int,T> {};
3.23 +
3.24 +typedef UnionFindEnum<int, BaseMap> UFE;
3.25 +
3.26 +void print(UFE const &ufe) {
3.27 + UFE::ClassIt cit;
3.28 + cout << "printing the classes of the structure:" << endl;
3.29 + int i = 1;
3.30 + for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
3.31 + cout << " " << i << " (" << cit << "):" << flush;
3.32 + UFE::ItemIt iit;
3.33 + for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
3.34 + cout << " " << iit << flush;
3.35 + }
3.36 + cout << endl;
3.37 + i++;
3.38 + }
3.39 + cout << "done" << endl;
3.40 +}
3.41 +
3.42 +
3.43 +int main() {
3.44 + UFE::MapType base;
3.45 + UFE U(base);
3.46 +
3.47 + print(U);
3.48 +
3.49 + cout << "Inserting 1..." << endl;
3.50 + U.insert(1);
3.51 + print(U);
3.52 +
3.53 + cout << "Inserting 2..." << endl;
3.54 + U.insert(2);
3.55 + print(U);
3.56 +
3.57 + cout << "Joining 1 and 2..." << endl;
3.58 + check(U.join(1,2));
3.59 + print(U);
3.60 +
3.61 + cout << "Inserting 3, 4, 5, 6, 7..." << endl;
3.62 + U.insert(3);
3.63 + U.insert(4);
3.64 + U.insert(5);
3.65 + U.insert(6);
3.66 + U.insert(7);
3.67 + print (U);
3.68 +
3.69 + cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
3.70 + check(U.join(1,4));
3.71 + check(!U.join(2,4));
3.72 + check(U.join(3,5));
3.73 + print(U);
3.74 +
3.75 + cout << "Inserting 8 to the component of 5 ..." << endl;
3.76 + U.insert(8,5);
3.77 + print(U);
3.78 +
3.79 + cout << "size of the class of 4: " << U.size(4) << endl;
3.80 + check(U.size(4) == 3);
3.81 + cout << "size of the class of 5: " << U.size(5) << endl;
3.82 + check(U.size(5) == 3);
3.83 + cout << "size of the class of 6: " << U.size(6) << endl;
3.84 + check(U.size(6) == 1);
3.85 + cout << "size of the class of 2: " << U.size(2) << endl;
3.86 + check(U.size(2) == 3);
3.87 +
3.88 + cout << "Inserting 9 ..." << endl;
3.89 + U.insert(9);
3.90 + print(U);
3.91 + cout << "Inserting 10 to the component of 9 ..." << endl;
3.92 + U.insert(10,9);
3.93 + print(U);
3.94 +
3.95 + cout << "Joining 8 and 10..." << endl;
3.96 + check(U.join(8,10));
3.97 + print(U);
3.98 +
3.99 + cout << "Move 9 to the class of 4 ..." << endl;
3.100 + check(U.move(9,4));
3.101 + print(U);
3.102 +
3.103 + cout << "Move 9 to the class of 2 ..." << endl;
3.104 + check(!U.move(9,2));
3.105 + print(U);
3.106 +
3.107 + cout << "size of the class of 4: " << U.size(4) << endl;
3.108 + check(U.size(4) == 4);
3.109 + cout << "size of the class of 9: " << U.size(9) << endl;
3.110 + check(U.size(9) == 4);
3.111 +
3.112 + cout << "Move 5 to the class of 6 ..." << endl;
3.113 + check(U.move(5,6));
3.114 + print(U);
3.115 +
3.116 + cout << "size of the class of 5: " << U.size(5) << endl;
3.117 + check(U.size(5) == 2);
3.118 + cout << "size of the class of 8: " << U.size(8) << endl;
3.119 + check(U.size(8) == 3);
3.120 +
3.121 + cout << "Move 7 to the class of 10 ..." << endl;
3.122 + check(U.move(7,10));
3.123 + print(U);
3.124 +
3.125 + cout << "size of the class of 7: " << U.size(7) << endl;
3.126 + check(U.size(7) == 4);
3.127 +
3.128 + cout <<"erase 9: " << endl;
3.129 + U.erase(9);
3.130 + print(U);
3.131 +
3.132 + cout <<"erase 1: " << endl;
3.133 + U.erase(1);
3.134 + print(U);
3.135 +
3.136 + cout << "size of the class of 4: " << U.size(4) << endl;
3.137 + check(U.size(4) == 2);
3.138 + cout << "size of the class of 2: " << U.size(2) << endl;
3.139 + check(U.size(2) == 2);
3.140 +
3.141 +
3.142 + cout <<"erase 1: " << endl;
3.143 + U.erase(1);
3.144 + print(U);
3.145 +
3.146 + cout <<"erase 6: " << endl;
3.147 + U.erase(6);
3.148 + print(U);
3.149 +
3.150 + cout << "split the class of 8: " << endl;
3.151 + U.split(8);
3.152 + print(U);
3.153 +
3.154 +
3.155 + cout << "size of the class of 4: " << U.size(4) << endl;
3.156 + check(U.size(4) == 2);
3.157 + cout << "size of the class of 3: " << U.size(3) << endl;
3.158 + check(U.size(3) == 1);
3.159 + cout << "size of the class of 2: " << U.size(2) << endl;
3.160 + check(U.size(2) == 2);
3.161 +
3.162 +
3.163 + cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
3.164 + check(U.join(3,4));
3.165 + check(!U.join(2,4));
3.166 + print(U);
3.167 +
3.168 +
3.169 + cout << "size of the class of 4: " << U.size(4) << endl;
3.170 + check(U.size(4) == 3);
3.171 + cout << "size of the class of 3: " << U.size(3) << endl;
3.172 + check(U.size(3) == 3);
3.173 + cout << "size of the class of 2: " << U.size(2) << endl;
3.174 + check(U.size(2) == 3);
3.175 +
3.176 + cout << "makeRep(4)" << endl;
3.177 + U.makeRep(4);
3.178 + print(U);
3.179 + cout << "makeRep(3)" << endl;
3.180 + U.makeRep(3);
3.181 + print(U);
3.182 + cout << "makeRep(2)" << endl;
3.183 + U.makeRep(2);
3.184 + print(U);
3.185 +
3.186 + cout << "size of the class of 4: " << U.size(4) << endl;
3.187 + check(U.size(4) == 3);
3.188 + cout << "size of the class of 3: " << U.size(3) << endl;
3.189 + check(U.size(3) == 3);
3.190 + cout << "size of the class of 2: " << U.size(2) << endl;
3.191 + check(U.size(2) == 3);
3.192 +
3.193 +
3.194 + cout << "eraseClass 4 ..." << endl;
3.195 + U.eraseClass(4);
3.196 + print(U);
3.197 +
3.198 + cout << "eraseClass 7 ..." << endl;
3.199 + U.eraseClass(7);
3.200 + print(U);
3.201 +
3.202 + cout << "done" << endl;
3.203 +
3.204 + cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
3.205 + << endl;
3.206 +
3.207 + return passed ? 0 : 1;
3.208 +}
4.1 --- a/src/work/johanna/Makefile Thu Apr 29 16:59:00 2004 +0000
4.2 +++ b/src/work/johanna/Makefile Thu Apr 29 17:00:44 2004 +0000
4.3 @@ -1,4 +1,4 @@
4.4 -BINARIES = kruskal_test ma_order_test unionfind_test
4.5 +BINARIES = kruskal_test ma_order_test
4.6 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos}
4.7 include ../makefile
4.8
5.1 --- a/src/work/johanna/unionfind.h Thu Apr 29 16:59:00 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,700 +0,0 @@
5.4 -// -*- c++ -*- //
5.5 -#ifndef HUGO_UNION_FIND_H
5.6 -#define HUGO_UNION_FIND_H
5.7 -
5.8 -//!ingroup auxdat
5.9 -//!\file
5.10 -//!\brief Union-Find data structures.
5.11 -
5.12 -
5.13 -#include <vector>
5.14 -#include <list>
5.15 -#include <utility>
5.16 -#include <algorithm>
5.17 -
5.18 -#include <invalid.h>
5.19 -
5.20 -namespace hugo {
5.21 -
5.22 - //! \addtogroup auxdat
5.23 - //! @{
5.24 -
5.25 - /**
5.26 - * \brief A \e Union-Find data structure implementation
5.27 - *
5.28 - * The class implements the \e Union-Find data structure.
5.29 - * The union operation uses rank heuristic, while
5.30 - * the find operation uses path compresson.
5.31 - * This is a very simple but efficient implementation, providing
5.32 - * only four methods: join (union), find, insert and size.
5.33 - * For more features see the \ref UnionFindEnum class.
5.34 - *
5.35 - * \pre The elements are automatically added only if the map
5.36 - * given to the constructor was filled with -1's. Otherwise you
5.37 - * need to add all the elements by the \ref insert() method.
5.38 - */
5.39 -
5.40 - template <typename T, typename TIntMap>
5.41 - class UnionFind {
5.42 -
5.43 - public:
5.44 - typedef T ElementType;
5.45 - typedef std::pair<int,int> PairType;
5.46 -
5.47 - private:
5.48 - std::vector<PairType> data;
5.49 - TIntMap& map;
5.50 -
5.51 - public:
5.52 - UnionFind(TIntMap& m) : map(m) {}
5.53 -
5.54 - /**
5.55 - * \brief Returns the index of the element's component.
5.56 - *
5.57 - * The method returns the index of the element's component.
5.58 - * This is an integer between zero and the number of inserted elements.
5.59 - */
5.60 -
5.61 - int find(T a)
5.62 - {
5.63 - int comp0 = map[a];
5.64 - if (comp0 < 0) {
5.65 - return insert(a);
5.66 - }
5.67 - int comp = comp0;
5.68 - int next;
5.69 - while ( (next = data[comp].first) != comp) {
5.70 - comp = next;
5.71 - }
5.72 - while ( (next = data[comp0].first) != comp) {
5.73 - data[comp0].first = comp;
5.74 - comp0 = next;
5.75 - }
5.76 -
5.77 - return comp;
5.78 - }
5.79 -
5.80 - /**
5.81 - * \brief Insert a new element into the structure.
5.82 - *
5.83 - * This method inserts a new element into the data structure.
5.84 - *
5.85 - * It is not required to use this method:
5.86 - * if the map given to the constructor was filled
5.87 - * with -1's then it is called automatically
5.88 - * on the first \ref find or \ref join.
5.89 - *
5.90 - * The method returns the index of the new component.
5.91 - */
5.92 -
5.93 - int insert(T a)
5.94 - {
5.95 - int n = data.size();
5.96 - data.push_back(std::make_pair(n, 1));
5.97 - map.set(a,n);
5.98 - return n;
5.99 - }
5.100 -
5.101 - /**
5.102 - * \brief Joining the components of element \e a and element \e b.
5.103 - *
5.104 - * This is the \e union operation of the Union-Find structure.
5.105 - * Joins the component of elemenent \e a and component of
5.106 - * element \e b. If \e a and \e b are in the same component then
5.107 - * it returns false otherwise it returns true.
5.108 - */
5.109 -
5.110 - bool join(T a, T b)
5.111 - {
5.112 - int ca = find(a);
5.113 - int cb = find(b);
5.114 -
5.115 - if ( ca == cb )
5.116 - return false;
5.117 -
5.118 - if ( data[ca].second > data[cb].second ) {
5.119 - data[cb].first = ca;
5.120 - data[ca].second += data[cb].second;
5.121 - }
5.122 - else {
5.123 - data[ca].first = cb;
5.124 - data[cb].second += data[ca].second;
5.125 - }
5.126 - return true;
5.127 - }
5.128 -
5.129 - /**
5.130 - * \brief Returns the size of the component of element \e a.
5.131 - *
5.132 - * Returns the size of the component of element \e a.
5.133 - */
5.134 -
5.135 - int size(T a)
5.136 - {
5.137 - int ca = find(a);
5.138 - return data[ca].second;
5.139 - }
5.140 -
5.141 - };
5.142 -
5.143 -
5.144 -
5.145 -
5.146 - /*******************************************************/
5.147 -
5.148 -
5.149 -#ifdef DEVELOPMENT_DOCS
5.150 -
5.151 - /**
5.152 - * \brief The auxiliary class for the \ref UnionFindEnum class.
5.153 - *
5.154 - * In the \ref UnionFindEnum class all components are represented as
5.155 - * a std::list.
5.156 - * Items of these lists are UnionFindEnumItem structures.
5.157 - *
5.158 - * The class has four fields:
5.159 - * - T me - the actual element
5.160 - * - IIter parent - the parent of the element in the union-find structure
5.161 - * - int size - the size of the component of the element.
5.162 - * Only valid if the element
5.163 - * is the leader of the component.
5.164 - * - CIter my_class - pointer into the list of components
5.165 - * pointing to the component of the element.
5.166 - * Only valid if the element is the leader of the component.
5.167 - */
5.168 -
5.169 -#endif
5.170 -
5.171 - template <typename T>
5.172 - struct UnionFindEnumItem {
5.173 -
5.174 - typedef std::list<UnionFindEnumItem> ItemList;
5.175 - typedef std::list<ItemList> ClassList;
5.176 - typedef typename ItemList::iterator IIter;
5.177 - typedef typename ClassList::iterator CIter;
5.178 -
5.179 - T me;
5.180 - IIter parent;
5.181 - int size;
5.182 - CIter my_class;
5.183 -
5.184 - UnionFindEnumItem() {}
5.185 - UnionFindEnumItem(const T &_me, CIter _my_class):
5.186 - me(_me), size(1), my_class(_my_class) {}
5.187 - };
5.188 -
5.189 -
5.190 - /**
5.191 - * \brief A \e Union-Find data structure implementation which
5.192 - * is able to enumerate the components.
5.193 - *
5.194 - * The class implements an \e Union-Find data structure
5.195 - * which is able to enumerate the components and the items in
5.196 - * a component. If you don't need this feature then perhaps it's
5.197 - * better to use the \ref UnionFind class which is more efficient.
5.198 - *
5.199 - * The union operation uses rank heuristic, while
5.200 - * the find operation uses path compresson.
5.201 - *
5.202 - * \pre You
5.203 - * need to add all the elements by the \ref insert() method.
5.204 - */
5.205 -
5.206 -
5.207 - template <typename T, template <typename Item> class Map>
5.208 - class UnionFindEnum {
5.209 -
5.210 - typedef std::list<UnionFindEnumItem<T> > ItemList;
5.211 - typedef std::list<ItemList> ClassList;
5.212 - typedef typename ItemList::iterator IIter;
5.213 - typedef typename ItemList::const_iterator IcIter;
5.214 - typedef typename ClassList::iterator CIter;
5.215 - typedef typename ClassList::const_iterator CcIter;
5.216 -
5.217 - public:
5.218 - typedef T ElementType;
5.219 - typedef UnionFindEnumItem<T> ItemType;
5.220 - typedef Map< IIter > MapType;
5.221 -
5.222 - private:
5.223 - MapType& m;
5.224 - ClassList classes;
5.225 -
5.226 - IIter _find(IIter a) const {
5.227 - IIter comp = a;
5.228 - IIter next;
5.229 - while( (next = comp->parent) != comp ) {
5.230 - comp = next;
5.231 - }
5.232 -
5.233 - IIter comp1 = a;
5.234 - while( (next = comp1->parent) != comp ) {
5.235 - comp1->parent = comp->parent;
5.236 - comp1 = next;
5.237 - }
5.238 - return comp;
5.239 - }
5.240 -
5.241 - public:
5.242 - UnionFindEnum(MapType& _m) : m(_m) {}
5.243 -
5.244 -
5.245 - /**
5.246 - * \brief Insert the given element into a new component.
5.247 - *
5.248 - * This method creates a new component consisting only of the
5.249 - * given element.
5.250 - */
5.251 -
5.252 - void insert(const T &a)
5.253 - {
5.254 -
5.255 -
5.256 - classes.push_back(ItemList());
5.257 - CIter aclass = classes.end();
5.258 - --aclass;
5.259 -
5.260 - ItemList &alist = *aclass;
5.261 - alist.push_back(ItemType(a, aclass));
5.262 - IIter ai = alist.begin();
5.263 -
5.264 - ai->parent = ai;
5.265 - m.set(a, ai);
5.266 -
5.267 - }
5.268 -
5.269 - /**
5.270 - * \brief Insert the given element into the component of the others.
5.271 - *
5.272 - * This methods insert the element \e a into the component of the
5.273 - * element \e comp.
5.274 - */
5.275 -
5.276 - void insert(const T &a, const T &comp) {
5.277 -
5.278 - IIter clit = _find(m[comp]);
5.279 - ItemList &c = *clit->my_class;
5.280 - c.push_back(ItemType(a,0));
5.281 - IIter ai = c.end();
5.282 - --ai;
5.283 - ai->parent = clit;
5.284 - m.set(a, ai);
5.285 - ++clit->size;
5.286 - }
5.287 -
5.288 -
5.289 - /**
5.290 - * \brief Find the leader of the component of the given element.
5.291 - *
5.292 - * The method returns the leader of the component of the given element.
5.293 - */
5.294 -
5.295 - T find(const T &a) const {
5.296 - return _find(m[a])->me;
5.297 - }
5.298 -
5.299 -
5.300 - /**
5.301 - * \brief Joining the component of element \e a and element \e b.
5.302 - *
5.303 - * This is the \e union operation of the Union-Find structure.
5.304 - * Joins the component of elemenent \e a and component of
5.305 - * element \e b. If \e a and \e b are in the same component then
5.306 - * returns false else returns true.
5.307 - */
5.308 -
5.309 - bool join(T a, T b) {
5.310 -
5.311 - IIter ca = _find(m[a]);
5.312 - IIter cb = _find(m[b]);
5.313 -
5.314 - if ( ca == cb ) {
5.315 - return false;
5.316 - }
5.317 -
5.318 - if ( ca->size > cb->size ) {
5.319 -
5.320 - cb->parent = ca->parent;
5.321 - ca->size += cb->size;
5.322 -
5.323 - ItemList &alist = *ca->my_class;
5.324 - alist.splice(alist.end(),*cb->my_class);
5.325 -
5.326 - classes.erase(cb->my_class);
5.327 - cb->my_class = 0;
5.328 - }
5.329 - else {
5.330 -
5.331 - ca->parent = cb->parent;
5.332 - cb->size += ca->size;
5.333 -
5.334 - ItemList &blist = *cb->my_class;
5.335 - blist.splice(blist.end(),*ca->my_class);
5.336 -
5.337 - classes.erase(ca->my_class);
5.338 - ca->my_class = 0;
5.339 - }
5.340 -
5.341 - return true;
5.342 - }
5.343 -
5.344 -
5.345 - /**
5.346 - * \brief Returns the size of the component of element \e a.
5.347 - *
5.348 - * Returns the size of the component of element \e a.
5.349 - */
5.350 -
5.351 - int size(const T &a) const {
5.352 - return _find(m[a])->size;
5.353 - }
5.354 -
5.355 -
5.356 - /**
5.357 - * \brief Split up the component of the element.
5.358 - *
5.359 - * Splitting the component of the element into sigleton
5.360 - * components (component of size one).
5.361 - */
5.362 -
5.363 - void split(const T &a) {
5.364 -
5.365 - IIter ca = _find(m[a]);
5.366 -
5.367 - if ( ca->size == 1 )
5.368 - return;
5.369 -
5.370 - CIter aclass = ca->my_class;
5.371 -
5.372 - for(IIter curr = ca; ++curr != aclass->end(); curr=ca) {
5.373 - classes.push_back(ItemList());
5.374 - CIter nl = --classes.end();
5.375 - nl->splice(nl->end(), *aclass, curr);
5.376 -
5.377 - curr->size=1;
5.378 - curr->parent=curr;
5.379 - curr->my_class = nl;
5.380 - }
5.381 -
5.382 - ca->size=1;
5.383 - return;
5.384 - }
5.385 -
5.386 -
5.387 - /**
5.388 - * \brief Set the given element to the leader element of its component.
5.389 - *
5.390 - * Set the given element to the leader element of its component.
5.391 - */
5.392 -
5.393 - void makeRep(const T &a) {
5.394 -
5.395 - IIter ia = m[a];
5.396 - IIter la = _find(ia);
5.397 - if (la == ia) return;
5.398 -
5.399 - ia->my_class = la->my_class;
5.400 - la->my_class = 0;
5.401 -
5.402 - ia->size = la->size;
5.403 -
5.404 - CIter l = ia->my_class;
5.405 - l->splice(l->begin(),*l,ia);
5.406 -
5.407 - ia->parent = ia;
5.408 - la->parent = ia;
5.409 - }
5.410 -
5.411 - /**
5.412 - * \brief Move the given element to an other component.
5.413 - *
5.414 - * This method moves the element \e a from its component
5.415 - * to the component of \e comp.
5.416 - * If \e a and \e comp are in the same component then
5.417 - * it returns false otherwise it returns true.
5.418 - */
5.419 -
5.420 - bool move(const T &a, const T &comp) {
5.421 -
5.422 - IIter ai = m[a];
5.423 - IIter lai = _find(ai);
5.424 - IIter clit = _find(m[comp]);
5.425 -
5.426 - if (lai == clit)
5.427 - return false;
5.428 -
5.429 - ItemList &c = *clit->my_class;
5.430 -
5.431 - bool is_leader = (lai == ai);
5.432 - bool singleton = false;
5.433 -
5.434 - if (is_leader) {
5.435 - ++lai;
5.436 - }
5.437 -
5.438 - c.splice(c.end(), *lai->my_class, ai);
5.439 -
5.440 - if (is_leader) {
5.441 - if (ai->size == 1) {
5.442 - classes.erase(ai->my_class);
5.443 - singleton = true;
5.444 - }
5.445 - else {
5.446 - lai->size = ai->size;
5.447 - lai->my_class = ai->my_class;
5.448 - }
5.449 - }
5.450 - if (!singleton) {
5.451 - for (IIter i = lai; i != lai->my_class->end(); ++i)
5.452 - i->parent = lai;
5.453 - --lai->size;
5.454 - }
5.455 -
5.456 - ai->parent = clit;
5.457 - ai->my_class = 0;
5.458 - ++clit->size;
5.459 -
5.460 - return true;
5.461 - }
5.462 -
5.463 -
5.464 - /**
5.465 - * \brief Remove the given element from the structure.
5.466 - *
5.467 - * Remove the given element from the structure.
5.468 - *
5.469 - * Removes the element from its component and if the component becomes
5.470 - * empty then removes that component from the component list.
5.471 - */
5.472 - void erase(const T &a) {
5.473 -
5.474 - IIter ma = m[a];
5.475 - if (ma == 0) return;
5.476 -
5.477 - IIter la = _find(ma);
5.478 - if (la == ma) {
5.479 - if (ma -> size == 1){
5.480 - classes.erase(ma->my_class);
5.481 - m.set(a,0);
5.482 - return;
5.483 - }
5.484 - ++la;
5.485 - la->size = ma->size;
5.486 - la->my_class = ma->my_class;
5.487 - }
5.488 -
5.489 - for (IIter i = la; i != la->my_class->end(); ++i) {
5.490 - i->parent = la;
5.491 - }
5.492 -
5.493 - la->size--;
5.494 - la->my_class->erase(ma);
5.495 - m.set(a,0);
5.496 - }
5.497 -
5.498 - /**
5.499 - * \brief Removes the component of the given element from the structure.
5.500 - *
5.501 - * Removes the component of the given element from the structure.
5.502 - */
5.503 -
5.504 - void eraseClass(const T &a) {
5.505 - IIter ma = m[a];
5.506 - if (ma == 0) return;
5.507 -# ifdef DEBUG
5.508 - CIter c = _find(ma)->my_class;
5.509 - for (IIter i=c->begin(); i!=c->end(); ++i)
5.510 - m.set(i->me, 0);
5.511 -# endif
5.512 - classes.erase(_find(ma)->my_class);
5.513 - }
5.514 -
5.515 -
5.516 - class ClassIt {
5.517 - friend class UnionFindEnum;
5.518 -
5.519 - CcIter i;
5.520 - public:
5.521 - ClassIt(Invalid): i(0) {}
5.522 - ClassIt() {}
5.523 -
5.524 - operator const T& () const {
5.525 - ItemList const &ll = *i;
5.526 - return (ll.begin())->me; }
5.527 - bool operator == (ClassIt it) const {
5.528 - return (i == it.i);
5.529 - }
5.530 - bool operator != (ClassIt it) const {
5.531 - return (i != it.i);
5.532 - }
5.533 - bool operator < (ClassIt it) const {
5.534 - return (i < it.i);
5.535 - }
5.536 -
5.537 - bool valid() const { return i != 0; }
5.538 - private:
5.539 - void first(const ClassList &l) { i = l.begin(); validate(l); }
5.540 - void next(const ClassList &l) {
5.541 - ++i;
5.542 - validate(l);
5.543 - }
5.544 - void validate(const ClassList &l) {
5.545 - if ( i == l.end() )
5.546 - i = 0;
5.547 - }
5.548 - };
5.549 -
5.550 - /**
5.551 - * \brief Sets the iterator to point to the first component.
5.552 - *
5.553 - * Sets the iterator to point to the first component.
5.554 - *
5.555 - * With the \ref first, \ref valid and \ref next methods you can
5.556 - * iterate through the components. For example:
5.557 - * \code
5.558 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
5.559 - * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
5.560 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
5.561 - * for (U.first(iter); U.valid(iter); U.next(iter)) {
5.562 - * // iter is convertible to Graph::Node
5.563 - * cout << iter << endl;
5.564 - * }
5.565 - * \endcode
5.566 - */
5.567 -
5.568 - ClassIt& first(ClassIt& it) const {
5.569 - it.first(classes);
5.570 - return it;
5.571 - }
5.572 -
5.573 - /**
5.574 - * \brief Returns whether the iterator is valid.
5.575 - *
5.576 - * Returns whether the iterator is valid.
5.577 - *
5.578 - * With the \ref first, \ref valid and \ref next methods you can
5.579 - * iterate through the components. See the example here: \ref first.
5.580 - */
5.581 -
5.582 - bool valid(ClassIt const &it) const {
5.583 - return it.valid();
5.584 - }
5.585 -
5.586 - /**
5.587 - * \brief Steps the iterator to the next component.
5.588 - *
5.589 - * Steps the iterator to the next component.
5.590 - *
5.591 - * With the \ref first, \ref valid and \ref next methods you can
5.592 - * iterate through the components. See the example here: \ref first.
5.593 - */
5.594 -
5.595 - ClassIt& next(ClassIt& it) const {
5.596 - it.next(classes);
5.597 - return it;
5.598 - }
5.599 -
5.600 -
5.601 - class ItemIt {
5.602 - friend class UnionFindEnum;
5.603 -
5.604 - IcIter i;
5.605 - const ItemList *l;
5.606 - public:
5.607 - ItemIt(Invalid): i(0) {}
5.608 - ItemIt() {}
5.609 -
5.610 - operator const T& () const { return i->me; }
5.611 - bool operator == (ItemIt it) const {
5.612 - return (i == it.i);
5.613 - }
5.614 - bool operator != (ItemIt it) const {
5.615 - return (i != it.i);
5.616 - }
5.617 - bool operator < (ItemIt it) const {
5.618 - return (i < it.i);
5.619 - }
5.620 -
5.621 - bool valid() const { return i != 0; }
5.622 - private:
5.623 - void first(const ItemList &il) { l=&il; i = l->begin(); validate(); }
5.624 - void next() {
5.625 - ++i;
5.626 - validate();
5.627 - }
5.628 - void validate() {
5.629 - if ( i == l->end() )
5.630 - i = 0;
5.631 - }
5.632 - };
5.633 -
5.634 -
5.635 -
5.636 - /**
5.637 - * \brief Sets the iterator to point to the first element of the component.
5.638 - *
5.639 - * \anchor first2
5.640 - * Sets the iterator to point to the first element of the component.
5.641 - *
5.642 - * With the \ref first2 "first", \ref valid2 "valid"
5.643 - * and \ref next2 "next" methods you can
5.644 - * iterate through the elements of a component. For example
5.645 - * (iterating through the component of the node \e node):
5.646 - * \code
5.647 - * Graph::Node node = ...;
5.648 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
5.649 - * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
5.650 - * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
5.651 - * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
5.652 - * // iiter is convertible to Graph::Node
5.653 - * cout << iiter << endl;
5.654 - * }
5.655 - * \endcode
5.656 - */
5.657 -
5.658 - ItemIt& first(ItemIt& it, const T& a) const {
5.659 - it.first( * _find(m[a])->my_class );
5.660 - return it;
5.661 - }
5.662 -
5.663 - /**
5.664 - * \brief Returns whether the iterator is valid.
5.665 - *
5.666 - * \anchor valid2
5.667 - * Returns whether the iterator is valid.
5.668 - *
5.669 - * With the \ref first2 "first", \ref valid2 "valid"
5.670 - * and \ref next2 "next" methods you can
5.671 - * iterate through the elements of a component.
5.672 - * See the example here: \ref first2 "first".
5.673 - */
5.674 -
5.675 - bool valid(ItemIt const &it) const {
5.676 - return it.valid();
5.677 - }
5.678 -
5.679 - /**
5.680 - * \brief Steps the iterator to the next component.
5.681 - *
5.682 - * \anchor next2
5.683 - * Steps the iterator to the next component.
5.684 - *
5.685 - * With the \ref first2 "first", \ref valid2 "valid"
5.686 - * and \ref next2 "next" methods you can
5.687 - * iterate through the elements of a component.
5.688 - * See the example here: \ref first2 "first".
5.689 - */
5.690 -
5.691 - ItemIt& next(ItemIt& it) const {
5.692 - it.next();
5.693 - return it;
5.694 - }
5.695 -
5.696 - };
5.697 -
5.698 -
5.699 - //! @}
5.700 -
5.701 -} //namespace hugo
5.702 -
5.703 -#endif //HUGO_UNION_FIND_H
6.1 --- a/src/work/johanna/unionfind_test.cc Thu Apr 29 16:59:00 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,205 +0,0 @@
6.4 -#include <iostream>
6.5 -
6.6 -#include <maps.h>
6.7 -#include <unionfind.h>
6.8 -
6.9 -using namespace hugo;
6.10 -using namespace std;
6.11 -
6.12 -bool passed = true;
6.13 -
6.14 -void check(bool rc) {
6.15 - passed = passed && rc;
6.16 - if(!rc) {
6.17 - cout << "Test failed!" << endl;
6.18 - }
6.19 -}
6.20 -
6.21 -template <typename T>
6.22 -class BaseMap : public StdMap<int,T> {};
6.23 -
6.24 -typedef UnionFindEnum<int, BaseMap> UFE;
6.25 -
6.26 -void print(UFE const &ufe) {
6.27 - UFE::ClassIt cit;
6.28 - cout << "printing the classes of the structure:" << endl;
6.29 - int i = 1;
6.30 - for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
6.31 - cout << " " << i << " (" << cit << "):" << flush;
6.32 - UFE::ItemIt iit;
6.33 - for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) {
6.34 - cout << " " << iit << flush;
6.35 - }
6.36 - cout << endl;
6.37 - i++;
6.38 - }
6.39 - cout << "done" << endl;
6.40 -}
6.41 -
6.42 -
6.43 -int main() {
6.44 - UFE::MapType base;
6.45 - UFE U(base);
6.46 -
6.47 - print(U);
6.48 -
6.49 - cout << "Inserting 1..." << endl;
6.50 - U.insert(1);
6.51 - print(U);
6.52 -
6.53 - cout << "Inserting 2..." << endl;
6.54 - U.insert(2);
6.55 - print(U);
6.56 -
6.57 - cout << "Joining 1 and 2..." << endl;
6.58 - check(U.join(1,2));
6.59 - print(U);
6.60 -
6.61 - cout << "Inserting 3, 4, 5, 6, 7..." << endl;
6.62 - U.insert(3);
6.63 - U.insert(4);
6.64 - U.insert(5);
6.65 - U.insert(6);
6.66 - U.insert(7);
6.67 - print (U);
6.68 -
6.69 - cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
6.70 - check(U.join(1,4));
6.71 - check(!U.join(2,4));
6.72 - check(U.join(3,5));
6.73 - print(U);
6.74 -
6.75 - cout << "Inserting 8 to the component of 5 ..." << endl;
6.76 - U.insert(8,5);
6.77 - print(U);
6.78 -
6.79 - cout << "size of the class of 4: " << U.size(4) << endl;
6.80 - check(U.size(4) == 3);
6.81 - cout << "size of the class of 5: " << U.size(5) << endl;
6.82 - check(U.size(5) == 3);
6.83 - cout << "size of the class of 6: " << U.size(6) << endl;
6.84 - check(U.size(6) == 1);
6.85 - cout << "size of the class of 2: " << U.size(2) << endl;
6.86 - check(U.size(2) == 3);
6.87 -
6.88 - cout << "Inserting 9 ..." << endl;
6.89 - U.insert(9);
6.90 - print(U);
6.91 - cout << "Inserting 10 to the component of 9 ..." << endl;
6.92 - U.insert(10,9);
6.93 - print(U);
6.94 -
6.95 - cout << "Joining 8 and 10..." << endl;
6.96 - check(U.join(8,10));
6.97 - print(U);
6.98 -
6.99 - cout << "Move 9 to the class of 4 ..." << endl;
6.100 - check(U.move(9,4));
6.101 - print(U);
6.102 -
6.103 - cout << "Move 9 to the class of 2 ..." << endl;
6.104 - check(!U.move(9,2));
6.105 - print(U);
6.106 -
6.107 - cout << "size of the class of 4: " << U.size(4) << endl;
6.108 - check(U.size(4) == 4);
6.109 - cout << "size of the class of 9: " << U.size(9) << endl;
6.110 - check(U.size(9) == 4);
6.111 -
6.112 - cout << "Move 5 to the class of 6 ..." << endl;
6.113 - check(U.move(5,6));
6.114 - print(U);
6.115 -
6.116 - cout << "size of the class of 5: " << U.size(5) << endl;
6.117 - check(U.size(5) == 2);
6.118 - cout << "size of the class of 8: " << U.size(8) << endl;
6.119 - check(U.size(8) == 3);
6.120 -
6.121 - cout << "Move 7 to the class of 10 ..." << endl;
6.122 - check(U.move(7,10));
6.123 - print(U);
6.124 -
6.125 - cout << "size of the class of 7: " << U.size(7) << endl;
6.126 - check(U.size(7) == 4);
6.127 -
6.128 - cout <<"erase 9: " << endl;
6.129 - U.erase(9);
6.130 - print(U);
6.131 -
6.132 - cout <<"erase 1: " << endl;
6.133 - U.erase(1);
6.134 - print(U);
6.135 -
6.136 - cout << "size of the class of 4: " << U.size(4) << endl;
6.137 - check(U.size(4) == 2);
6.138 - cout << "size of the class of 2: " << U.size(2) << endl;
6.139 - check(U.size(2) == 2);
6.140 -
6.141 -
6.142 - cout <<"erase 1: " << endl;
6.143 - U.erase(1);
6.144 - print(U);
6.145 -
6.146 - cout <<"erase 6: " << endl;
6.147 - U.erase(6);
6.148 - print(U);
6.149 -
6.150 - cout << "split the class of 8: " << endl;
6.151 - U.split(8);
6.152 - print(U);
6.153 -
6.154 -
6.155 - cout << "size of the class of 4: " << U.size(4) << endl;
6.156 - check(U.size(4) == 2);
6.157 - cout << "size of the class of 3: " << U.size(3) << endl;
6.158 - check(U.size(3) == 1);
6.159 - cout << "size of the class of 2: " << U.size(2) << endl;
6.160 - check(U.size(2) == 2);
6.161 -
6.162 -
6.163 - cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
6.164 - check(U.join(3,4));
6.165 - check(!U.join(2,4));
6.166 - print(U);
6.167 -
6.168 -
6.169 - cout << "size of the class of 4: " << U.size(4) << endl;
6.170 - check(U.size(4) == 3);
6.171 - cout << "size of the class of 3: " << U.size(3) << endl;
6.172 - check(U.size(3) == 3);
6.173 - cout << "size of the class of 2: " << U.size(2) << endl;
6.174 - check(U.size(2) == 3);
6.175 -
6.176 - cout << "makeRep(4)" << endl;
6.177 - U.makeRep(4);
6.178 - print(U);
6.179 - cout << "makeRep(3)" << endl;
6.180 - U.makeRep(3);
6.181 - print(U);
6.182 - cout << "makeRep(2)" << endl;
6.183 - U.makeRep(2);
6.184 - print(U);
6.185 -
6.186 - cout << "size of the class of 4: " << U.size(4) << endl;
6.187 - check(U.size(4) == 3);
6.188 - cout << "size of the class of 3: " << U.size(3) << endl;
6.189 - check(U.size(3) == 3);
6.190 - cout << "size of the class of 2: " << U.size(2) << endl;
6.191 - check(U.size(2) == 3);
6.192 -
6.193 -
6.194 - cout << "eraseClass 4 ..." << endl;
6.195 - U.eraseClass(4);
6.196 - print(U);
6.197 -
6.198 - cout << "eraseClass 7 ..." << endl;
6.199 - U.eraseClass(7);
6.200 - print(U);
6.201 -
6.202 - cout << "done" << endl;
6.203 -
6.204 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
6.205 - << endl;
6.206 -
6.207 - return passed ? 0 : 1;
6.208 -}