Did you know ... | Search Documentation: |
Packs (add-ons) for SWI-Prolog |
Title: | A union-find algorithm implementation for SWI-Prolog |
---|---|
Rating: | Not rated. Create the first rating! |
Latest version: | 1.0.0 |
SHA1 sum: | e11f8e5f67196a5856ebad516fa9051a628bd654 |
Author: | Jose Antonio Riaza Valverde <riaza.valverde@gmail.com> |
Maintainer: | Jose Antonio Riaza Valverde <riaza.valverde@gmail.com> |
Packager: | Jose Antonio Riaza Valverde <riaza.valverde@gmail.com> |
Home page: | https://github.com/jariazavalverde/prolog-union-find |
Download URL: | https://github.com/jariazavalverde/prolog-union-find |
No reviews. Create the first review!.
Version | SHA1 | #Downloads | URL |
---|---|---|---|
1.0.0 | e11f8e5f67196a5856ebad516fa9051a628bd654 | 38 | http://jariaza.es/swipl/union_find/union_find-1.0.0.tgz |
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:
?- 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.
n
elements.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(?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.
Pack contains 5 files holding a total of 18.3K bytes.