DisjointSet() function

Question

I've got code that's an implementation of Kruskal's alghorithm and I really would like to know what exactly this DisjointSet() function is doing. I can not find this, so maybe someone can explain it to me?

from utils.disjointset import DisjointSet
from model.undirectededge import UndirectedEdge

class Kruskal(object):
    @staticmethod
    def execute(graph):
        mst =set()
        disjointset = DisjointSet()
        for node in graph.iternodes ():
            disjointset.create(node)
        sorted_edges=sorted(graph.iteredges(),key=lambda edge:edge.weight)
        for edge in sorted_edges :
            if disjointset.find(edge.source)!=disjointset.find(edge.target):
                mst.add( UndirectedEdge(edge.source,edge.target,edge.weight))
            disjointset.union(edge.source,edge.target)
        return mst

Answer 1

The concept of disjoint set is explained on Wikipedia:

... is a data structure that stores a collection of disjoint (non-overlapping) sets.

...Disjoint-set data structures play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

In that article you can also find pseudo code for its two principle functions: find and union.

There are several implementation choices one can make, and without seeing the source of your DisjointSet it is not possible to tell which flavour it uses (rank-based, size-based, path splitting, path halving, ...).

You can find some Q&A on the subject on this site:

• Disjoint set implementation in Python
• Implementing Disjoint Set System In Python
• Disjoint-Set forests in Python alternate implementation

For the code you have presented, I believe the following implementation of DisjointSet should work:

class DisjointSet:
    class Element:
        def __init__(self, key):
            self.parent = self
            self.rank = 0

    def __init__(self):
        self.elements = {}

    def create(self, key):
        if key not in self.elements:
            self.elements[key] = self.Element(key)

    def find(self, key):
        el = self.elements[key]
        # Path splitting algorithm
        while el.parent != el:
            el, el.parent = el.parent, el.parent.parent
        return el

    def union(self, a, b):
        x = self.find(a)
        y = self.find(b)
        if x != y:
            # Union by rank
            if x.rank < y.rank:
                x, y = y, x
            y.parent = x
            if x.rank == y.rank:
                x.rank += 1