Relation: explicitly defined equivalence relation

The Abstract Explicit Partition is defined on a set of points begins with each point forming its own partition (an equivalence class). The programmer is then able to take the union of various partitions forming larger petitions.

Critical Operations for Abstract Explicit Partitions

• Take the union of two partitions
  set_union( Type, Type );
• Return a representative of the partition containing an object
  int find( Type ) const
• Return the number of partitions
  int partitions() const
• Determining if an object is in in a partition of its own
  bool is_singleton( Type ) const

Example Data Structures

The most common data structure for representing explicit partitions is the disjoint set data structure. Most operations occur in O(α(n)) time where α(n) is the inverse of the Ackermann function and it can be said that α(n) < 4 for any humanly computable number and consequently, the operations are O(1) for all intents and purposes.

• Disjoint Set

To view an implementation of the Disjoint Set data structure, see Disjoint Sets.