Changeset 462:0ab31578af67 in lemon-0.x for src/work

Timestamp:

04/28/04 22:55:18 (21 years ago)

Author:

beckerjc

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@613

Message:

Doc for the union-find structures.

Location:

src/work/johanna

Files:

• unionfind.h (modified) (20 diffs)
• unionfind_test.cc (modified) (2 diffs)

src/work/johanna/unionfind.h

@@ -2 +2 @@
 #ifndef HUGO_UNION_FIND_H
 #define HUGO_UNION_FIND_H
+
+//!ingroup auxdat
+//!\file
+//!\brief Union-Find data structures.
+
 
 #include <vector>
@@ -11 +16 @@
 
 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 <typename T, typename TIntMap>
@@ -26 +49 @@
     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)
@@ -45 +74 @@
       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)
@@ -54 +96 @@
     }
 
+    /**
+     * \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)
     {
@@ -73 +124 @@
     }
 
+    /**
+     * \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)
     {
@@ -87 +144 @@
 
 
+#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 <typename T>
@@ -105 +183 @@
       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 <typename T, template <typename Item> class Map>
@@ -125 +221 @@
     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;
@@ -147 +239 @@
     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)
     {
@@ -164 +264 @@
     }
 
+    /**
+     * \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) {
@@ -203 +319 @@
     }
 
+
+    /**
+     * \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) {
 
@@ -231 +361 @@
     }
 
+
+    /**
+     * \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) {
 
@@ -244 +408 @@
         }
         ++la;
-        la->size = ma->size - 1; 
+        la->size = ma->size; 
         la->my_class = ma->my_class;    
       }
@@ -252 +416 @@
       }
 
+      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) {
@@ -302 +473 @@
     };
 
+    /**
+     * \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<Graph::Node, Graph::NodeMap>::MapType map(G);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::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 {
@@ -308 +496 @@
     }
 
+    /**
+     * \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 {
@@ -352 +558 @@
 
 
+
+    /**
+     * \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<Graph::Node, Graph::NodeMap>::MapType map(G);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
+     * UnionFindEnum<Graph::Node, Graph::NodeMap>::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 );
@@ -357 +586 @@
     }
 
+    /**
+     * \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 {
@@ -366 +619 @@
     }
     
-
-
   };
 
+
+  //! @}
+
 } //namespace hugo
 

src/work/johanna/unionfind_test.cc

@@ -76 +76 @@
   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 <<"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;
@@ -93 +101 @@
   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;