1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Commented Mar 6, 2021 at 0:49
  • $\begingroup$ 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." $\endgroup$ Commented Mar 6, 2021 at 2:46
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Mar 6, 2021 at 3:17

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .