C - A Data Structure for Disjoint Sets

Summary

This appendix describes a simple yet very efficient Perl solution to a problem known as the disjoint sets problem, the dynamic equivalence relation problem, or the unionfind problem. This problem appears in applications with the following scenario.

1. Each one of a finite set of keys is assigned to exactly one of a number of classes. These classes are the “disjoint sets” or the partitions of an equivalence relation. Often, the set of keys is known in advance, but this is not necessary to use our Perl package.

2. Initially, each key is in a class by itself.

3. As the application progresses, classes are joined together to form larger classes; classes are never divided into smaller classes. (The operation of joining classes together is called union or merge.)

4. At any moment, it must be possible to determine whether two keys are in the same class or in different classes.

To solve this problem, we create a package named UnionFind. Objects of type UnionFind represent an entire collection of keys and classes. The three methods of this package are:

• $uf = UnionFind– > new(), which creates a new collection of disjoint sets, each of which has only one element;

• $uf– > inSameSet($key1,$key2), which returns true if its two arguments are elements of the same disjoint set or false if not;

• $uf– > union($key1,$key2), which combines the sets to which its two arguments belong into a single set.