Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Applications

One of the most important applications of partitions involves the processing of equivalence relations. Equivalence relations arise in many interesting contexts. For example, two nodes in an electric circuit are electrically equivalent if there is a conducting path (a wire) connecting the two nodes. In effect, the wires establish an electrical equivalence relation over the nodes of a circuit.

A similar relation arises among the classes in a Java program. Consider the following Java code fragment:

interface I {}
class A implements I {}
class B implements I {}
class C extends A {}
class D extends B {}

The three classes A, B, C and D are equivalent in the sense that they all implement the same interface I. In effect, the class declarations establish an equivalence relation over the classes in a Java program.

Definition (Equivalence Relation) An equivalence relation over a universal set U is a relation with the following properties:
The relation is reflexive . That is, for every , .
The relation is symmetric . That is, for every pair and , if then .
The relation is transitive . That is, for every triple , and , if and then .

An important characteristic of an equivalence relation is that it partitions the elements of the universal set U into a set of equivalence classes . That is, U is partitioned into , such that for every pair and , if and only if x and y are in the same element of the partition. That is, if there exists a value of i such that .

For example, consider the universe . and the equivalence relation defined over U defines as follows:

This relation results in the following partition of U:

The list of equivalences in Equation contains many redundancies. Since we know that the relation is reflexive, symmetric and transitive, it is possible to infer the complete relation from the following list

The problem of finding the set of equivalence classes from a list of equivalence pairs is easily solved using a partition. Program shows how it can be done using the PartitionAsForest class defined in Section .

program29343
Program: Application of disjoint sets--finding equivalence classes.

The algorithm first gets a positive integer n from the input and creates a partition, p, of the universe (lines 7-12). As explained in Section , the initial partition comprises n disjoint sets of size one. That is, each element of the universal set is in a separate element of the partition.

Each iteration of the main loop processes one equivalence pair (lines 18-23). An equivalence pair consists of two numbers, i and j, such that and . The find operation is used to determine the sets s and t in partition p that contain elements i and j, respectively (lines 24-25).

If s and t are not the same set, then the disjoint sets are united using the join operation (lines 26-27). Otherwise, i and j are already in the same set and the equivalence pair is redundant (line 29). After all the pairs have been processed, the final partition is printed (line 31).