Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

UnionFind< S > Class Template Reference

General union/find implementation. More...

#include <UnionFind.hpp>

List of all members.

Public Member Functions

 UnionFind ()
 Constructor.
void Clear ()
 Sets all elements to be isolated.
bool IsRoot (int x) const
 Returns true if x is the captain of a group.
int GetRoot (int x) const
 Gets the captain of x's group.
int UnionGroups (int x, int y)
 Unions two sets of elements.

Private Attributes

std::vector< int > m_sets

Static Private Attributes

static const int ISOLATED = -1
 Flag denoting that the element is its own group.

Detailed Description

template<int S>
class UnionFind< S >

General union/find implementation.

Definition at line 19 of file UnionFind.hpp.


Constructor & Destructor Documentation

template<int S>
UnionFind< S >::UnionFind (  )  [inline]

Constructor.

All elements are initially isolated.

Definition at line 46 of file UnionFind.hpp.

References UnionFind< S >::Clear().


Member Function Documentation

template<int S>
void UnionFind< S >::Clear (  )  [inline]

Sets all elements to be isolated.

Definition at line 53 of file UnionFind.hpp.

References UnionFind< S >::ISOLATED, and UnionFind< S >::m_sets.

Referenced by UnionFind< S >::UnionFind().

template<int S>
int UnionFind< S >::GetRoot ( int  x  )  const [inline]

Gets the captain of x's group.

Definition at line 66 of file UnionFind.hpp.

References UnionFind< S >::m_sets.

Referenced by UnionFind< S >::UnionGroups().

template<int S>
bool UnionFind< S >::IsRoot ( int  x  )  const [inline]

Returns true if x is the captain of a group.

Definition at line 60 of file UnionFind.hpp.

References UnionFind< S >::m_sets.

template<int S>
int UnionFind< S >::UnionGroups ( int  x,
int  y 
) [inline]

Unions two sets of elements.

Definition at line 75 of file UnionFind.hpp.

References UnionFind< S >::GetRoot(), and UnionFind< S >::m_sets.


Member Data Documentation

template<int S>
const int UnionFind< S >::ISOLATED = -1 [static, private]

Flag denoting that the element is its own group.

Definition at line 40 of file UnionFind.hpp.

Referenced by UnionFind< S >::Clear().

template<int S>
std::vector<int> UnionFind< S >::m_sets [mutable, private]

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


6 Jan 2011 Doxygen 1.6.3