"""Disjoint-Set Some applications involve grouping n distinct objects into a collection of disjoint sets. Two important operations are then finding which set a given object belongs to and uniting the two sets. This module implements Disjoint-Set Forests. """ ###################################################################### class DisjointSetNode: def __init__(self, value): self.value = value self.parent = self self.rank = 0 # No need make_set as that is done by the DisjointSetNode's # constructor. # def make_set(x): # x.parent = x # x.rank = 0 def find_set(x): if x != x.parent: x.parent = find_set(x.parent) return x.parent def union(x, y): link(find_set(x), find_set(y)) def link(x, y): if x.rank > y.rank: y.parent = x else: x.parent = y if x.rank == y.rank: y.rank = y.rank + 1 ###################################################################### def test(): small = "abcdef" big = "ABCDEF" small_list = test_build_list(small) big_list = test_build_list(big) test_union(small_list) test_union(big_list) print "Small Letters" test_print_parents(small_list) print print "Big Letters" test_print_parents(big_list) union(small_list[0], big_list[0]) print print "Unioned Letters" test_print_parents(small_list) test_print_parents(big_list) def test_build_list(values): result = [] for v in values: result.append(DisjointSetNode(v)) return result def test_union(nodes): N = len(nodes) n = N / 2 for i in xrange(n-1): union(nodes[i+1], nodes[i]) for i in xrange(n, N-1): union(nodes[i], nodes[i+1]) union(nodes[0], nodes[N-1]) def test_print_parents(list_of_nodes): for x in list_of_nodes: original_parent = x.parent.value set_parent = find_set(x) after_parent = x.parent.value print "Value:", x.value, print "OriginalParent:", original_parent, print "ParentAfterPathComparession:", after_parent if __name__ == '__main__': test()