1/*
2unionfind_opt.pl: Union find (optimised)
3(C) Thom.Fruehwirth at uni-ulm.de, 2005/01/25
4(C) Tom.Schrijvers at cs.kuleuven.be, 2005/01/25
5This program is distributed under the terms of the GNU General Public License:
7
8%% DESCRIPTION
9Optimised union-find implementation.#
10A new set can be created, sets can be united, and the representative for a set
11can be searched.
12
13%% HOW TO USE
14The following operations are supported:                                     #
15  *make(A)*:    create a new set with single element A                      #
16  *find(A,B)*:  B is representative of the set containing A                 #
17  *union(A,B)*: join the two sets containing A and B                        #
18  *link(A,B)*:  join the two sets represented by A and B (internal)
19
20Data is represented as:                                                     #
21  *root(A,N)*:  A is the representative of a set (root of tree with depth N)#
22  *A ~> B*:     A and B are in the same set (edge indirectly pointing to root)
23
25T Schrijvers, T Fruehwirth. Optimal union-find in Constraint Handling Rules.
26Theory and Practice of Logic Programming, 2006.
27
28%% SAMPLE QUERIES
29Q: make(a), make(b), make(c), make(d), make(e), union(a,b), union(c,d),
30    union(e,c).
31A: root(a,1), root(c,1), b~>a, d~>c, e~>c.
32
33Q: make(a), make(b), make(c), make(d), make(e), union(a,b), union(c,d),
34    union(e,c), find(b,X), find(d,Y).
35A: X=a, Y=c, root(a,1), root(c,1), b~>a, d~>c, e~>c.
36*/
37
38:- module(unionfind, [make/1,union/2,find/2]).   39:- use_module(library(chr)).   40
41:- op(700, xfx, '~>').   42
43:- chr_constraint
44    make(+element),
45    find(?element,?element),
46    union(+element,+element),
47    (?element) ~> (+element),
49    root(+element,?natural).
50
51%:- chr_type element == dense_int.          % efficient: arrays
52:- chr_type element == int.                % less efficient: hashtables
53
54
55make     @ make(A) <=> root(A,0).
56
57union    @ union(A,B) <=> find(A,X), find(B,Y), link(X,Y).
58
59findNode @ A ~> B, find(A,X) <=> find(B,X), A ~> X.
60findRoot @ root(B,_) \ find(B,X) <=> X=B.
61