Disjoint-set Forests In Python Alternate Implementation

I'm implementing a disjoint set system in Python, but I've hit a wall. I'm using a tree implementation for the system and am implementing Find(), Merge() and Create() functions for

Solution 1:

The implementation of this data structure becomes simpler when you realize that the operations union and find can also be implemented as methods of a disjoint set forest class, rather than on the individual disjoint sets.

If you can read C++, then have a look at my take on the data structure; it hides the actual sets from the outside world, representing them only as numeric indices in the API. In Python, it would be something like

classDisjSets(object):
    def__init__(self, n):
        self._parent = range(n)
        self._rank = [0] * n

    deffind(self, i):
        if self._parent[i] == i:
            return i
        else:
            self._parent[i] = self.find(self._parent[i])
            return self._parent[i]

    defunion(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self._rank[root_i] < self._rank[root_j]:
                self._parent[root_i] = root_j
            elif self._rank[root_i] > self._rank[root_j]:
                self._parent[root_j] = root_i
            else:
                self._parent[root_i] = root_j
                self._rank[root_j] += 1

(Not tested.)

If you choose not to follow this path, the client of your code will indeed have to have knowledge of Nodes and Find must take a Node argument.

Solution 2:

Clearly merge function should be applied to pair of nodes.

So find function should take single node parameter and look like this:

def find(node):
    if node.parent != node:
        node.parent = find(node.parent)
    return node.parent

Also wikipedia has pseudocode that is easily translatable to python.

Solution 3:

Find is always done on an item. Find(item) is defined as returning the set to which the item belongs. Merger as such must not take nodes, merge always takes two items/sets. Merge or union (item1, item2) must first find(item1) and find(item2) which will return the sets to which each of these belong. After that the smaller set represented by an up-tree must be added to the taller. When a find is issued, always retrace the path and compress it.

A tested implementation with path compression is here.