# combine equal pairs into equivalence classes

Given a set $$S$$ of values, and a set $$P \subset S \times S$$ of pairwise equivalences, what is an algorithm for partitioning $$S$$ into equivalence classes?
$$P$$ is guaranteed to be an equivalence relation.
Assume that $$P$$ "covers" every member of $$S$$.
Efficiency isn't all that crucial: I'm interested in $$\#S < 100000$$ and $$\#P < 10000$$.

This is like building up pairs into clusters, but because this is for exact equality rather than mere similarity, I'm finding that clustering algorithms are red herrings.

• Is $P$ guaranteed to be an equivalence relation (for example, is it transitive)? If so, then one can start with any $s\in S$ and then add anything related to $s$, then anything related to those new things, and so on recursive—that will result in the equivalence class of $s$. Commented Mar 6, 2021 at 0:49
• Yes (edited to clarify). I'm just not sure whether to iterate on $P$ or on $S$ until it's exhausted, or to recurse on a growing set of clusters, or what. Intuitively, "just agglomerate." Commented Mar 6, 2021 at 2:46
• Equivalence classes on the set $S$ are the same as the connected component of the graph whose edges are given by $P$. baeldung.com/cs/graph-connected-components Commented Mar 6, 2021 at 3:17

Equivalence classes on the set $$S$$ are the same as the connected components of the graph whose edges are given by $$P$$. Fortunately, there are standard algorithms for computing the connected components: here is one example.