Representing Equality Theories Via Disjoint Set Union

Although many application domain classes can use simple pointer comparison to determine equality, sometimes multiple objects may be grouped into equivalence classes, so that a more coarse-grained equality theory is needed.

The disjoint set template class EqClass provides, in addition to the constructor, the public operations operator+=() and operator==(), the former to take the union of two equivalence classes, and the latter to determine whether two representatives are in the same equivalence class. The operator+=() method implements set union by rank with path compression, and is nearly constant time; see Ch 22 of [4] for details.


Bill Pippin 2010-01-14