Simulation Modeling Tool Kit
Public Types | Public Member Functions | Public Attributes | List of all members
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

newSet ()
 Add a new set (disjoint from all others).
mergeSets (T a, T b)
 Connect two disjoint sets, returning the ID of their union (which may not be a or b).
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.
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: