OpenWalnut
1.4.0
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
src
core
common
datastructures
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
#include <boost/shared_ptr.hpp>
32
33
34
/**
35
* Implements a very simple union-find datastructure aka disjoint_sets.
36
* \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:
37
* http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html
38
*
39
* And you may use it like this:
40
\verbatim
41
typedef std::vector< SizeType > RankVector;
42
typedef RankVector::iterator RankRAIter;
43
typedef std::vector< VertexDescriptor > ParentVector;
44
typedef ParentVector::iterator ParentRAIter;
45
46
typedef boost::iterator_property_map< RankRAIter,
47
IndexMap,
48
std::iterator_traits< RankRAIter >::value_type,
49
std::iterator_traits< RankRAIter >::reference > RankMap;
50
51
typedef boost::iterator_property_map< ParentRAIter,
52
IndexMap,
53
std::iterator_traits< ParentRAIter >::value_type,
54
std::iterator_traits< ParentRAIter >::reference > ParentMap;
55
56
RankVector ranks( d_numOfVertices );
57
ParentVector parents( d_numOfVertices );
58
boost::disjoint_sets< RankMap, ParentMap > dset( boost::make_iterator_property_map( ranks.begin(),
59
boost::get( boost::vertex_index, g ),
60
ranks[0] ),
61
boost::make_iterator_property_map( parents.begin(),
62
boost::get( boost::vertex_index, g ),
63
parents[0] )
64
);
65
66
// After the disjoint set dset is construct, we can use
67
68
dset.make_set( u ); // make u a set
69
dset.link( u, v ); // u and v are belonging to the same set.
70
dset.find_set( u ); // find the set owning u. A representative of the set is returned
71
\endverbatim
72
*/
73
class
WUnionFind
74
{
75
friend
class
WUnionFindTest
;
76
public
:
77
/**
78
* Creates a new union find datastructure with size elements where each
79
* element is initialized as a single set.
80
*
81
* \param size Number of elements
82
*/
83
explicit
WUnionFind
(
size_t
size );
84
85
/**
86
* Find the canonical element of the given element and do path compression
87
*
88
* http://en.wikipedia.org/wiki/Disjoint-set_data_structure
89
*
90
* depth of recursion is said to be small, therefore, recursion
91
* works fine for large dataset, too.
92
*
93
* \throw WOutOfBounds If x is bigger than the number of elements available
94
*
95
* \param x The x'th element
96
* \return The canonical element of that component which x is also member of
97
*/
98
size_t
find
(
size_t
x );
99
100
/**
101
* Computes the set with maximum number of elements. If there are more than one candidate one is
102
* picked arbitrarily.
103
*
104
* \return Reference to the set of indices all beloning to a set of maximal size.
105
*/
106
boost::shared_ptr< std::set< size_t > >
getMaxSet
();
107
108
/**
109
* Merges two components (iow: makes a union) where the given elements are
110
* members of.
111
*
112
* \throw WOutOfBounds If i or j are bigger than the number of elements available
113
*
114
* \param i Element of some component
115
* \param j Element of some (maybe other) component
116
*/
117
void
merge
(
size_t
i,
size_t
j );
118
119
private
:
120
std::vector< size_t >
m_component
;
//!< Stores for each index its ID
121
};
122
123
124
#endif // WUNIONFIND_H
Generated by
1.8.4