Disjoint Set Class in Ruby

dr_saturn (Stuart Coyle) — Sun, 10 Feb 2008 02:49:59 GMT

A disjoint Set can be used for creating minimal spanning trees.
The union-find algorithm is fast, faster than linked lists for some uses.
See: Wikipedia Disjoint Set

It's fast and simple. Just add a DisjointSetNode object to the
objects that you want to create a tree of.



# This is a disjoint set implementing union-find

# It can be used for generating a minimal spanning

# tree using Kruskal's algorithm.

# http://en.wikipedia.org/wiki/Kruskal's_algorithm



class DisjointSetNode

  attr_accessor :parent, :rank



  def initialize

    @parent = self

    @rank = 0

  end



  # An optimised union by rank. Attaches smaller tree to larger.

  def union(other)

    self_root = self.find

    other_root = other.find

    if self_root.rank > other_root.rank

      other_root.parent = self_root

    elsif self_root.rank < other_root.rank

      self_root.parent = other_root

    elsif self_root != other_root

      other_root.parent = self_root

      self_root.rank += 1

    end

  end



  def find

    if self.parent === self

      self

    else

      self.parent = self.parent.find

    end

  end



end   # class DisjointSetNode

Some simple test code:



require 'disjointsetnode'

require 'test/unit'

require 'test/unit/ui/console/testrunner'



    class DisjointSetTest < Test::Unit::TestCase

      N_Nodes = 1000



      def setup

        @nodes = Array.new

        (1..N_Nodes).each do |node|

        @nodes << DisjointSetNode.new

        end

      end



      # def teardown

      # end



      def test_creation

        @nodes.each do |node|

          assert !node.nil?, "A Node is nil!"

        end

      end



      def test_initial_values

        @nodes.each do |node|

          assert node.parent === node, "self #{node}, parent #{node.parent} not equal."

          assert node.rank == 0, " A node's rtank is not 0."

        end

      end



      def test_union

        # Join all nodes in sequence

        @nodes.each do |node|

          if !@lastnode.nil?

            node.union(@lastnode)

            node_f = node.find

            lnode_f = @lastnode.find

            assert node_f == lnode_f, "Join not completed: node_f: #{node_f}, lnode_f: #{lnode_f}"

          end

          @lastnode = node

        end

      end



      def test_random_union

        (1..N_Nodes-1).each do |n|

          node = @nodes[n]

          other = @nodes[rand(N_Nodes-1)]

          node.union(other)

          node_f = node.find

          onode_f = other.find

          assert node_f == onode_f, "Join not completed: node_f: #{node_f}, onode_f: #{onode_f}"

        end

      end

    end



# This runs the tests for ya! 

Test::Unit::UI::Console::TestRunner.run(DisjointSetTest)

DZone Snippets: Dr_saturn's Code Snippets

Disjoint Set Class in Ruby