Disjoint Sets
April 2, 2010
We make our data type abstract. Make-disjoint-set
creates a procedure that responds to three messages: 'make-set
adds a new element to the forest, 'find
finds the partition to which a particular element belongs, and 'union
merges two partitions:
(define (make-disjoint-set hash eql? oops size)
(let ((forest (make-hash hash eql? oops size)))
(define (make-set item) ; car is parent, cdr is rank
(forest 'insert item (cons item 0)))
(define (find item)
(let ((parent (car (forest 'lookup item))))
(if (eql? item parent) item
(let ((x (forest 'lookup (find parent))))
(forest 'insert item x)
(car x)))))
(define (union item1 item2)
(let* ((root1 (find item1)) (root2 (find item2))
(rank1 (cdr (forest 'lookup root1)))
(rank2 (cdr (forest 'lookup root2))))
(cond ((< rank1 rank2)
(forest 'insert root1 (cons root2 rank1)))
((< rank2 rank1)
(forest 'insert root2 (cons root1 rank2)))
((not (eql? root1 root2))
(forest 'insert root2 (cons root1 rank2))
(forest 'insert root1 (cons root1 (+ rank1 1)))))))
(lambda (message . args)
(case message
((enlist) (forest 'enlist))
((make-set) (apply make-set args))
((find) (apply find args))
((union) (apply union args))))))
Make-set
stores each element in a hash table with the element itself as the key; the associated value is a pair with the parent in the car and the rank in the cdr. Find
implements path compression by first finding the root, then modifying the hash table to store the root in the element’s node before returning the root. Union
implements the rank heuristic by implementing the rank only when the ranks of the roots of the two partitions being merged are the same. We also implemented an 'enlist
message that is useful during debugging.
Here are some examples:
> (define djs (make-disjoint-set string-hash string=? #f 19))
> (djs 'make-set "A")
> (djs 'make-set "B")
> (djs 'enlist)
(("B" "B" . 0) ("A" "A" . 0))
> (djs 'union "A" "B")
> (djs 'enlist)
(("B" "A" . 0) ("A" "A" . 1))
> (djs 'find "A")
"A"
> (djs 'find "B")
"A"
We used hash tables from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/STcpI9Cu.
I just created a class based on the python dict. I included path compression, but not the rank heuristics.
[…] studied disjoint sets in the previous exercise. In today’s exercise we use disjoint sets to implement Kruskal’s algorithm to find the minimum […]
this method would help……
int detectAndRemoveLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
removeLoop(slow_p, list);
/* Return 1 to indicate that loop is found */
return 1;
}
}