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)