# HG changeset patch
# User beckerjc
# Date 1083185718 0
# Node ID 0ab31578af67cabec52d883af29357939d0b026a
# Parent  a11ddf8a6614b9534c9bbf084a42a9949503f534
Doc for the union-find structures.

diff -r a11ddf8a6614 -r 0ab31578af67 doc/Doxyfile
--- a/doc/Doxyfile	Wed Apr 28 16:25:34 2004 +0000
+++ b/doc/Doxyfile	Wed Apr 28 20:55:18 2004 +0000
@@ -405,6 +405,7 @@
                          ../src/work/alpar/list_graph.h \
                          ../src/work/athos/minlengthpaths.h \
                          ../src/work/klao/path.h \
+                         ../src/work/johanna/unionfind.h \
 			 ../src/work/marci/graph_wrapper.h	
                          
 
diff -r a11ddf8a6614 -r 0ab31578af67 src/work/johanna/unionfind.h
--- a/src/work/johanna/unionfind.h	Wed Apr 28 16:25:34 2004 +0000
+++ b/src/work/johanna/unionfind.h	Wed Apr 28 20:55:18 2004 +0000
@@ -2,6 +2,11 @@
 #ifndef HUGO_UNION_FIND_H
 #define HUGO_UNION_FIND_H
 
+//!ingroup auxdat
+//!\file
+//!\brief Union-Find data structures.
+
+
 #include <vector>
 #include <list>
 #include <utility>
@@ -11,6 +16,24 @@
 
 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>
   class UnionFind {
     
@@ -25,6 +48,12 @@
   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)
     {
@@ -45,6 +74,19 @@
       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();
@@ -53,6 +95,15 @@
       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);
@@ -72,6 +123,12 @@
       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);
@@ -86,6 +143,27 @@
   /*******************************************************/
 
 
+#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>
   struct UnionFindEnumItem {
@@ -105,6 +183,24 @@
       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>
   class UnionFindEnum {
 
@@ -124,10 +220,6 @@
     MapType& m;
     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;
       IIter next;
@@ -146,6 +238,14 @@
   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)
     {
 
@@ -163,10 +263,26 @@
 
     }
 
+    /**
+     * \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]);
@@ -202,11 +318,25 @@
       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]);
@@ -230,6 +360,40 @@
       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 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];
@@ -243,7 +407,7 @@
 	  return;
 	}
 	++la;
-	la->size = ma->size - 1; 
+	la->size = ma->size; 
 	la->my_class = ma->my_class;	
       }
 
@@ -251,10 +415,17 @@
 	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;
@@ -301,16 +472,51 @@
       }
     };
 
+    /**
+     * \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 {
       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;
@@ -351,23 +557,71 @@
     };
 
 
+
+    /**
+     * \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 );
       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
 
diff -r a11ddf8a6614 -r 0ab31578af67 src/work/johanna/unionfind_test.cc
--- a/src/work/johanna/unionfind_test.cc	Wed Apr 28 16:25:34 2004 +0000
+++ b/src/work/johanna/unionfind_test.cc	Wed Apr 28 20:55:18 2004 +0000
@@ -75,11 +75,19 @@
   check(U.size(5) == 2);
   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;
   U.erase(1);
   print(U);
@@ -92,11 +100,46 @@
   U.split(5);
   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);