Did you know ... | Search Documentation: |

Pack union_find -- README.md |

A union-find data structure is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.

This package provides an implementation of the union-find algorithm with the following features:

**Path compression**: Path compression flattens the structure of the tree by making every node point to the root whenever a find predicate is used on it.**Union by rank**: Union predicates always attach the shorter tree to the root of the taller tree. Thus, the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node.

?- pack_install(union_find).

:- use_module(library(union_find)).

This module uses `union_find/n`

terms for the representation of union-find structures, where the `i`

-th argument stores the root and the rank of the element `i`

as a pair `Root-Rank`

. For instance, the term `union_find(1-1, 1-0, 3-0)`

represents a union-find structure with disjoint sets `[1, 2]`

and `[3]`

. The union/3, union_all/2, `find/[3-4]`

and disjoint_sets/2 predicates perform destructive assignments (see setarg/3) that are undone if backtracking brings the state back into a position before the call.

Note that `find/[3-4]`

predicates perform destructive assignments for **path compression**, that flattens the structure of the tree by making every node point to the root whenever `find/[3-4]`

are used on it.

**union_find/2**- initializes a new union-find structure as a term with`n`

elements.**make_set/2**- adds a new element to a union-find structure.**union/3**- merges two sets of a union-find structure.**union_all/2**- merges a list of sets of a union-find structure.**find/3**- finds the root of an element in a union-find structure.**find/4**- finds the root and the rank of an element in a union-find structure.**disjoint_sets/2**- gets a list of disjoint sets of a union-find structure.

union_find(?UnionFind, +Size)

This predicate initializes a new `?UnionFind` structure of size `+Size`

. A union-find structure consists of a term `union_find/(+Size)`

with a number of elements each of which stores a parent pointer and a rank value. union_find/2 takes `O(n)` time.

make_set(+UnionFindIn, ?UnionFindOut)

This predicate makes a new set in `+UnionFindIn`

by creating a new element with a unique id, 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. make_set/2 takes `O(n)` time.

union(+UnionFind, +Element1, +Element2)

This predicate uses find/4 to determine the roots of the trees `+Element1`

and `+Element2`

belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. This predicate succeeds attaching the shorter tree (by rank) to the root of the taller tree in `+UnionFind`

. **This predicate performs destructive assignments into +UnionFind.**

union_all(+UnionFind, +Elements)

This predicate succeeds joining all the elements `+Elements`

in the union-find structure `+UnionFind`

. **This predicate performs destructive assignments into +UnionFind.**

find(+UnionFind, ?Element, ?Root)

This predicate follows the chain of parent pointers from `?Element` up the tree until it reaches a `?Root` element, whose parent is itself. `?Root` is the representative member of the set to which `?Element` belongs, and may be `?Element` itself. Path compression flattens the structure of the tree by making every node point to the root whenever `

find/3` is used on it. **This predicate performs destructive assignments into +UnionFind.**

find(+UnionFind, ?Element, ?Root, ?Rank)

Same as find/3, but returning also the `?Rank` of the `?Root`. **This predicate performs destructive assignments into +UnionFind.**

disjoint_sets(+UnionFind, ?Sets).

This predicate succeeds when `?Sets` is the list of disjoint sets on the `+UnionFind`

structure. **This predicate performs destructive assignments into +UnionFind.**

:- use_module(library(union_find_assoc)).

This module uses association lists for the representation of union-find structures, where each value is a pair `Root-Rank`

. For instance, the term `t(b, a-0, -, t(a, a-1, -, t, t), t(c, c-0, -, t, t))`

represents a union-find structure with disjoint sets `[a, b]`

and `[c]`

. The association lists library provides methods for creating, querying and modifying association lists in `O(`log(n)`

)` worst-case time.

Note that `find_assoc/[4-5]`

predicates also produce new union-find structures for **path compression**, that flattens the structure of the tree by making every node point to the root whenever `find_assoc/[4-5]`

are used on it.

**union_find_assoc/2**- initializes a new union-find structure as an association list from a list of terms.**make_set_assoc/3**- adds a new element to a union-find structure.**union_assoc/4**- merges two sets of a union-find structure.**union_all_assoc/3**- merges a list of sets of a union-find structure.**find_assoc/4**- finds the root of an element in a union-find structure.**find_assoc/5**- finds the root and the rank of an element in a union-find structure.**disjoint_sets_assoc/2**- gets a list of disjoint sets of a union-find structure.

union_find_assoc(?UnionFind, +Elements)

This predicate initializes a new `?UnionFind` structure with a list of elements `+Elements`

as keys.

make_set_assoc(+UnionFindIn, +Element, ?UnionFindOut)

This predicate makes a new set by creating a new element with a unique id `+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.

union_assoc(+UnionFindIn, +Element1, +Element2, ?UnionFindOut)

This predicate uses find_assoc/5 to determine the roots of the trees `+Element1`

and `+Element2`

belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. This predicate succeeds attaching the shorter tree (by rank) to the root of the taller tree in `+UnionFindIn`

.

union_all_assoc(+UnionFindIn, +Elements, ?UnionFindOut)

This predicate succeeds joining all the elements of the list `+Elements`

in the union-find structure `+UnionFindIn`

, producing the union-find structure `?UnionFindOut`.

find_assoc(+UnionFindIn, +Element, ?Root, ?UnionFindOut)

This predicate follows the chain of parent pointers from ?Element up the tree until it reaches a ?Root element, whose parent is itself. `?Root` is the representative member of the set to which `+Element`

belongs, and may be
`+Element`

itself. Path compression flattens the structure of the tree by making every node point to the root whenever find_assoc/4 is used on it.

find_assoc(+UnionFindIn, +Element, ?Root, ?Rank, ?UnionFindOut)

Same as find_assoc/4, but returning also the `?Rank` of the `?Root`.

disjoint_sets_assoc(+UnionFind, ?Sets).

This predicate succeeds when `?Sets` is the list of disjoint sets on the `+UnionFind`

structure.

**Kruskal's algorithm** is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

:- use_module(library(union_find_assoc)). kruskal(g(Vertices-Edges), g(Vertices-Tree)) :- union_find_assoc(UF, Vertices), keysort(Edges, Sorted), kruskal(UF, Sorted, Tree). kruskal(_, [], []). kruskal(UF0, [Edge|Edges], [Edge|Tree]) :- Edge = _-(V1, V2), find_assoc(UF0, V1, R1, UF1), find_assoc(UF1, V2, R2, UF2), R1 \== R2, !, union_assoc(UF2, V1, V2, UF3), kruskal(UF3, Edges, Tree). kruskal(UF, [_|Edges], Tree) :- kruskal(UF, Edges, Tree).

?- kruskal(g([a,b,c,d,e,f,g]-[7-(a,b), 5-(a,d), 8-(b,c), 7-(b,e), 9-(b,d), 5-(c,e), 15-(d,e), 6-(d,f), 8-(e,f), 9-(e,g), 11-(f,g)]), Tree). % Tree = g([a,b,c,d,e,f,g]-[5-(a,d),5-(c,e),6-(d,f),7-(a,b),7-(b,e),9-(e,g)]).

Source code is released under the terms of the BSD 3-Clause License.