smtk::common::UnionFind< T > Class Template Reference

A disjoint-set structure for fast union-find operations. More...

#include <UnionFind.h>

Collaboration diagram for smtk::common::UnionFind< T >:

Public Types
typedef T	value_type
	Each value used to identify a set is of this type.

Public Member Functions
T	newSet ()
	Add a new set (disjoint from all others).
T	mergeSets (T a, T b)
	Connect two disjoint sets, returning the ID of their union (which may not be a or b).
T	find (T src)
	Find the parent of a set.
std::set< T >	roots ()
	Get the current root sets (entries in Sets whose parents are themselves)
void	collapseIds (std::map< T, T > &collapsedIds, T startCount)
	Popoulate a map with remaining disjoint sets numbered starting at startCount.
T	size () const
	Return the number of sets that have been created.

Public Attributes
std::vector< UnionFindSet< T > >	m_sets

Detailed Description

template<typename T>
class smtk::common::UnionFind< T >

A disjoint-set structure for fast union-find operations.

This class is templated on the integer set-id type. The template parameter should be a signed integer; smaller sizes may improve performance when a smaller number of unique sets is acceptable.

A negative integer is used to identify an invalid value; for instance, calling Find() on an integer not returned by NewSet or MergeSets is an error and will return -1.

---

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

• /home/docs/checkouts/readthedocs.org/user_builds/smtk/checkouts/latest/smtk/common/UnionFind.h