Index: src/work/johanna/unionfind.h
===================================================================
--- src/work/johanna/unionfind.h	(revision 394)
+++ src/work/johanna/unionfind.h	(revision 462)
@@ -2,4 +2,9 @@
 #ifndef HUGO_UNION_FIND_H
 #define HUGO_UNION_FIND_H
+
+//!ingroup auxdat
+//!\file
+//!\brief Union-Find data structures.
+
 
 #include <vector>
@@ -11,4 +16,22 @@
 
 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,4 +49,10 @@
     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,4 +74,17 @@
       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,4 +96,13 @@
     }
 
+    /**
+     * \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,4 +124,10 @@
     }
 
+    /**
+     * \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,4 +144,25 @@
 
 
+#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,4 +183,22 @@
       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,8 +221,4 @@
     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,4 +239,12 @@
     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,7 +264,23 @@
     }
 
+    /**
+     * \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,9 +319,23 @@
     }
 
+
+    /**
+     * \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,4 +361,38 @@
     }
 
+
+    /**
+     * \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,5 +408,5 @@
 	}
 	++la;
-	la->size = ma->size - 1; 
+	la->size = ma->size; 
 	la->my_class = ma->my_class;	
       }
@@ -252,7 +416,14 @@
       }
 
+      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,4 +473,21 @@
     };
 
+    /**
+     * \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,7 +496,25 @@
     }
 
+    /**
+     * \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,4 +558,27 @@
 
 
+
+    /**
+     * \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,7 +586,31 @@
     }
 
+    /**
+     * \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,8 +619,9 @@
     }
     
-
-
   };
 
+
+  //! @}
+
 } //namespace hugo
 
