WUnionFind Class Reference

Implements a very simple union-find datastructure aka disjoint_sets. More...

#include <WUnionFind.h>

Collaboration diagram for WUnionFind:

Public Member Functions
	WUnionFind (size_t size)
	Creates a new union find datastructure with size elements where each element is initialized as a single set. More...
size_t	find (size_t x)
	Find the canonical element of the given element and do path compression. More...
std::shared_ptr< std::set< size_t > >	getMaxSet ()
	Computes the set with maximum number of elements. More...
void	merge (size_t i, size_t j)
	Merges two components (iow: makes a union) where the given elements are members of. More...

Private Attributes
std::vector< size_t >	m_component
	Stores for each index its ID. More...

Friends
class	WUnionFindTest
	Access for test class. More...

Detailed Description

Implements a very simple union-find datastructure aka disjoint_sets.

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: http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html

And you may use it like this:

typedef std::vector< SizeType >          RankVector;
typedef RankVector::iterator             RankRAIter;
typedef std::vector< VertexDescriptor >  ParentVector;
typedef ParentVector::iterator           ParentRAIter;

typedef boost::iterator_property_map< RankRAIter,
                                      IndexMap,
                                      std::iterator_traits< RankRAIter >::value_type,
                                      std::iterator_traits< RankRAIter >::reference > RankMap;

typedef boost::iterator_property_map< ParentRAIter,
                                      IndexMap,
                                      std::iterator_traits< ParentRAIter >::value_type,
                                      std::iterator_traits< ParentRAIter >::reference > ParentMap;

RankVector   ranks( d_numOfVertices );
ParentVector parents( d_numOfVertices );
boost::disjoint_sets< RankMap, ParentMap > dset( boost::make_iterator_property_map( ranks.begin(),
                                                                                    boost::get( boost::vertex_index, g ),
                                                                                    ranks[0] ),
                                                 boost::make_iterator_property_map( parents.begin(),
                                                                                    boost::get( boost::vertex_index, g ),
                                                                                    parents[0] )
                                               );

// After the disjoint set dset is construct, we can use

dset.make_set( u ); // make u a set
dset.link( u, v );  // u and v are belonging to the same set.
dset.find_set( u ); // find the set owning u. A representative of the set is returned

Definition at line 73 of file WUnionFind.h.

Constructor & Destructor Documentation

WUnionFind()

WUnionFind::WUnionFind ( size_t  size )

explicit

Creates a new union find datastructure with size elements where each element is initialized as a single set.

Parameters

size	Number of elements

Definition at line 36 of file WUnionFind.cpp.

References m_component.

Member Function Documentation

find()

size_t WUnionFind::find

(

size_t

x

)

Find the canonical element of the given element and do path compression.

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

depth of recursion is said to be small, therefore, recursion works fine for large dataset, too.

Exceptions

WOutOfBounds

If x is bigger than the number of elements available

Parameters

x	The x'th element

Returns

The canonical element of that component which x is also member of

Definition at line 45 of file WUnionFind.cpp.

References m_component.

Referenced by WJoinContourTree::buildJoinTree(), tm_utils::componentDecomposition(), getMaxSet(), and merge().

Here is the caller graph for this function:

getMaxSet()

std::shared_ptr< std::set< size_t > > WUnionFind::getMaxSet

(

)

Computes the set with maximum number of elements.

If there are more than one candidate one is picked arbitrarily.

Returns

Reference to the set of indices all beloning to a set of maximal size.

Definition at line 82 of file WUnionFind.cpp.

References find(), and m_component.

Referenced by WJoinContourTree::getVolumeVoxelsEnclosedByIsoSurface(), and WUnionFindTest::testMaxSet().

Here is the call graph for this function:

Here is the caller graph for this function:

merge()

void WUnionFind::merge	(	size_t	i,
		size_t	j
	)

Merges two components (iow: makes a union) where the given elements are members of.

Exceptions

WOutOfBounds

If i or j are bigger than the number of elements available

Parameters

i	Element of some component
j	Element of some (maybe other) component

Definition at line 60 of file WUnionFind.cpp.

References find(), and m_component.

Referenced by WJoinContourTree::buildJoinTree(), tm_utils::componentDecomposition(), WJoinContourTree::getVolumeVoxelsEnclosedByIsoSurface(), WUnionFindTest::testMaxSet(), and WUnionFindTest::testUnionMergesToBiggerIndex().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

WUnionFindTest

friend class WUnionFindTest

friend

Access for test class.

Definition at line 75 of file WUnionFind.h.

Member Data Documentation

m_component

std::vector< size_t > WUnionFind::m_component

private

Stores for each index its ID.

Definition at line 120 of file WUnionFind.h.

Referenced by find(), getMaxSet(), merge(), WUnionFindTest::testUnionMergesToBiggerIndex(), and WUnionFind().

---

The documentation for this class was generated from the following files:

• WUnionFind.h
• WUnionFind.cpp