union_find: Union Find

In peekxc/Mapper: Topological Data Analysis using Mapper

Description

Exports a UnionFind data structure exposed as an Rcpp Module.

Usage

union_find(size)

Arguments

size	the size of the disjoint set

Details

UnionFind, also called a disjoint-set, is a data structure that allows efficient tracking and unioning of elements in terms of connected components. To use the structure, instantiate it with a given (fixed) size of components, and then union or find as needed. This implementation uses path compression to speed up successive find operations.

Value

A queryable disjoint-set structure.

Methods

• union Unions two elements together.

• union_all Unions all the elements in a given vector together.

• find Find which components a given element is associated with. If the elements given doesn't exist, -1 is returned.

• find_all Finds which component each element in a given vector is associated with. If the elements given doesn't exist, -1 is returned.

• print Prints the connected components.

• connected_components Retrieves the connected components as a integer vector.

References

Tarjan, Robert Endre. "Efficiency of a good but not linear set union algorithm." Journal of the ACM (JACM) 22.2 (1975): 215-225.

peekxc/Mapper documentation built on June 12, 2020, 2:14 a.m.