Implementing Disjoint Set System In Python

Question

What I have so far is largely based off page 571 of "Introduction To Algorithms" by Cormen et al.

I have a Node class in python that represents a set:

class Node:
    def __init__(self, parent, rank = 0):
        self.parent = parent
        self.rank = rank

This implementation is going to use a List of Nodes as the forest (I am open to better ways to store the sets).

Initialize() returns a list of Nodes, that I will store in variable set and pass into the other functions.

Find searches through the forest for the value and returns the set that it appears in. I chose to use for s in range(len(set)): so that in the recursion I could shrink the list of sets being passed in by set[s:].

def Find(set, value):
    for s in range(len(set)):
        if value != set[s].parent:
            set[s].parent = Find(set[s:], set[s].parent)
        return set[s]

Merge merges sets in the forest by finding them and promoting the higher ranked set.

def Merge(set, value1, value2):
    set_val_1 = Find(set, value1)
    set_val_2 = Find(set, value2)
    if set_val_1.rank > set_val_2.rank:
        set_val_2.parent = set_val_1
    else:
        set_val_1.parent = set_val_2
        if set_val_1.rank == set_val_2.rank:
            set_val_2.rank += 1

I am getting some errors when I do Finds and Merges, namely Find is not returning the proper set, and so I am not sure if Merge is working properly as well. I would appreciate some help to make sure the functions are implemented properly.

Answer 1

Have you looked at any other existing implementations?