1.1 --- a/doc/Doxyfile Wed Apr 28 16:25:34 2004 +0000
1.2 +++ b/doc/Doxyfile Wed Apr 28 20:55:18 2004 +0000
1.3 @@ -405,6 +405,7 @@
1.4 ../src/work/alpar/list_graph.h \
1.5 ../src/work/athos/minlengthpaths.h \
1.6 ../src/work/klao/path.h \
1.7 + ../src/work/johanna/unionfind.h \
1.8 ../src/work/marci/graph_wrapper.h
1.9
1.10
2.1 --- a/src/work/johanna/unionfind.h Wed Apr 28 16:25:34 2004 +0000
2.2 +++ b/src/work/johanna/unionfind.h Wed Apr 28 20:55:18 2004 +0000
2.3 @@ -2,6 +2,11 @@
2.4 #ifndef HUGO_UNION_FIND_H
2.5 #define HUGO_UNION_FIND_H
2.6
2.7 +//!ingroup auxdat
2.8 +//!\file
2.9 +//!\brief Union-Find data structures.
2.10 +
2.11 +
2.12 #include <vector>
2.13 #include <list>
2.14 #include <utility>
2.15 @@ -11,6 +16,24 @@
2.16
2.17 namespace hugo {
2.18
2.19 + //! \addtogroup auxdat
2.20 + //! @{
2.21 +
2.22 + /**
2.23 + * \brief A \e Union-Find data structure implementation
2.24 + *
2.25 + * The class implements the \e Union-Find data structure.
2.26 + * The union operation uses rank heuristic, while
2.27 + * the find operation uses path compresson.
2.28 + * This is a very simple but efficient implementation, providing
2.29 + * only four methods: join (union), find, insert and size.
2.30 + * For more features see the \ref UnionFindEnum class.
2.31 + *
2.32 + * \pre The elements are automatically added only if the map
2.33 + * given to the constructor was filled with -1's. Otherwise you
2.34 + * need to add all the elements by the \ref insert() method.
2.35 + */
2.36 +
2.37 template <typename T, typename TIntMap>
2.38 class UnionFind {
2.39
2.40 @@ -25,6 +48,12 @@
2.41 public:
2.42 UnionFind(TIntMap& m) : map(m) {}
2.43
2.44 + /**
2.45 + * \brief Returns the index of the element's component.
2.46 + *
2.47 + * The method returns the index of the element's component.
2.48 + * This is an integer between zero and the number of inserted elements.
2.49 + */
2.50
2.51 int find(T a)
2.52 {
2.53 @@ -45,6 +74,19 @@
2.54 return comp;
2.55 }
2.56
2.57 + /**
2.58 + * \brief Insert a new element into the structure.
2.59 + *
2.60 + * This method inserts a new element into the data structure.
2.61 + *
2.62 + * It is not required to use this method:
2.63 + * if the map given to the constructor was filled
2.64 + * with -1's then it is called automatically
2.65 + * on the first \ref find or \ref join.
2.66 + *
2.67 + * The method returns the index of the new component.
2.68 + */
2.69 +
2.70 int insert(T a)
2.71 {
2.72 int n = data.size();
2.73 @@ -53,6 +95,15 @@
2.74 return n;
2.75 }
2.76
2.77 + /**
2.78 + * \brief Joining the components of element \e a and element \e b.
2.79 + *
2.80 + * This is the \e union operation of the Union-Find structure.
2.81 + * Joins the component of elemenent \e a and component of
2.82 + * element \e b. If \e a and \e b are in the same component then
2.83 + * it returns false otherwise it returns true.
2.84 + */
2.85 +
2.86 bool join(T a, T b)
2.87 {
2.88 int ca = find(a);
2.89 @@ -72,6 +123,12 @@
2.90 return true;
2.91 }
2.92
2.93 + /**
2.94 + * \brief Returns the size of the component of element \e a.
2.95 + *
2.96 + * Returns the size of the component of element \e a.
2.97 + */
2.98 +
2.99 int size(T a)
2.100 {
2.101 int ca = find(a);
2.102 @@ -86,6 +143,27 @@
2.103 /*******************************************************/
2.104
2.105
2.106 +#ifdef DEVELOPMENT_DOCS
2.107 +
2.108 + /**
2.109 + * \brief The auxiliary class for the \ref UnionFindEnum class.
2.110 + *
2.111 + * In the \ref UnionFindEnum class all components are represented as
2.112 + * a std::list.
2.113 + * Items of these lists are UnionFindEnumItem structures.
2.114 + *
2.115 + * The class has four fields:
2.116 + * - T me - the actual element
2.117 + * - IIter parent - the parent of the element in the union-find structure
2.118 + * - int size - the size of the component of the element.
2.119 + * Only valid if the element
2.120 + * is the leader of the component.
2.121 + * - CIter my_class - pointer into the list of components
2.122 + * pointing to the component of the element.
2.123 + * Only valid if the element is the leader of the component.
2.124 + */
2.125 +
2.126 +#endif
2.127
2.128 template <typename T>
2.129 struct UnionFindEnumItem {
2.130 @@ -105,6 +183,24 @@
2.131 me(_me), size(1), my_class(_my_class) {}
2.132 };
2.133
2.134 +
2.135 + /**
2.136 + * \brief A \e Union-Find data structure implementation which
2.137 + * is able to enumerate the components.
2.138 + *
2.139 + * The class implements an \e Union-Find data structure
2.140 + * which is able to enumerate the components and the items in
2.141 + * a component. If you don't need this feature then perhaps it's
2.142 + * better to use the \ref UnionFind class which is more efficient.
2.143 + *
2.144 + * The union operation uses rank heuristic, while
2.145 + * the find operation uses path compresson.
2.146 + *
2.147 + * \pre You
2.148 + * need to add all the elements by the \ref insert() method.
2.149 + */
2.150 +
2.151 +
2.152 template <typename T, template <typename Item> class Map>
2.153 class UnionFindEnum {
2.154
2.155 @@ -124,10 +220,6 @@
2.156 MapType& m;
2.157 ClassList classes;
2.158
2.159 - // IIter where(const T &a) { return m[a]; }
2.160 - // IIter parent(IIter a) { return a->parent; }
2.161 - // P sibling(P a) { return &m[a->sibling]; }
2.162 -
2.163 IIter _find(IIter a) const {
2.164 IIter comp = a;
2.165 IIter next;
2.166 @@ -146,6 +238,14 @@
2.167 public:
2.168 UnionFindEnum(MapType& _m) : m(_m) {}
2.169
2.170 +
2.171 + /**
2.172 + * \brief Insert the given element into a new component.
2.173 + *
2.174 + * This method creates a new component consisting only of the
2.175 + * given element.
2.176 + */
2.177 +
2.178 void insert(const T &a)
2.179 {
2.180
2.181 @@ -163,10 +263,26 @@
2.182
2.183 }
2.184
2.185 + /**
2.186 + * \brief Find the leader of the component of the given element.
2.187 + *
2.188 + * The method returns the leader of the component of the given element.
2.189 + */
2.190 +
2.191 T find(const T &a) const {
2.192 return _find(m[a])->me;
2.193 }
2.194
2.195 +
2.196 + /**
2.197 + * \brief Joining the component of element \e a and element \e b.
2.198 + *
2.199 + * This is the \e union operation of the Union-Find structure.
2.200 + * Joins the component of elemenent \e a and component of
2.201 + * element \e b. If \e a and \e b are in the same component then
2.202 + * returns false else returns true.
2.203 + */
2.204 +
2.205 bool join(T a, T b) {
2.206
2.207 IIter ca = _find(m[a]);
2.208 @@ -202,11 +318,25 @@
2.209 return true;
2.210 }
2.211
2.212 +
2.213 + /**
2.214 + * \brief Returns the size of the component of element \e a.
2.215 + *
2.216 + * Returns the size of the component of element \e a.
2.217 + */
2.218 +
2.219 int size(const T &a) const {
2.220 return _find(m[a])->size;
2.221 }
2.222
2.223 -
2.224 +
2.225 + /**
2.226 + * \brief Split up the component of the element.
2.227 + *
2.228 + * Splitting the component of the element into sigleton
2.229 + * components (component of size one).
2.230 + */
2.231 +
2.232 void split(const T &a) {
2.233
2.234 IIter ca = _find(m[a]);
2.235 @@ -230,6 +360,40 @@
2.236 return;
2.237 }
2.238
2.239 +
2.240 + /**
2.241 + * \brief Set the given element to the leader element of its component.
2.242 + *
2.243 + * Set the given element to the leader element of its component.
2.244 + */
2.245 +
2.246 + void makeRep(const T &a) {
2.247 +
2.248 + IIter ia = m[a];
2.249 + IIter la = _find(ia);
2.250 + if (la == ia) return;
2.251 +
2.252 + ia->my_class = la->my_class;
2.253 + la->my_class = 0;
2.254 +
2.255 + ia->size = la->size;
2.256 +
2.257 + CIter l = ia->my_class;
2.258 + l->splice(l->begin(),*l,ia);
2.259 +
2.260 + ia->parent = ia;
2.261 + la->parent = ia;
2.262 + }
2.263 +
2.264 +
2.265 + /**
2.266 + * \brief Remove the given element from the structure.
2.267 + *
2.268 + * Remove the given element from the structure.
2.269 + *
2.270 + * Removes the element from its component and if the component becomes
2.271 + * empty then removes that component from the component list.
2.272 + */
2.273 void erase(const T &a) {
2.274
2.275 IIter ma = m[a];
2.276 @@ -243,7 +407,7 @@
2.277 return;
2.278 }
2.279 ++la;
2.280 - la->size = ma->size - 1;
2.281 + la->size = ma->size;
2.282 la->my_class = ma->my_class;
2.283 }
2.284
2.285 @@ -251,10 +415,17 @@
2.286 i->parent = la;
2.287 }
2.288
2.289 + la->size--;
2.290 la->my_class->erase(ma);
2.291 m.set(a,0);
2.292 }
2.293
2.294 + /**
2.295 + * \brief Removes the component of the given element from the structure.
2.296 + *
2.297 + * Removes the component of the given element from the structure.
2.298 + */
2.299 +
2.300 void eraseClass(const T &a) {
2.301 IIter ma = m[a];
2.302 if (ma == 0) return;
2.303 @@ -301,16 +472,51 @@
2.304 }
2.305 };
2.306
2.307 + /**
2.308 + * \brief Sets the iterator to point to the first component.
2.309 + *
2.310 + * Sets the iterator to point to the first component.
2.311 + *
2.312 + * With the \ref first, \ref valid and \ref next methods you can
2.313 + * iterate through the components. For example:
2.314 + * \code
2.315 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
2.316 + * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
2.317 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::ClassIt iter;
2.318 + * for (U.first(iter); U.valid(iter); U.next(iter)) {
2.319 + * // iter is convertible to Graph::Node
2.320 + * cout << iter << endl;
2.321 + * }
2.322 + * \endcode
2.323 + */
2.324
2.325 ClassIt& first(ClassIt& it) const {
2.326 it.first(classes);
2.327 return it;
2.328 }
2.329
2.330 + /**
2.331 + * \brief Returns whether the iterator is valid.
2.332 + *
2.333 + * Returns whether the iterator is valid.
2.334 + *
2.335 + * With the \ref first, \ref valid and \ref next methods you can
2.336 + * iterate through the components. See the example here: \ref first.
2.337 + */
2.338 +
2.339 bool valid(ClassIt const &it) const {
2.340 return it.valid();
2.341 }
2.342
2.343 + /**
2.344 + * \brief Steps the iterator to the next component.
2.345 + *
2.346 + * Steps the iterator to the next component.
2.347 + *
2.348 + * With the \ref first, \ref valid and \ref next methods you can
2.349 + * iterate through the components. See the example here: \ref first.
2.350 + */
2.351 +
2.352 ClassIt& next(ClassIt& it) const {
2.353 it.next(classes);
2.354 return it;
2.355 @@ -351,23 +557,71 @@
2.356 };
2.357
2.358
2.359 +
2.360 + /**
2.361 + * \brief Sets the iterator to point to the first element of the component.
2.362 + *
2.363 + * \anchor first2
2.364 + * Sets the iterator to point to the first element of the component.
2.365 + *
2.366 + * With the \ref first2 "first", \ref valid2 "valid"
2.367 + * and \ref next2 "next" methods you can
2.368 + * iterate through the elements of a component. For example
2.369 + * (iterating through the component of the node \e node):
2.370 + * \code
2.371 + * Graph::Node node = ...;
2.372 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::MapType map(G);
2.373 + * UnionFindEnum<Graph::Node, Graph::NodeMap> U(map);
2.374 + * UnionFindEnum<Graph::Node, Graph::NodeMap>::ItemIt iiter;
2.375 + * for (U.first(iiter, node); U.valid(iiter); U.next(iiter)) {
2.376 + * // iiter is convertible to Graph::Node
2.377 + * cout << iiter << endl;
2.378 + * }
2.379 + * \endcode
2.380 + */
2.381 +
2.382 ItemIt& first(ItemIt& it, const T& a) const {
2.383 it.first( * _find(m[a])->my_class );
2.384 return it;
2.385 }
2.386
2.387 + /**
2.388 + * \brief Returns whether the iterator is valid.
2.389 + *
2.390 + * \anchor valid2
2.391 + * Returns whether the iterator is valid.
2.392 + *
2.393 + * With the \ref first2 "first", \ref valid2 "valid"
2.394 + * and \ref next2 "next" methods you can
2.395 + * iterate through the elements of a component.
2.396 + * See the example here: \ref first2 "first".
2.397 + */
2.398 +
2.399 bool valid(ItemIt const &it) const {
2.400 return it.valid();
2.401 }
2.402
2.403 + /**
2.404 + * \brief Steps the iterator to the next component.
2.405 + *
2.406 + * \anchor next2
2.407 + * Steps the iterator to the next component.
2.408 + *
2.409 + * With the \ref first2 "first", \ref valid2 "valid"
2.410 + * and \ref next2 "next" methods you can
2.411 + * iterate through the elements of a component.
2.412 + * See the example here: \ref first2 "first".
2.413 + */
2.414 +
2.415 ItemIt& next(ItemIt& it) const {
2.416 it.next();
2.417 return it;
2.418 }
2.419
2.420 + };
2.421
2.422
2.423 - };
2.424 + //! @}
2.425
2.426 } //namespace hugo
2.427
3.1 --- a/src/work/johanna/unionfind_test.cc Wed Apr 28 16:25:34 2004 +0000
3.2 +++ b/src/work/johanna/unionfind_test.cc Wed Apr 28 20:55:18 2004 +0000
3.3 @@ -75,11 +75,19 @@
3.4 check(U.size(5) == 2);
3.5 cout << "size of the class of 6: " << U.size(6) << endl;
3.6 check(U.size(6) == 1);
3.7 + cout << "size of the class of 2: " << U.size(2) << endl;
3.8 + check(U.size(2) == 3);
3.9
3.10 cout <<"erase 1: " << endl;
3.11 U.erase(1);
3.12 print(U);
3.13
3.14 + cout << "size of the class of 4: " << U.size(4) << endl;
3.15 + check(U.size(4) == 2);
3.16 + cout << "size of the class of 2: " << U.size(2) << endl;
3.17 + check(U.size(2) == 2);
3.18 +
3.19 +
3.20 cout <<"erase 1: " << endl;
3.21 U.erase(1);
3.22 print(U);
3.23 @@ -92,11 +100,46 @@
3.24 U.split(5);
3.25 print(U);
3.26
3.27 +
3.28 + cout << "size of the class of 4: " << U.size(4) << endl;
3.29 + check(U.size(4) == 2);
3.30 + cout << "size of the class of 3: " << U.size(3) << endl;
3.31 + check(U.size(3) == 1);
3.32 + cout << "size of the class of 2: " << U.size(2) << endl;
3.33 + check(U.size(2) == 2);
3.34 +
3.35 +
3.36 cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
3.37 check(U.join(3,4));
3.38 check(!U.join(2,4));
3.39 print(U);
3.40
3.41 +
3.42 + cout << "size of the class of 4: " << U.size(4) << endl;
3.43 + check(U.size(4) == 3);
3.44 + cout << "size of the class of 3: " << U.size(3) << endl;
3.45 + check(U.size(3) == 3);
3.46 + cout << "size of the class of 2: " << U.size(2) << endl;
3.47 + check(U.size(2) == 3);
3.48 +
3.49 + cout << "makeRep(4)" << endl;
3.50 + U.makeRep(4);
3.51 + print(U);
3.52 + cout << "makeRep(3)" << endl;
3.53 + U.makeRep(3);
3.54 + print(U);
3.55 + cout << "makeRep(2)" << endl;
3.56 + U.makeRep(2);
3.57 + print(U);
3.58 +
3.59 + cout << "size of the class of 4: " << U.size(4) << endl;
3.60 + check(U.size(4) == 3);
3.61 + cout << "size of the class of 3: " << U.size(3) << endl;
3.62 + check(U.size(3) == 3);
3.63 + cout << "size of the class of 2: " << U.size(2) << endl;
3.64 + check(U.size(2) == 3);
3.65 +
3.66 +
3.67 cout << "eraseClass 4 ..." << endl;
3.68 U.eraseClass(4);
3.69 print(U);