Equivalence classes on the Transitive Closure of a Reflexive Relation

Question

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 c₁, c₂, ..., c_n such that a ◊ c₁ ◊ c₂ ◊ ··· ◊ c_n ◊ 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.

S₁ = {A, B, C, D, E, F, G, H}
≅₁ = {(A, B), (B, C), (B, E), (D, G) (E, H)}
S₁/≅₁* = {{A, B, C, E, H}, {D, G}, {F}}.

S₂ = {α, β, γ, δ, ε, ζ, η, θ, ι, κ}
≅₂ = {(α, ζ), (α, ι), (β, γ), (β, ε), (γ, δ), (γ, ε), (ζ, θ), (η, κ), (θ, ι)}
S₂/≅₂* = {{α, ζ, θ, ι}, {β, γ, δ, ε}, {η, κ}}

S₃ = {♠, ♣, ♥, ♦}
≅₃ = {}
S₃/≅₃* = {{♠}, {♣}, {♥}, {♦}}

S₄ = {Α, Β, Γ, Δ, Ε, Ζ, Η, Θ, Ι, Κ, Λ}
≅₄ = {(Α, Ε), (Β, Ζ), (Γ, Η), (Δ, Θ), (Ε, Ι), (Ζ, Κ), (Η, Λ), (Θ, Α), (Ι, Β), (Κ, Γ), (Λ, Δ)}
S₄/≅₄* = {{Α, Β, Γ, Δ, Ε, Ζ, Η, Θ, Ι, Κ, Λ}}

Answer 1

Pyth, 50 29 bytes

JchQ1FNeQAmf/@JTd0N XGJ.(JH;J

Input is expected to be a list of two elements where the first element is a list of all the objects in S, and the second element is a list of all the members in ≅, represented as lists. So for the first example, the input is

[["A", "B", "C", "D", "E", "F", "G", "H"], [["A", "B"], ["B", "C"], ["B", "E"], ["D", "G"], ["E", "H"]]]

Explanation:

                               Implicit assignment of Q to input, so head(Q) is S and end(Q) is ≅
JchQ1                          Assign J to chop(head(Q),1) e.g. [1,2,3] => [[1],[2],[3]]
     FNeQ                      For N in end(Q)
         A                       Assign [H,G] to following list
          m       N                Map following function over N
           f     0                   Return first T where following function of T starting at 0,1,2... is truthy         
            /@JTd                      lambda d: true if d is J[T]
                    XGJ.(JH;     Append J[H] to J[G] and pop J[H]
                            J  Print J

Note that if transitive or reflexive members (i.e. redundant) members of ≅ are included, my code should output junk.

You can try it out here.