The goal of this challenge is to compute the set of equivalence classes over the transitive closure of a symmetric, reflexive relation. For those who don't know what that means, here is a brief introduction into the relevant terms:
A relation ◊ is symmetric if a ◊ b ↔ b ◊ a. It is reflexive if each object is related to itself, i.e. a ◊ a always holds. It is transitive if a ◊ b ∧ b ◊ c → a ◊ c, i.e. if a is related to b and b is related to c, then a is related to c. An equivalence relation is a relation that is symmetric, reflexive and transitive.
The transitive closure ◊* of ◊ is a transitive relation such that a ◊* b holds if and only if there is a (possibly empty) series of objects c1, c2, ..., cn such that a ◊ c1 ◊ c2 ◊ ··· ◊ cn ◊ b. The transitive closure of a symmetric, reflexive relation is an equivalence relation.
Let ≡ be an equivalence relation over the set S. An equivalence class a≡ of an object a over the relation ≡ is the largest subset of S such that a ≡ x for all x ∈ S or formally: a≡ = { x | x ∈ S, a ≡ x }. All elements of a≡ are equivalent to one another.
The set of equivalence classes S/≡ of ≡ over S is the set of equivalence classes of all members of S.
Constraints
In this task, your objective is to write a function that takes a binary relation ≅ and a finite non-empty set S. You may take input in a suitable way and choose a suitable data-structure for S (e.g. an array or a linked list). Assume that ≅ is a symmetric, reflexive relation over S. Your function should return or print out the set of equivalence classes over S of the transitiveclosure of ≅. You may choose a suitable output format or data structure for the result. As the result is a set, each object in S may appear only once.
You may not use library routines or other builtin functionality to find the components of a graph or related things.
Winning condition
The shortest answer in octets wins. The most elegant answer is chosen in case of a tie.
Sample input
The reflexive and symmetric members of ≅ have been omitted for brevity.
S1 = {A, B, C, D, E, F, G, H}
≅1 = {(A, B), (B, C), (B, E), (D, G) (E, H)}
S1/≅1* = {{A, B, C, E, H}, {D, G}, {F}}.
S2 = {α, β, γ, δ, ε, ζ, η, θ, ι, κ}
≅2 = {(α, ζ), (α, ι), (β, γ), (β, ε), (γ, δ), (γ, ε), (ζ, θ), (η, κ), (θ, ι)}
S2/≅2* = {{α, ζ, θ, ι}, {β, γ, δ, ε}, {η, κ}}
S3 = {♠, ♣, ♥, ♦}
≅3 = {}
S3/≅3* = {{♠}, {♣}, {♥}, {♦}}
S4 = {Α, Β, Γ, Δ, Ε, Ζ, Η, Θ, Ι, Κ, Λ}
≅4 = {(Α, Ε), (Β, Ζ), (Γ, Η), (Δ, Θ), (Ε, Ι), (Ζ, Κ), (Η, Λ), (Θ, Α), (Ι, Β), (Κ, Γ), (Λ, Δ)}
S4/≅4* = {{Α, Β, Γ, Δ, Ε, Ζ, Η, Θ, Ι, Κ, Λ}}