Unoptimized Union-Find algorithm in Ruby.

ufind.rb

class UnionFind
  def initialize(universe)
    @data = {}
    universe.each do |element|
      @data[element] = element
    end
  end

  def find(n)
    root = n
    while @data[root] != root do
      root = @data[root]
    end
    root
  end

  def union(a,b)
    rootA, rootB = find(a), find(b)
    return if rootA == rootB
    @data[rootA] = @data[rootB]
  end

  def equiv?(a,b)
    find(a) == find(b)
  end
end

describe UnionFind do
  describe "#find" do
    before(:each) do
      @eq = UnionFind.new('a'..'z')
    end

    it "sends elements to itself when fresh" do
      expect(@eq.find('a')).to eq('a')
    end

    it "sends elements in the same set to one of those elements" do
      @eq.union('a', 'e')
      expect(@eq.find('a')).to eq('e')
    end

    it "sends elements in the same set to one of those elements, multiple" do
      @eq.union('a', 'e')
      @eq.union('i', 'o')
      @eq.union('i', 'a')
      expect(@eq.find('a')).to eq('e')
    end

    it "checks whether values are in the same equivilence class" do
      # use some soundex classes
      @eq.union('a', 'e')
      @eq.union('i', 'o')
      @eq.union('u', 'y')
      @eq.union('h', 'w')
      @eq.union('a', 'i')
      @eq.union('u', 'h')
      @eq.union('a', 'u')

      @eq.union('b', 'f')
      @eq.union('p', 'v')
      @eq.union('b', 'p')

      expect(@eq.equiv?('o', 'h')).to be
      expect(@eq.equiv?('f', 'p')).to be
      expect(@eq.equiv?('h', 'v')).not_to be
    end
  end
end

Union-find computes represents the quotient set.