merge - Implementing Disjoint Set System In Python -

what have far largely based off page 571 of "introduction algorithms" cormen et al.

i have node class in python represents set:

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

this implementation going use list of nodes forest (i open better ways store sets).

initialize() returns list of nodes, store in variable set , pass other functions.

find searches through forest value , returns set appears in. chose use for s in range(len(set)): in recursion shrink list of sets being passed in set[s:].

def find(set, value):     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 forest finding them , promoting 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 getting errors when finds , merges, namely find not returning proper set, , not sure if merge working well. appreciate make sure functions implemented properly.

i don't have latest edition of book, doesn't quite disjoint-set forest.

i think mistake think forest has stored in collection , have traverse collection operations on nodes. remove set merge() , find() , implement find() as

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

just in book. add makeset() returns single correctly initialized node, , maybe sameset() function too:

def sameset(n1, n2):     return find(n1) == find(n2) 

you have working disjoint set implementation.