1/** 2 * 3 * FILENAME: union_find.pl 4 * DESCRIPTION: This module contains predicates for manipulating union-find structures with indices. 5 * AUTHORS: JosÃ© Antonio Riaza Valverde <riaza.valverde@gmail.com> 6 * GITHUB: https://github.com/jariazavalverde/prolog-union-find 7 * UPDATED: 04.12.2019 8 * 9 **/ 10 11 12 13:- module(union_find, [ 14 union_find/2, 15 make_set/2, 16 union/3, 17 union_all/2, 18 find/3, 19 find/4, 20 disjoint_sets/2, 21]). 22 23 24 25% union_find/2 26% union_find(?UnionFind, +Size) 27% 28% This predicate initializes a new ?UnionFind structure of size +Size. A union-find structure consists of a 29% term union_find/(+Size) with a number of elements each of which stores a parent pointer and a rank value. 30% union_find/2 takes O(n) time. 31union_find(UF, N) :- 32 union_find(1, N, Args), 33 UF =.. [union_find|Args]. 34 35% union_find/3 36% union_find(+LastID, +Size, ?UnionFind) 37% 38% NOT EXPORTED 39union_find(_, 0, []). 40union_find(I, N, [I-0|UF]) :- 41 succ(M, N), 42 succ(I, J), 43 union_find(J, M, UF). 44 45% make_set/2 46% make_set(+UnionFindIn, ?UnionFindOut) 47% 48% This predicate makes a new set in +UnionFindIn by creating a new element with a unique id, a rank of 0, and a parent 49% pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set. 50% make_set/2 takes O(n) time. 51make_set(UF0, UF1) :- 52 functor(UF0, union_find, N), 53 succ(N, M), 54 UF0 =.. [union_find|Args0], 55 append(Args0, [M-0], Args1), 56 UF1 =.. [union_find|Args1]. 57 58% union/3 59% union(+UnionFind, +Element1, +Element2) 60% 61% This predicate uses find/4 to determine the roots of the trees +Element1 and +Element2 belong to. 62% If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. 63% This predicate succeeds attaching the shorter tree (by rank) to the root of the taller tree in +UnionFind. 64% This predicate performs destructive assignments into +UnionFind. 65union(UF, I, J) :- 66 find(UF, I, X, RankI), 67 find(UF, J, Y, RankJ), 68 (X \== Y -> 69 (RankI < RankJ -> setarg(X, UF, Y-RankI) ; 70 (RankI > RankJ -> setarg(Y, UF, X-RankJ) ; 71 setarg(Y, UF, X-RankJ), 72 succ(RankI, SrankI), 73 setarg(X, UF, X-SrankI))) ; true). 74 75% union_all/2 76% union_all(+UnionFind, +Elements) 77% 78% This predicate succeeds joining all the elements +Elements in the union-find structure +UnionFind. 79% This predicate performs destructive assignments into +UnionFind. 80union_all(_, []). 81union_all(_, [_]). 82union_all(UF, [X,Y|Xs]) :- 83 union(UF, X, Y), 84 union_all(UF, [Y|Xs]). 85 86% find/3 87% find(+UnionFind, ?Element, ?Root) 88% 89% This predicate follows the chain of parent pointers from ?Element up the tree until it reaches a ?Root element, 90% whose parent is itself. ?Root is the representative member of the set to which ?Element belongs, and may be 91% ?Element itself. Path compression flattens the structure of the tree by making every node point to the root 92% whenever find/3 is used on it. 93% This predicate performs destructive assignments into +UnionFind. 94find(UF, I, X) :- 95 arg(I, UF, J-R), 96 (I == J -> X = J ; find(UF, J, X), setarg(I, UF, X-R)). 97 98% find/4 99% find(+UnionFind, ?Element, ?Root, ?Rank) 100% 101% Same as find/3, but returning also the ?Rank of the ?Root. 102% This predicate performs destructive assignments into +UnionFind. 103find(UF, I, X, S) :- 104 arg(I, UF, J-R), 105 (I == J -> X = J, S = R ; find(UF, J, X, S), setarg(I, UF, X-R)). 106 107% disjoint_sets/2 108% disjoint_sets(+UnionFind, ?Sets). 109% 110% This predicate succeeds when ?Sets is the list of disjoint sets on the +UnionFind structure. 111% This predicate performs destructive assignments into +UnionFind. 112disjoint_sets(UF, Sets) :- 113 findall(Set, bagof(I, find(UF, I, _), Set), Sets)