protocol

union_find_protocol

Union-find data structure protocol.

Availability:
logtalk_load(union_find(loader))
Author: José Antonio Riaza Valverde; adapted to Logtalk by Paulo Moura
Version: 1:0:0
Date: 2022-02-17
Compilation flags:
static
Dependencies:
(none)
Remarks:
(none)
Inherited public predicates:
(none)

Public predicates

new/2

Creates a new union-find data structure with a list of elements as keys.

Compilation flags:
static
Template:
new(Elements,UnionFind)
Mode and number of proofs:
new(+list(element),?union_find) - zero_or_one

make_set/3

Makes a new set by creating a new element with a unique key Element, a rank of 0, and a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set.

Compilation flags:
static
Template:
make_set(UnionFind,Element,NewUnionFind)
Mode and number of proofs:
make_set(+union_find,+element,?union_find) - zero_or_one

union/4

Merges the two trees, if distinct, that contain the given elements. The trees are joined by attaching the shorter tree (by rank) to the root of the taller tree. Fails if any of the elements is not found.

Compilation flags:
static
Template:
union(UnionFind,Element1,Element2,NewUnionFind)
Mode and number of proofs:
union(+union_find,+element,+element,?union_find) - zero_or_one

union_all/3

Merges the distinct trees for all the given elements returning the resulting union-find data structure. Fails if any of the elements is not found.

Compilation flags:
static
Template:
union_all(UnionFind,Elements,NewUnionFind)
Mode and number of proofs:
union_all(+union_find,+list(element),?union_find) - zero_or_one

find/4

Finds the root element of a set by following the chain of parent pointers from the given element. Root is the representative member of the set to which the element belongs, and may be element itself. Fails if the element is not found.

Compilation flags:
static
Template:
find(UnionFind,Element,Root,NewUnionFind)
Mode and number of proofs:
find(+union_find,+element,?element,?union_find) - zero_or_one
Remarks:

  • Path compression: The structure of the tree containing the element is flattened by making every node point to the root whenever this predicate is used on it.

find/5

Same as the find/4 predicate, but returning also the rank of the root. Fails if the element is not found.

Compilation flags:
static
Template:
find(UnionFind,Element,Root,Rank,UnionFindOut)
Mode and number of proofs:
find(+union_find,+element,?element,?rank,?union_find) - zero_or_one
Remarks:

  • Path compression: The structure of the tree containing the element is flattened by making every node point to the root whenever this predicate is used on it.

disjoint_sets/2

Returns the list of disjoint sets in the given union-find data structure.

Compilation flags:
static
Template:
disjoint_sets(UnionFind,Sets)
Mode and number of proofs:
disjoint_sets(+union_find,?sets) - zero_or_one

Protected predicates

(none)

Private predicates

(none)

Operators

(none)

See also

union_find