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