libstatic._analyzer.unionfind.UnionFind

class documentation

class UnionFind(Generic[T], Collection[T]): (source)

Constructor: UnionFind(elements)

View In Hierarchy

Union-find disjoint sets datastructure.

Union-find is a data structure that maintains disjoint set (called connected components or components in short) membership, and makes it easier to merge (union) two components, and to find if two elements are connected (i.e., belong to the same component).

This implements the "weighted-quick-union-with-path-compression" union-find algorithm. Only works if elements are immutable objects.

Worst case for union and find: (N + Mlog*N), with N elements and M unions. The function log* is the number of times needed to take log of a number until reaching 1. In practice, the amortized cost of each operation is nearly linear [1].

Terms

Component
Elements belonging to the same disjoint set
Connected
Two elements are connected if they belong to the same component.
Union
The operation where two components are merged into one.
Root
An internal representative of a disjoint set.
Find
The operation to find the root of a disjoint set.

Parameters

elements : NoneType or container, optional, default: None
The initial list of elements.

Attributes

n_elts : int
Number of elements.
n_comps : int
Number of distjoint sets or components.
[1]http://algs4.cs.princeton.edu/lectures/
Method __contains__ Undocumented
Method __getitem__ Undocumented
Method __init__ Undocumented
Method __iter__ Undocumented
Method __len__ Undocumented
Method __repr__ Undocumented
Method __str__ Undocumented
Method add Add a single disjoint element.
Method component Find the connected component containing the given element.
Method components Return the list of connected components.
Method connected Return whether the two given elements belong to the same component.
Method copy Copy this union-find into a fresh one.
Method remove Remove an item from the collection.
Method union Merge the components of the two given elements into one. Initialize elements if they are not already in the collection.
Class Variable free Undocumented
Instance Variable n_comps Undocumented
Instance Variable n_elts Undocumented
Method _find Find the index of root of the disjoint set containing the given element.
Instance Variable _elts Undocumented
Instance Variable _free Undocumented
Instance Variable _indx Undocumented
Instance Variable _nb_rm Undocumented
Instance Variable _next Undocumented
Instance Variable _par Undocumented
Instance Variable _removed Undocumented
Instance Variable _siz Undocumented
def __contains__(self, x: object) -> bool: (source)

Undocumented

def __getitem__(self, index: int) -> T: (source)

Undocumented

def __init__(self, elements: Iterable[T] | None = None): (source)

Undocumented

def __iter__(self) -> Iterator[T]: (source)

Undocumented

def __len__(self) -> int: (source)

Undocumented

def __repr__(self) -> str: (source)

Undocumented

def __str__(self) -> str: (source)

Undocumented

def add(self, x: T): (source)

Add a single disjoint element.

Parameters

x : immutable object

Returns

None

def component(self, x: T) -> Collection[T]: (source)

Find the connected component containing the given element.

Parameters

x : immutable object

Returns

Insertion ordered set, first element is the root.

Raises

ValueError
If the given element is not found.
def components(self) -> list[Collection[T]]: (source)

Return the list of connected components.

Returns

list
A list of insertion ordered set, first element is the root.
def connected(self, x: T, y: T) -> bool: (source)

Return whether the two given elements belong to the same component.

Parameters

x : immutable object y : immutable object

Returns

bool
True if x and y are connected, false otherwise.
def copy(self) -> UnionFind[T]: (source)

Copy this union-find into a fresh one.

def remove(self, x: T): (source)

Remove an item from the collection.

Raises

ValueError
If the element is not in the collection.
def union(self, x: T, y: T): (source)

Merge the components of the two given elements into one. Initialize elements if they are not already in the collection.

Parameters

x : immutable object y : immutable object

free = (source)

Undocumented

n_comps: int = (source)

Undocumented

n_elts: int = (source)

Undocumented

def _find(self, x: T) -> int: (source)

Find the index of root of the disjoint set containing the given element.

Parameters

x : immutable object

Returns

int
The (index of the) root.

Raises

ValueError
If the given element is not found.

Note

Despite beeing one of the core method of a 'Union-Find' structure, _find() is marked as private. This is because the implementation of the removal feature implies that _find might return the index of a removed element. So the returned number shoud not be used to access a element of the union, simply to act like a representant object for it's set.

_elts: list[T | _Free] = (source)

Undocumented

_free: set[int] = (source)

Undocumented

_indx: dict[T, int] = (source)

Undocumented

_nb_rm: list[int] = (source)

Undocumented

_next: int = (source)

Undocumented

_par: list[int] = (source)

Undocumented

_removed: set[int] = (source)

Undocumented

_siz: list[int] = (source)

Undocumented