lemon-0.x: comparison src/work/johanna/unionfind.h

equal deleted inserted replaced

-:bcbd2365ccca
+:9164eefa975a
 // -*- c++ -*- //
 #ifndef HUGO_UNION_FIND_H
 #define HUGO_UNION_FIND_H
+//!ingroup auxdat
+//!\file
+//!\brief Union-Find data structures.
 #include <vector>
 #include <list>
 #include <utility>
 #include <algorithm>
 #include <invalid.h>
 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 {
 public:
 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) {
 	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);
 	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 <typename T>
 struct UnionFindEnumItem {
 typedef std::list<UnionFindEnumItem> ItemList;
 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 <typename T, template <typename Item> class Map>
 class UnionFindEnum {
 typedef std::list<UnionFindEnumItem<T> > ItemList;
 private:
 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;
 while( (next = comp->parent) != comp ) {
 	comp = next;
 }
 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());
 ai->parent = ai;
 m.set(a, ai);
 }
+/**
+* \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]);
 }
 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 )
 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 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;
 	  classes.erase(ma->my_class);
 	  m.set(a,0);
 	  return;
 	}
 	++la;
-	la->size = ma->size - 1;
+	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
 	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<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;
 }
 	  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<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
 #endif //HUGO_UNION_FIND_H

changeset 478	8c74de352f80
parent 394	3a34c5626e52
child 481	54d8feda437b