class UnionFind::UnionFind

@author Robert Sedgewick @author Kevin Wayne @author Michael Imstepf @see algs4.cs.princeton.edu/15uf/UF.java.html @see algs4.cs.princeton.edu/15uf/

Attributes

components[RW]

Public Class Methods

new(components) click to toggle source

Initializes an empty union-find data structure with n isolated components 0 through n-1. @param components [Array] components @raise [ArgumentError] if components.length < 1 or if components is not an Array

# File lib/union_find.rb, line 33
def initialize(components)
  # Unexpected behaviour,
  # for Sets the @components does not copy the content of components
  # rather it points to the components variable and any changes to the components
  # variables are reflected in @components.
  # Force copy instead.
  @components = components.dup

  raise ArgumentError, 'input is not a Set' unless @components.is_a? Set   

  @number_of_isolated_components = @components.length

  raise ArgumentError, 'number of components is < 1' if @number_of_isolated_components < 1         

  @parent = {} # parent of component
  @tree_size = {} # size of tree rooted at component (cannot be more than 31)
end

Public Instance Methods

add(component) click to toggle source

Dynamically adds component. @return [Component] component

# File lib/union_find.rb, line 53
def add(component)
  if @components.add?(component)
    # if component does not already exist
    @number_of_isolated_components += 1
  end
end
connected?(component_1, component_2) click to toggle source

Do two components share the same root? @param component_1 [Component] component @param component_2 [Component] component

@return [Boolean]

# File lib/union_find.rb, line 100
def connected?(component_1, component_2)
  find_root(component_1) == find_root(component_2)
end
count_isolated_components() click to toggle source

Returns the number of isolated components. @return [Interger] the number of components

# File lib/union_find.rb, line 62
def count_isolated_components
  @number_of_isolated_components
end
union(component_1, component_2) click to toggle source

Connect root of component 1 with root of component 2 by attaching smaller subtree root node with larger tree. If both trees have the same size, the root of the second component becomes a child of the root of the first component. @param component_1 [Component] component @param component_2 [Component] component @return [Component, NilClass] the root of the larger tree or the root of the first component if both have the same tree size or nil if no connection has been made

# File lib/union_find.rb, line 73
def union(component_1, component_2)
  root_component_1 = find_root(component_1)
  root_component_2 = find_root(component_2)

  # exit if already connected
  return nil if root_component_1 == root_component_2

  # make smaller root point to larger one
  if @tree_size[root_component_1] < @tree_size[root_component_2]
    @parent[root_component_1] = root_component_2
    root = root_component_2
    @tree_size[root_component_2] += @tree_size[root_component_1]
  else
    @parent[root_component_2] = root_component_1
    root = root_component_1
    @tree_size[root_component_1] += @tree_size[root_component_2]
  end
  
  @number_of_isolated_components -= 1

  root
end

Private Instance Methods

find_root(component) click to toggle source

Returns the root of a component. @param component [Component] component @return [Component] the root of the component @raise [IndexError] unless component exists

# File lib/union_find.rb, line 110
def find_root(component)
  raise IndexError, 'component does not exist' unless @components.include? component
  
  set_parent_and_tree_size(component)

  while component != @parent[component] # stop at the top node where component id == parent id
    @parent[component] = @parent[@parent[component]] # path compression by halving
    component = @parent[component]
  end

  return component
end
set_parent_and_tree_size(component) click to toggle source

Sets parent and tree size for each component. To prevent initialize method from taking linear time, this method is used to do this assignment on demand. @param component [Component] component @return [Component] component

# File lib/union_find.rb, line 128
def set_parent_and_tree_size(component)    
  @parent[component] ||= component
  @tree_size[component] ||= 1
  component
end