Skip to content
A union-find algorithm implementation for SWI-Prolog
Prolog
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
prolog
releases
sample
LICENSE
README.md
pack.pl

README.md

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.

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

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's algorithm

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

License

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

You can’t perform that action at this time.