Did you know ... Search Documentation:

# Package "union_find"

Title: A union-find algorithm implementation for SWI-Prolog Not rated. Create the first rating! 1.0.0 e11f8e5f67196a5856ebad516fa9051a628bd654 Jose Antonio Riaza Valverde Jose Antonio Riaza Valverde Jose Antonio Riaza Valverde https://github.com/jariazavalverde/prolog-union-find https://github.com/jariazavalverde/prolog-union-find

## Reviews

No reviews. Create the first review!.

# Union-find data structure in Prolog

## A union-find algorithm implementation for SWI-Prolog

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.

## Installation (SWI-Prolog)

`?- pack_install(union_find).`

## Usage

### Union-find with indices

`:- 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.

#### Creating union-find structures

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

#### Modifying union-find structures

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

#### Querying union-find structures

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

### Union-find with association lists

`:- 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.

#### Creating union-find structures (assoc)

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

#### Modifying union-find structures (assoc)

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

#### Querying union-find structures (assoc)

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

## Example

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)]).```