OpenWalnut  1.4.0
Public Member Functions | Private Attributes | Friends
WUnionFind Class Reference

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

#include <WUnionFind.h>

List of all members.

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.
size_t find (size_t x)
 Find the canonical element of the given element and do path compression.
boost::shared_ptr< std::set
< size_t > > 
getMaxSet ()
 Computes the set with maximum number of elements.
void merge (size_t i, size_t j)
 Merges two components (iow: makes a union) where the given elements are members of.

Private Attributes

std::vector< size_tm_component
 Stores for each index its ID.

Friends

class WUnionFindTest

Detailed Description

Implements a very simple union-find datastructure aka disjoint_sets.

Notes:
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 ( size_t  size) [explicit]

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

Parameters:
sizeNumber of elements

Definition at line 36 of file WUnionFind.cpp.

References m_component.


Member Function Documentation

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:
WOutOfBoundsIf x is bigger than the number of elements available
Parameters:
xThe 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 getMaxSet(), and merge().

boost::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 WUnionFindTest::testMaxSet().

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

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

Exceptions:
WOutOfBoundsIf i or j are bigger than the number of elements available
Parameters:
iElement of some component
jElement of some (maybe other) component

Definition at line 60 of file WUnionFind.cpp.

References find(), and m_component.

Referenced by WUnionFindTest::testMaxSet(), and WUnionFindTest::testUnionMergesToBiggerIndex().


Member Data Documentation

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: