OpenWalnut  1.4.0
WUnionFind.h
1 //---------------------------------------------------------------------------
2 //
3 // Project: OpenWalnut ( http://www.openwalnut.org )
4 //
5 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
6 // For more information see http://www.openwalnut.org/copying
7 //
8 // This file is part of OpenWalnut.
9 //
10 // OpenWalnut is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // OpenWalnut is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
22 //
23 //---------------------------------------------------------------------------
24 
25 #ifndef WUNIONFIND_H
26 #define WUNIONFIND_H
27 
28 #include <set>
29 #include <vector>
30 
31 #ifndef Q_MOC_RUN
32 #include <boost/shared_ptr.hpp>
33 #endif
34 
35 
36 /**
37  * Implements a very simple union-find datastructure aka disjoint_sets.
38  * \note I know there is a boost solution on that, but I didn't get it to work and I don't know how fast it is:
39  * http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html
40  *
41  * And you may use it like this:
42  \verbatim
43  typedef std::vector< SizeType > RankVector;
44  typedef RankVector::iterator RankRAIter;
45  typedef std::vector< VertexDescriptor > ParentVector;
46  typedef ParentVector::iterator ParentRAIter;
47 
48  typedef boost::iterator_property_map< RankRAIter,
49  IndexMap,
50  std::iterator_traits< RankRAIter >::value_type,
51  std::iterator_traits< RankRAIter >::reference > RankMap;
52 
53  typedef boost::iterator_property_map< ParentRAIter,
54  IndexMap,
55  std::iterator_traits< ParentRAIter >::value_type,
56  std::iterator_traits< ParentRAIter >::reference > ParentMap;
57 
58  RankVector ranks( d_numOfVertices );
59  ParentVector parents( d_numOfVertices );
60  boost::disjoint_sets< RankMap, ParentMap > dset( boost::make_iterator_property_map( ranks.begin(),
61  boost::get( boost::vertex_index, g ),
62  ranks[0] ),
63  boost::make_iterator_property_map( parents.begin(),
64  boost::get( boost::vertex_index, g ),
65  parents[0] )
66  );
67 
68  // After the disjoint set dset is construct, we can use
69 
70  dset.make_set( u ); // make u a set
71  dset.link( u, v ); // u and v are belonging to the same set.
72  dset.find_set( u ); // find the set owning u. A representative of the set is returned
73  \endverbatim
74  */
76 {
77 friend class WUnionFindTest;
78 public:
79  /**
80  * Creates a new union find datastructure with size elements where each
81  * element is initialized as a single set.
82  *
83  * \param size Number of elements
84  */
85  explicit WUnionFind( size_t size );
86 
87  /**
88  * Find the canonical element of the given element and do path compression
89  *
90  * http://en.wikipedia.org/wiki/Disjoint-set_data_structure
91  *
92  * depth of recursion is said to be small, therefore, recursion
93  * works fine for large dataset, too.
94  *
95  * \throw WOutOfBounds If x is bigger than the number of elements available
96  *
97  * \param x The x'th element
98  * \return The canonical element of that component which x is also member of
99  */
100  size_t find( size_t x );
101 
102  /**
103  * Computes the set with maximum number of elements. If there are more than one candidate one is
104  * picked arbitrarily.
105  *
106  * \return Reference to the set of indices all beloning to a set of maximal size.
107  */
108  boost::shared_ptr< std::set< size_t > > getMaxSet();
109 
110  /**
111  * Merges two components (iow: makes a union) where the given elements are
112  * members of.
113  *
114  * \throw WOutOfBounds If i or j are bigger than the number of elements available
115  *
116  * \param i Element of some component
117  * \param j Element of some (maybe other) component
118  */
119  void merge( size_t i, size_t j );
120 
121 private:
122  std::vector< size_t > m_component; //!< Stores for each index its ID
123 };
124 
125 
126 #endif // WUNIONFIND_H
Implements a very simple union-find datastructure aka disjoint_sets.
Definition: WUnionFind.h:75
void merge(size_t i, size_t j)
Merges two components (iow: makes a union) where the given elements are members of.
Definition: WUnionFind.cpp:60
std::vector< size_t > m_component
Stores for each index its ID.
Definition: WUnionFind.h:122
size_t find(size_t x)
Find the canonical element of the given element and do path compression.
Definition: WUnionFind.cpp:45
boost::shared_ptr< std::set< size_t > > getMaxSet()
Computes the set with maximum number of elements.
Definition: WUnionFind.cpp:82
Unit tests the WUnionFind datastructure.
WUnionFind(size_t size)
Creates a new union find datastructure with size elements where each element is initialized as a sing...
Definition: WUnionFind.cpp:36