# Changeset 462:0ab31578af67 in lemon-0.x for src/work/johanna/unionfind.h

Ignore:
Timestamp:
04/28/04 22:55:18 (18 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@613
Message:

Doc for the union-find structures.

File:
1 edited

Unmodified
Added
Removed
• ## src/work/johanna/unionfind.h

 r394 #ifndef HUGO_UNION_FIND_H #define HUGO_UNION_FIND_H //!ingroup auxdat //!\file //!\brief Union-Find data structures. #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 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) 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) } /** * \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) { } /** * \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) { #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 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> ClassList classes; //    IIter where(const T &a) { return m[a]; } //    IIter parent(IIter a) { return a->parent; } //    P sibling(P a) { return &m[a->sibling]; } IIter _find(IIter a) const { IIter comp = a; 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) { } /** * \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) { } /** * \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) { } /** * \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 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) { } ++la; la->size = ma->size - 1; la->size = ma->size; la->my_class = ma->my_class; } } 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) { }; /** * \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 { } /** * \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 { /** * \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 ); } /** * \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 { } }; //! @} } //namespace hugo
Note: See TracChangeset for help on using the changeset viewer.