"""
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
