| |
- 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
| |