unionfind
index
d:\projekte\research\persistence1d\python\unionfind.py

 
Classes
       
builtins.object
UnionFind

 
class UnionFind(builtins.object)
    UnionFind(NumElements)
 
Implements the Union-Find data structure.
 
It keeps track of elements
partitioned into a number of disjoint (non-overlapping) sets.
This data structure is required for merge trees and similar algorithms.
 
This implementation uses path compression in several places,
written with a merge-tree-like algorithm in mind.
 
A set is identified by the ID of the defining element (e.g., vertex).
 
Author: Tino Weinkauf
 
  Methods defined here:
ExtendSet(self, idxElementFrom, idxElementTo)
Extends a set from one element to the next.
 
@note The element identified by @idxElementFrom needs to belong to a set.
@note The element identified by @idxElementTo cannot belong to a set.
ExtendSetByID(self, idxRoot, idxElementTo)
Extends a set with a given set ID.
 
@note The set identified by @idxRoot needs to exist.
    In particular, this needs to be true: Find(idxRoot) == idxRoot
 
@note The element identified by @idxElementTo cannot belong to a set.
Find(self, idxElement)
Finds the ID of the set to which the element @idxElement belongs.
 
This function does not use compression, and therefore does not change any underlying data.
FindAndCompress(self, idxElement)
Finds the ID of the set to which the element @idxElement belongs, and compresses the entire path.
 
Compression means that all elements along the path point to the root of the set.
This makes future calls to any Find*() function faster.
FindMergeCompressTo(self, idxElement, idxRoot)
Find a path from @idxElement to its root and compresses the entire path to a new root.
 
Useful only when merging sets.
 
@returns true, if the root of @idxElement is already idxRoot, i.e., they belong to the same set.
@returns false, otherwise.
GetNumSets(self)
Returns the number of sets.
MakeSet(self, idxElement)
Creates a new set with the given @idxElement as a root.
Union(self, idxElementMergeThisOne, idxElementIntoThisOne)
Merges two sets into one.
 
The two sets are identified by their elements @idxElementMergeThisOne and @idxElementIntoThisOne.
The former set is merged into the latter, i.e., the latter one remains.
 
This function uses a lot of compression to speed-up later calls to any Find*() function.
__init__(self, NumElements)
Initializes the domain with @NumElements elements living in zero sets.

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

Data and other attributes defined here:
NOSET = -1