1
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$
  • 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
    
\$\endgroup\$
  • 1
    \$\begingroup\$ As you suggested dropping the @staticmethod decorator, you could write self instead of x. \$\endgroup\$ – Mathias Ettinger Sep 22 '16 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\$ – MattTheSnake Sep 22 '16 at 16:04
  • \$\begingroup\$ @vnp Thanks! The rewrite of find is much better. \$\endgroup\$ – MattTheSnake Sep 22 '16 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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