Index: src/work/johanna/Makefile =================================================================== --- src/work/johanna/Makefile (revision 394) +++ src/work/johanna/Makefile (revision 483) @@ -1,3 +1,3 @@ -BINARIES = kruskal_test ma_order_test unionfind_test +BINARIES = kruskal_test ma_order_test INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,klao,akos} include ../makefile Index: src/work/johanna/unionfind.h =================================================================== --- src/work/johanna/unionfind.h (revision 481) +++ (revision ) @@ -1,700 +1,0 @@ -// -*- c++ -*- // -#ifndef HUGO_UNION_FIND_H -#define HUGO_UNION_FIND_H - -//!ingroup auxdat -//!\file -//!\brief Union-Find data structures. - - -#include -#include -#include -#include - -#include - -namespace hugo { - - //! \addtogroup auxdat - //! @{ - - /** - * \brief A \e Union-Find data structure implementation - * - * The class implements the \e Union-Find data structure. - * The union operation uses rank heuristic, while - * the find operation uses path compresson. - * This is a very simple but efficient implementation, providing - * only four methods: join (union), find, insert and size. - * For more features see the \ref UnionFindEnum class. - * - * \pre The elements are automatically added only if the map - * given to the constructor was filled with -1's. Otherwise you - * need to add all the elements by the \ref insert() method. - */ - - template - class UnionFind { - - public: - typedef T ElementType; - typedef std::pair PairType; - - private: - std::vector data; - TIntMap& map; - - public: - UnionFind(TIntMap& m) : map(m) {} - - /** - * \brief Returns the index of the element's component. - * - * The method returns the index of the element's component. - * This is an integer between zero and the number of inserted elements. - */ - - int find(T a) - { - int comp0 = map[a]; - if (comp0 < 0) { - return insert(a); - } - int comp = comp0; - int next; - while ( (next = data[comp].first) != comp) { - comp = next; - } - while ( (next = data[comp0].first) != comp) { - data[comp0].first = comp; - comp0 = next; - } - - return comp; - } - - /** - * \brief Insert a new element into the structure. - * - * This method inserts a new element into the data structure. - * - * It is not required to use this method: - * if the map given to the constructor was filled - * with -1's then it is called automatically - * on the first \ref find or \ref join. - * - * The method returns the index of the new component. - */ - - int insert(T a) - { - int n = data.size(); - data.push_back(std::make_pair(n, 1)); - map.set(a,n); - return n; - } - - /** - * \brief Joining the components of element \e a and element \e b. - * - * This is the \e union operation of the Union-Find structure. - * Joins the component of elemenent \e a and component of - * element \e b. If \e a and \e b are in the same component then - * it returns false otherwise it returns true. - */ - - bool join(T a, T b) - { - int ca = find(a); - int cb = find(b); - - if ( ca == cb ) - return false; - - if ( data[ca].second > data[cb].second ) { - data[cb].first = ca; - data[ca].second += data[cb].second; - } - else { - data[ca].first = cb; - data[cb].second += data[ca].second; - } - return true; - } - - /** - * \brief Returns the size of the component of element \e a. - * - * Returns the size of the component of element \e a. - */ - - int size(T a) - { - int ca = find(a); - return data[ca].second; - } - - }; - - - - - /*******************************************************/ - - -#ifdef DEVELOPMENT_DOCS - - /** - * \brief The auxiliary class for the \ref UnionFindEnum class. - * - * In the \ref UnionFindEnum class all components are represented as - * a std::list. - * Items of these lists are UnionFindEnumItem structures. - * - * The class has four fields: - * - T me - the actual element - * - IIter parent - the parent of the element in the union-find structure - * - int size - the size of the component of the element. - * Only valid if the element - * is the leader of the component. - * - CIter my_class - pointer into the list of components - * pointing to the component of the element. - * Only valid if the element is the leader of the component. - */ - -#endif - - template - struct UnionFindEnumItem { - - typedef std::list ItemList; - typedef std::list ClassList; - typedef typename ItemList::iterator IIter; - typedef typename ClassList::iterator CIter; - - T me; - IIter parent; - int size; - CIter my_class; - - UnionFindEnumItem() {} - UnionFindEnumItem(const T &_me, CIter _my_class): - me(_me), size(1), my_class(_my_class) {} - }; - - - /** - * \brief A \e Union-Find data structure implementation which - * is able to enumerate the components. - * - * The class implements an \e Union-Find data structure - * which is able to enumerate the components and the items in - * a component. If you don't need this feature then perhaps it's - * better to use the \ref UnionFind class which is more efficient. - * - * The union operation uses rank heuristic, while - * the find operation uses path compresson. - * - * \pre You - * need to add all the elements by the \ref insert() method. - */ - - - template class Map> - class UnionFindEnum { - - typedef std::list > ItemList; - typedef std::list ClassList; - typedef typename ItemList::iterator IIter; - typedef typename ItemList::const_iterator IcIter; - typedef typename ClassList::iterator CIter; - typedef typename ClassList::const_iterator CcIter; - - public: - typedef T ElementType; - typedef UnionFindEnumItem ItemType; - typedef Map< IIter > MapType; - - private: - MapType& m; - ClassList classes; - - IIter _find(IIter a) const { - IIter comp = a; - IIter next; - while( (next = comp->parent) != comp ) { - comp = next; - } - - IIter comp1 = a; - while( (next = comp1->parent) != comp ) { - comp1->parent = comp->parent; - comp1 = next; - } - return comp; - } - - public: - UnionFindEnum(MapType& _m) : m(_m) {} - - - /** - * \brief Insert the given element into a new component. - * - * This method creates a new component consisting only of the - * given element. - */ - - void insert(const T &a) - { - - - classes.push_back(ItemList()); - CIter aclass = classes.end(); - --aclass; - - ItemList &alist = *aclass; - alist.push_back(ItemType(a, aclass)); - IIter ai = alist.begin(); - - ai->parent = ai; - m.set(a, ai); - - } - - /** - * \brief Insert the given element into the component of the others. - * - * This methods insert the element \e a into the component of the - * element \e comp. - */ - - void insert(const T &a, const T &comp) { - - IIter clit = _find(m[comp]); - ItemList &c = *clit->my_class; - c.push_back(ItemType(a,0)); - IIter ai = c.end(); - --ai; - ai->parent = clit; - m.set(a, ai); - ++clit->size; - } - - - /** - * \brief Find the leader of the component of the given element. - * - * The method returns the leader of the component of the given element. - */ - - T find(const T &a) const { - return _find(m[a])->me; - } - - - /** - * \brief Joining the component of element \e a and element \e b. - * - * This is the \e union operation of the Union-Find structure. - * Joins the component of elemenent \e a and component of - * element \e b. If \e a and \e b are in the same component then - * returns false else returns true. - */ - - bool join(T a, T b) { - - IIter ca = _find(m[a]); - IIter cb = _find(m[b]); - - if ( ca == cb ) { - return false; - } - - if ( ca->size > cb->size ) { - - cb->parent = ca->parent; - ca->size += cb->size; - - ItemList &alist = *ca->my_class; - alist.splice(alist.end(),*cb->my_class); - - classes.erase(cb->my_class); - cb->my_class = 0; - } - else { - - ca->parent = cb->parent; - cb->size += ca->size; - - ItemList &blist = *cb->my_class; - blist.splice(blist.end(),*ca->my_class); - - classes.erase(ca->my_class); - ca->my_class = 0; - } - - return true; - } - - - /** - * \brief Returns the size of the component of element \e a. - * - * Returns the size of the component of element \e a. - */ - - int size(const T &a) const { - return _find(m[a])->size; - } - - - /** - * \brief Split up the component of the element. - * - * Splitting the component of the element into sigleton - * components (component of size one). - */ - - void split(const T &a) { - - IIter ca = _find(m[a]); - - if ( ca->size == 1 ) - return; - - CIter aclass = ca->my_class; - - for(IIter curr = ca; ++curr != aclass->end(); curr=ca) { - classes.push_back(ItemList()); - CIter nl = --classes.end(); - nl->splice(nl->end(), *aclass, curr); - - curr->size=1; - curr->parent=curr; - curr->my_class = nl; - } - - ca->size=1; - return; - } - - - /** - * \brief Set the given element to the leader element of its component. - * - * Set the given element to the leader element of its component. - */ - - void makeRep(const T &a) { - - IIter ia = m[a]; - IIter la = _find(ia); - if (la == ia) return; - - ia->my_class = la->my_class; - la->my_class = 0; - - ia->size = la->size; - - CIter l = ia->my_class; - l->splice(l->begin(),*l,ia); - - ia->parent = ia; - la->parent = ia; - } - - /** - * \brief Move the given element to an other component. - * - * This method moves the element \e a from its component - * to the component of \e comp. - * If \e a and \e comp are in the same component then - * it returns false otherwise it returns true. - */ - - bool move(const T &a, const T &comp) { - - IIter ai = m[a]; - IIter lai = _find(ai); - IIter clit = _find(m[comp]); - - if (lai == clit) - return false; - - ItemList &c = *clit->my_class; - - bool is_leader = (lai == ai); - bool singleton = false; - - if (is_leader) { - ++lai; - } - - c.splice(c.end(), *lai->my_class, ai); - - if (is_leader) { - if (ai->size == 1) { - classes.erase(ai->my_class); - singleton = true; - } - else { - lai->size = ai->size; - lai->my_class = ai->my_class; - } - } - if (!singleton) { - for (IIter i = lai; i != lai->my_class->end(); ++i) - i->parent = lai; - --lai->size; - } - - ai->parent = clit; - ai->my_class = 0; - ++clit->size; - - return true; - } - - - /** - * \brief Remove the given element from the structure. - * - * Remove the given element from the structure. - * - * Removes the element from its component and if the component becomes - * empty then removes that component from the component list. - */ - void erase(const T &a) { - - IIter ma = m[a]; - if (ma == 0) return; - - IIter la = _find(ma); - if (la == ma) { - if (ma -> size == 1){ - classes.erase(ma->my_class); - m.set(a,0); - return; - } - ++la; - la->size = ma->size; - la->my_class = ma->my_class; - } - - for (IIter i = la; i != la->my_class->end(); ++i) { - i->parent = la; - } - - la->size--; - la->my_class->erase(ma); - m.set(a,0); - } - - /** - * \brief Removes the component of the given element from the structure. - * - * Removes the component of the given element from the structure. - */ - - void eraseClass(const T &a) { - IIter ma = m[a]; - if (ma == 0) return; -# ifdef DEBUG - CIter c = _find(ma)->my_class; - for (IIter i=c->begin(); i!=c->end(); ++i) - m.set(i->me, 0); -# endif - classes.erase(_find(ma)->my_class); - } - - - class ClassIt { - friend class UnionFindEnum; - - CcIter i; - public: - ClassIt(Invalid): i(0) {} - ClassIt() {} - - operator const T& () const { - ItemList const &ll = *i; - return (ll.begin())->me; } - bool operator == (ClassIt it) const { - return (i == it.i); - } - bool operator != (ClassIt it) const { - return (i != it.i); - } - bool operator < (ClassIt it) const { - return (i < it.i); - } - - bool valid() const { return i != 0; } - private: - void first(const ClassList &l) { i = l.begin(); validate(l); } - void next(const ClassList &l) { - ++i; - validate(l); - } - void validate(const ClassList &l) { - if ( i == l.end() ) - i = 0; - } - }; - - /** - * \brief Sets the iterator to point to the first component. - * - * Sets the iterator to point to the first component. - * - * With the \ref first, \ref valid and \ref next methods you can - * iterate through the components. For example: - * \code - * UnionFindEnum::MapType map(G); - * UnionFindEnum U(map); - * UnionFindEnum::ClassIt iter; - * for (U.first(iter); U.valid(iter); U.next(iter)) { - * // iter is convertible to Graph::Node - * cout << iter << endl; - * } - * \endcode - */ - - ClassIt& first(ClassIt& it) const { - it.first(classes); - return it; - } - - /** - * \brief Returns whether the iterator is valid. - * - * Returns whether the iterator is valid. - * - * With the \ref first, \ref valid and \ref next methods you can - * iterate through the components. See the example here: \ref first. - */ - - bool valid(ClassIt const &it) const { - return it.valid(); - } - - /** - * \brief Steps the iterator to the next component. - * - * Steps the iterator to the next component. - * - * With the \ref first, \ref valid and \ref next methods you can - * iterate through the components. See the example here: \ref first. - */ - - ClassIt& next(ClassIt& it) const { - it.next(classes); - return it; - } - - - class ItemIt { - friend class UnionFindEnum; - - IcIter i; - const ItemList *l; - public: - ItemIt(Invalid): i(0) {} - ItemIt() {} - - operator const T& () const { return i->me; } - bool operator == (ItemIt it) const { - return (i == it.i); - } - bool operator != (ItemIt it) const { - return (i != it.i); - } - bool operator < (ItemIt it) const { - return (i < it.i); - } - - bool valid() const { return i != 0; } - private: - void first(const ItemList &il) { l=&il; i = l->begin(); validate(); } - void next() { - ++i; - validate(); - } - void validate() { - if ( i == l->end() ) - i = 0; - } - }; - - - - /** - * \brief Sets the iterator to point to the first element of the component. - * - * \anchor first2 - * Sets the iterator to point to the first element of the component. - * - * With the \ref first2 "first", \ref valid2 "valid" - * and \ref next2 "next" methods you can - * iterate through the elements of a component. For example - * (iterating through the component of the node \e node): - * \code - * Graph::Node node = ...; - * UnionFindEnum::MapType map(G); - * UnionFindEnum U(map); - * UnionFindEnum::ItemIt iiter; - * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) { - * // iiter is convertible to Graph::Node - * cout << iiter << endl; - * } - * \endcode - */ - - ItemIt& first(ItemIt& it, const T& a) const { - it.first( * _find(m[a])->my_class ); - return it; - } - - /** - * \brief Returns whether the iterator is valid. - * - * \anchor valid2 - * Returns whether the iterator is valid. - * - * With the \ref first2 "first", \ref valid2 "valid" - * and \ref next2 "next" methods you can - * iterate through the elements of a component. - * See the example here: \ref first2 "first". - */ - - bool valid(ItemIt const &it) const { - return it.valid(); - } - - /** - * \brief Steps the iterator to the next component. - * - * \anchor next2 - * Steps the iterator to the next component. - * - * With the \ref first2 "first", \ref valid2 "valid" - * and \ref next2 "next" methods you can - * iterate through the elements of a component. - * See the example here: \ref first2 "first". - */ - - ItemIt& next(ItemIt& it) const { - it.next(); - return it; - } - - }; - - - //! @} - -} //namespace hugo - -#endif //HUGO_UNION_FIND_H Index: src/work/johanna/unionfind_test.cc =================================================================== --- src/work/johanna/unionfind_test.cc (revision 481) +++ (revision ) @@ -1,205 +1,0 @@ -#include - -#include -#include - -using namespace hugo; -using namespace std; - -bool passed = true; - -void check(bool rc) { - passed = passed && rc; - if(!rc) { - cout << "Test failed!" << endl; - } -} - -template -class BaseMap : public StdMap {}; - -typedef UnionFindEnum UFE; - -void print(UFE const &ufe) { - UFE::ClassIt cit; - cout << "printing the classes of the structure:" << endl; - int i = 1; - for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) { - cout << " " << i << " (" << cit << "):" << flush; - UFE::ItemIt iit; - for (ufe.first(iit, cit); ufe.valid(iit); ufe.next(iit)) { - cout << " " << iit << flush; - } - cout << endl; - i++; - } - cout << "done" << endl; -} - - -int main() { - UFE::MapType base; - UFE U(base); - - print(U); - - cout << "Inserting 1..." << endl; - U.insert(1); - print(U); - - cout << "Inserting 2..." << endl; - U.insert(2); - print(U); - - cout << "Joining 1 and 2..." << endl; - check(U.join(1,2)); - print(U); - - cout << "Inserting 3, 4, 5, 6, 7..." << endl; - U.insert(3); - U.insert(4); - U.insert(5); - U.insert(6); - U.insert(7); - print (U); - - cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl; - check(U.join(1,4)); - check(!U.join(2,4)); - check(U.join(3,5)); - print(U); - - cout << "Inserting 8 to the component of 5 ..." << endl; - U.insert(8,5); - print(U); - - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 3); - cout << "size of the class of 5: " << U.size(5) << endl; - check(U.size(5) == 3); - cout << "size of the class of 6: " << U.size(6) << endl; - check(U.size(6) == 1); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 3); - - cout << "Inserting 9 ..." << endl; - U.insert(9); - print(U); - cout << "Inserting 10 to the component of 9 ..." << endl; - U.insert(10,9); - print(U); - - cout << "Joining 8 and 10..." << endl; - check(U.join(8,10)); - print(U); - - cout << "Move 9 to the class of 4 ..." << endl; - check(U.move(9,4)); - print(U); - - cout << "Move 9 to the class of 2 ..." << endl; - check(!U.move(9,2)); - print(U); - - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 4); - cout << "size of the class of 9: " << U.size(9) << endl; - check(U.size(9) == 4); - - cout << "Move 5 to the class of 6 ..." << endl; - check(U.move(5,6)); - print(U); - - cout << "size of the class of 5: " << U.size(5) << endl; - check(U.size(5) == 2); - cout << "size of the class of 8: " << U.size(8) << endl; - check(U.size(8) == 3); - - cout << "Move 7 to the class of 10 ..." << endl; - check(U.move(7,10)); - print(U); - - cout << "size of the class of 7: " << U.size(7) << endl; - check(U.size(7) == 4); - - cout <<"erase 9: " << endl; - U.erase(9); - print(U); - - cout <<"erase 1: " << endl; - U.erase(1); - print(U); - - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 2); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 2); - - - cout <<"erase 1: " << endl; - U.erase(1); - print(U); - - cout <<"erase 6: " << endl; - U.erase(6); - print(U); - - cout << "split the class of 8: " << endl; - U.split(8); - print(U); - - - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 2); - cout << "size of the class of 3: " << U.size(3) << endl; - check(U.size(3) == 1); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 2); - - - cout << "Joining 3 - 4 and 2 - 4 ..." << endl; - check(U.join(3,4)); - check(!U.join(2,4)); - print(U); - - - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 3); - cout << "size of the class of 3: " << U.size(3) << endl; - check(U.size(3) == 3); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 3); - - cout << "makeRep(4)" << endl; - U.makeRep(4); - print(U); - cout << "makeRep(3)" << endl; - U.makeRep(3); - print(U); - cout << "makeRep(2)" << endl; - U.makeRep(2); - print(U); - - cout << "size of the class of 4: " << U.size(4) << endl; - check(U.size(4) == 3); - cout << "size of the class of 3: " << U.size(3) << endl; - check(U.size(3) == 3); - cout << "size of the class of 2: " << U.size(2) << endl; - check(U.size(2) == 3); - - - cout << "eraseClass 4 ..." << endl; - U.eraseClass(4); - print(U); - - cout << "eraseClass 7 ..." << endl; - U.eraseClass(7); - print(U); - - cout << "done" << endl; - - cout << (passed ? "All tests passed." : "Some of the tests failed!!!") - << endl; - - return passed ? 0 : 1; -}