SMTK
@SMTK_VERSION@
Simulation Modeling Tool Kit
|
A disjoint-set structure for fast union-find operations. More...
#include <UnionFind.h>
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 |
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.