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

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

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

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

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
  • 1
    \$\begingroup\$ As you suggested dropping the @staticmethod decorator, you could write self instead of x. \$\endgroup\$ Sep 22, 2016 at 8:10
  • \$\begingroup\$ @MathiasEttinger Thanks for the suggestion. It is a lot more natural to not have to call find with an argument \$\endgroup\$ Sep 22, 2016 at 16:04
  • \$\begingroup\$ @vnp Thanks! The rewrite of find is much better. \$\endgroup\$ Sep 22, 2016 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.