KrisLibrary
1.0.0
|
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 |
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.