UnionFind data structure implemented in Python

Question

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

Answer 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
  

• 301_Moved_Permanently: As you suggested dropping the @staticmethod decorator, you could write self instead of x.
• MattTheSnake: @MathiasEttinger Thanks for the suggestion. It is a lot more natural to not have to call find with an argument
• MattTheSnake: @vnp Thanks! The rewrite of find is much better.