Welcome, guest | Sign In | My Account | Store | Cart
"""
MakeSet(x) initializes disjoint set for object x
Find(x) returns representative object of the set containing x
Union(x,y) makes two sets containing x and y respectively into one set

Some Applications:
- Kruskal's algorithm for finding minimal spanning trees
- Finding connected components in graphs
- Finding connected components in images (binary)
"""


def MakeSet(x):
     x
.parent = x
     x
.rank   = 0

def Union(x, y):
     xRoot
= Find(x)
     yRoot
= Find(y)
     
if xRoot.rank > yRoot.rank:
         yRoot
.parent = xRoot
     
elif xRoot.rank < yRoot.rank:
         xRoot
.parent = yRoot
     
elif xRoot != yRoot: # Unless x and y are already in same set, merge them
         yRoot
.parent = xRoot
         xRoot
.rank = xRoot.rank + 1

def Find(x):
     
if x.parent == x:
       
return x
     
else:
        x
.parent = Find(x.parent)
       
return x.parent

""""""""""""""""""""""""""""""""""""""""""
# sample code using Union-Find (not needed)

import itertools

class Node:
   
def __init__ (self, label):
       
self.label = label
   
def __str__(self):
       
return self.label
   
l
= [Node(ch) for ch in "abcdefg"]      #list of seven objects with distinct labels
print ""
print "objects labels:\t\t\t", [str(i) for i in l]

[MakeSet(node) for node in l]       #starting with every object in its own set

sets
=  [str(Find(x)) for x in l]
print "set representatives:\t\t", sets
print "number of disjoint sets:\t", len([i for i in itertools.groupby(sets)])

assert( Find(l[0]) != Find(l[2]) )
Union(l[0],l[2])        #joining first and third
assert( Find(l[0]) == Find(l[2]) )

assert( Find(l[0]) != Find(l[1]) )
assert( Find(l[2]) != Find(l[1]) )
Union(l[0],l[1])        #joining first and second
assert( Find(l[0]) == Find(l[1]) )
assert( Find(l[2]) == Find(l[1]) )

Union(l[-2],l[-1])        #joining last two sets
Union(l[-3],l[-1])        #joining last two sets

sets
= [str(Find(x)) for x in l]
print "set representatives:\t\t", sets
print "number of disjoint sets:\t", len([i for i in itertools.groupby(sets)])

for o in l:
   
del o.parent

History