UnionFind Class Reference

From an indexed set of elments, allows fast unioning of the elements into sets. More...

#include <unionfind.h>

Public Member Functions
	UnionFind (int entries=0)
void	Initialize (const int entries)
	Resize X to size entries, sets all sets Si={xi}.
void	Resize (const int entries)
	Resize X to size entries, sets all sets Si={xi}.
int	AddEntry ()
	Increment the size of X by 1, sets Sn={xn}.
int	FindSet (const int i)
	Returns the id of the set to which xi belongs.
int	Union (const int i, const int j)
	Unions the sets to which xi and xj belong.
void	GetSets (std::vector< int > &sets)
	Returns the sets to which the items belong, such that sets[i] = set(xi)
size_t	CountSets () const
	Counts the number of sets.
void	GetRoots (std::vector< int > &roots) const
	Returns the roots of all sets.
void	EnumerateSets (std::vector< std::vector< int > > &sets) const
	Returns the sets, by listing all items for each set.
void	EnumerateSet (int i, std::vector< int > &s) const
	Returns the entire set for item i.
bool	IsRoot (const int i) const
int	FindRoot (const int i) const

Detailed Description

From an indexed set of elments, allows fast unioning of the elements into sets.

From a set X={x1,x2,...} (such that |X| = entries), the sets are initialized to Si = {xi}. Larger sets are created by unioning the set of xi with that of xj using the Union() method.

The sets are referenced using unique integer identifiers from 0 to entries-1.

---

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

• unionfind.h
• unionfind.cpp