Implementing an unrelated dialing system in Python

Question

What I still have is largely based on p. 571, An Introduction to Algorithms, by Cormen et al.

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

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

This implementation will use List nodes as a forest (I am open to better ways to store sets).

Initialize() returns a list of nodes that I will store in the set variable, and go to other functions.

Find searches the forest for the value and returns the set in which it appears. I decided to use for s in range(len(set)): so that in recursion I could compress the list of sets passed to 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 brings together sets in the forest, discovering them and contributing to a higher level 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 get some errors when I do Find and Merge s, namely Find does not return the correct set, and therefore I'm not sure that Merge working fine. I would appreciate some help to make sure that the functions performed correctly.

Answer 1

I do not have the latest version of the book, but it does not look like a forest with a disjoint set.

I think your mistake is to think that the forest should be stored in the collection and that you need to go through this collection to perform operations on nodes. Remove set from Merge() and Find() and implement Find() as

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

just like in the book. Then add MakeSet() , which returns one properly initialized node function and possibly << 26>:

 def SameSet(n1, n2): return Find(n1) == Find(n2) 

Now you have a working implementation of disjoint sets.

Answer 2

Have you looked at other existing implementations ?

Answer 3

Assuming each node is initialized as its own parent:

 def Find(node): while node is not node.parent: node = node.parent return node 

Answer 4

Using this implementation as a starting point, I created a new python class to handle disjoint sets, which also supports persistence using MongoDb.

In my class, you should be able, for example:

• Create an instance of UnionFind() , which uses python built-in dictionaries by default, and later resolve consolidate() your results in the MongoDb collection
• Create an instance of UnionFind from the MongoDb collection and use it directly.

You might want to check out the code on github .

Cheers, Simone