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.

About these ads

Pages: 1 2

2 Responses to “Disjoint Sets”

  1. Mike said

    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]
    
  2. [...] studied disjoint sets in the previous exercise. In today’s exercise we use disjoint sets to implement Kruskal’s algorithm to find the minimum [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: