Subject Infrastructure Repository 


Disjoint SetA disjointset is a data structure for maintaining dynamic partitions of a set. I. Language Agnostic Overview A partition of some set X is a collection of nonempty subsets whose union is X, but any two of the subsets are disjoint. For example, let X = {1,2,3,4,5}. Then, {{1,3,5},{2,4}} is a partition of X. The source code for the disjointset class is taken from the book “Data Structure and Algorithm Analysis in Java” by Mark Allen Weiss, first edition, 1998. There are two operations that must be supported by a disjoint set implementation:
Any disjointset implementation must satisfy the following properties:
The find operation takes a tree node as input and returns the root of the tree which contains the node. It does this by following the parent pointers until a root node is reached. Thus, the time complexity of the find operation is proportional to the maximum height of the trees in the forest, and the complexity is linear when the forest degenerates into a list. Conversely, the union operation takes the roots of two trees and merges them into one tree. The time complexity of the union operation is constant since the operation simply sets one root's parent pointer to be the other input root node. Further, an optimized unionfind algorithm incorporates two improvements over the original algorithm described above:
II. Java Specific Overview The disjoint set tree is implemented on top of an integer array, which makes the forest have the following properties:
There are two implementations of the disjointset class included, one optimized and one unoptimized. They are both subject to the same invariants, however, and so only the invariants and dependent methods are discussed here. The disjointset invariant has three requirements:
The pre and postconditions for the Find operation, Find(int x), are:
The pre and postconditions for the Union operation, union(int root1,int root2), are:
Metrics: Original: Lines of code for implementation: 35 Methods for implementation: 5 Lines of code for invariants: 39 Methods for invariants: 3 Fast: Lines of code for implementation: 38 Methods for implementation: 4 Lines of code for invariants: 39 Methods for invariants: 3 References: Wikipedia's entry on disjoint sets: http://en.wikipedia.org/wiki/Disjointset_data_structure Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGrawHill, 2001. ISBN 0262032937. Chapter 21: Data Structures for Disjoint Sets, pp.498524
Try the following link to upgrade the page display. (Explanation) 