3.4. Union Find

The uf module includes

cereeberus.compute.uf.signedDistToLine2Pts(pt, p0, p1)

return a signed distance to a line where line is defined as two points

positive sign refers to “above” the line or “left” of a vertical line to get the expected sign of “right” is positive, the vertical line will be inverted back under the “angle_sign” in _computeNodeHeights() of MergeTree.py

cereeberus.compute.uf.getSortedNodeHeights(graph, filtration, precision=5)

compute heights of each node given filtration line and return as sorted list of node height tuples, rounded to given precision

class cereeberus.compute.uf.UnionFind(size, verbose=False)

Array index implementation of UnionFind inspired by William Fiset’s java implementation (github.com/williamfiset/data-structures) with special rerooting function to handle merge tree construction

__init__(size, verbose=False)

create internal union find structure represented as array with all nodes pointing to themselves (individual components)

getNumComponents()

get number of total connected components

getSizeOfComponent(c)

get size of c’s connected component

getSize()

get input max size of UF structure

rerootComponent(c, newRoot)

given a component and any connected node, make that node the new root of the component - key for building up a mergetree

find(c)

return the root of the connected component of c

union(c1, c2)

union c1 and c2 connected components

isFullyConnected()

if all “size” # of nodes are fully connected, return True

printAll()

print all nodes and the connected components of each