Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

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 user-defined data types in a C++ program. Consider the following C++ code fragment:

class A;
typedef A B;
typedef A C;
typedef B D;
The four data types A, B, C and D are equivalent in the sense that values of one type can be assigned directly to variables of another (without requiring a type conversion). In effect, the typedef declarations establish a type equivalence relation over the user-defined data types in a C++ program.

Definition (Equivalence Relation)  An equivalence relation   over a universal set U is a relation tex2html_wrap_inline67862 with the following properties:
  1. The relation tex2html_wrap_inline67862 is reflexive . I.e., for every tex2html_wrap_inline67866, tex2html_wrap_inline67868.
  2. The relation tex2html_wrap_inline67862 is symmetric . I.e., for every pair tex2html_wrap_inline67866 and tex2html_wrap_inline67874, if tex2html_wrap_inline67876 then tex2html_wrap_inline67878.
  3. The relation tex2html_wrap_inline67862 is transitive . I.e., for every triple tex2html_wrap_inline67866, tex2html_wrap_inline67874 and tex2html_wrap_inline67886, if tex2html_wrap_inline67876 and tex2html_wrap_inline67890 then tex2html_wrap_inline67892.

An important characteristic of an equivalence relation is that it partitions the elements of the universal set U into a set of equivalence classes . I.e., U is partitioned into tex2html_wrap_inline67580, such that for every pair tex2html_wrap_inline67866 and tex2html_wrap_inline67874, tex2html_wrap_inline67876 if and only if x and y are in the same element of the partition. I.e.,

displaymath67854

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

  multline30070

This relation results in the following partition of U:

displaymath67855

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

displaymath67856

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

   program30077
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 tex2html_wrap_inline67920 (lines 3-5). As explained in Section gif, the initial partition comprises n disjoint sets of size one. I.e., 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 9-18). An equivalence pair consists of two numbers, i and j, such that tex2html_wrap_inline67922 and tex2html_wrap_inline67924. The find operation is used to determine the sets s and t in partition p that contain elements i and j, respectively (lines 11-12).

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


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.