# UnionFind data structure implemented in Python

This class is used to create sets out of nodes to from a graph-like structure (or grouping since I remove most of the normal graph structure and all child nodes have the same parent).

Is there anything I can do to improve the design of this class? Is the use of static methods here appropriate?

class UnionFind(object):
'''
Used to initialize the set and then holds the required functions
to operate on them
'''

def __init__(self, vertex):
self.rank = 0
self.parent = self
self.vertex = vertex

@staticmethod
def find(x):
if x != x.parent:
x.parent = UnionFind.find(x.parent)
return x

@staticmethod
def union(x,y):
xroot = UnionFind.find(x)
yroot = UnionFind.find(y)

if xroot == yroot:
return
if xroot.rank > yroot.rank:
yroot.parent = xroot
else:
xroot.parent = yroot
if xroot.rank == yroot.rank:
yroot.rank += 1


• find is not a right name. A method find(x) is expected to find objects matching x. find_root seems more appropriate.

I know that Sedgewick & Wayne use find, and they are wrong.

• find (or find_root) has no reason to be static. x.find_root() is way more natural than UnionFind.find_root(x).

• Python does not eliminate tail recursion. I recommend to rewrite find as

def find(x):
while x != x.parent:
x = x.parent
return x

• As you suggested dropping the @staticmethod decorator, you could write self instead of x. – Mathias Ettinger Sep 22 '16 at 8:10
• @MathiasEttinger Thanks for the suggestion. It is a lot more natural to not have to call find with an argument – MattTheSnake Sep 22 '16 at 16:04
• @vnp Thanks! The rewrite of find is much better. – MattTheSnake Sep 22 '16 at 16:05