Class: UnionFind::UnionFind

Inherits:
Object
  • Object
show all
Defined in:
lib/union_find.rb

Overview

See Also:

Author:

  • Robert Sedgewick

  • Kevin Wayne

  • Michael Imstepf

Instance Method Summary collapse

Constructor Details

#initialize(components) ⇒ UnionFind

Initializes an empty union-find data structure with n isolated components 0 through n-1.

Parameters:

  • components (Array) —

    components

Raises:

  • (ArgumentError) —

    if components.length < 1 or if components is not an Array



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/union_find.rb', line 31

def initialize(components)
  raise ArgumentError, 'input is not an Array' unless components.class == Array   

  components = components.uniq # remove duplicates
  @number_of_isolated_components = components.length
  
  raise ArgumentError, 'number of components is < 1' if @number_of_isolated_components < 1         

  @parent = {} # parent of i
  @tree_size = {} # size of tree rooted at i (cannot be more than 31)
  components.each do |component|
    @parent[component] = component
    @tree_size[component] = 1
  end
end

Instance Method Details

#connected?(component_1, component_2) ⇒ Boolean

Do two components share the same root?

Parameters:

  • component_1 (Integer) —

    the integer representing one component

  • component_2 (Integer) —

    the integer representing the other component

Returns:

  • (Boolean) 


101
102
103
 
# File 'lib/union_find.rb', line 101

def connected?(component_1, component_2)
  find_root(component_1) == find_root(component_2)
end

#count_isolated_components ⇒ Interger

Returns the number of isolated components.

Returns:

  • (Interger) —

    the number of components



49
50
51
 
# File 'lib/union_find.rb', line 49

def count_isolated_components
  @number_of_isolated_components
end

#find_root(component) ⇒ Component

Returns the root of a component.

Parameters:

  • component_id (Integer) —

    the integer representing one component

Returns:

  • (Component) —

    the root of the component

Raises:

  • (IndexError) —

    unless component exists



57
58
59
60
61
62
63
64
65
66
 
# File 'lib/union_find.rb', line 57

def find_root(component)
  raise IndexError, 'component does not exist' unless @parent[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

#union(component_1, component_2) ⇒ Component, NilClass

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.

Parameters:

  • component_1_id (Integer) —

    the integer representing one component

  • component_2_id (Integer) —

    the integer representing the other component

Returns:

  • (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



75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/union_find.rb', line 75

def union(component_1, component_2)
  root_component_1 = find_root(component_1)
  root_component_2 = find_root(component_2)

  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