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.
class DisjointSet(dict): def add(self, item): self[item] = item def find(self, item): parent = self[item] while self[parent] != parent: parent = self[parent] self[item] = parent return parent def union(self, item1, item2): self[item2] = self[item1][…] 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;
}
}