Class: Uf::DisjointSet

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

Overview

A hash based representation of Disjoint Sets

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(elements) ⇒ DisjointSet

Returns a new instance of DisjointSet.



13
14
15
16
17
 
# File 'lib/uf.rb', line 13

def initialize(elements)
  @parent = {}
  @depth = {}
  create_disjoint_sets(elements)
end

Instance Attribute Details

#depth ⇒ Object (readonly) Also known as: rank

Returns the value of attribute depth.



9
10
11
 
# File 'lib/uf.rb', line 9

def depth
  @depth
end

#parent ⇒ Object (readonly)

Returns the value of attribute parent.



9
10
11
 
# File 'lib/uf.rb', line 9

def parent
  @parent
end

Instance Method Details

#connected?(el_a, el_b) ⇒ Boolean

Returns:

  • (Boolean) 


33
34
35
 
# File 'lib/uf.rb', line 33

def connected?(el_a, el_b)
  find_root(el_a) == find_root(el_b)
end

#create_disjoint_sets(elements) ⇒ Object 



19
20
21
22
23
24
 
# File 'lib/uf.rb', line 19

def create_disjoint_sets(elements)
  elements.each do |x|
    parent[x] = x
    depth[x] = 0
  end
end

#find_root(element) ⇒ Object 



26
27
28
29
30
31
 
# File 'lib/uf.rb', line 26

def find_root(element)
  if parent[element] != element
    parent[element] = find_root(parent[element]) # path compression
  end
  parent[element]
end

#union(el_a, el_b) ⇒ Object 



37
38
39
40
41
42
43
 
# File 'lib/uf.rb', line 37

def union(el_a, el_b)
  root_a = find_root(el_a)
  root_b = find_root(el_b)
  return if root_a == root_b

  update_depths(root_a, root_b)
end

#update_depths(root_a, root_b) ⇒ Object

make bigger tree set child of small



46
47
48
49
50
51
52
53
54
55
 
# File 'lib/uf.rb', line 46

def update_depths(root_a, root_b)
  if depth[root_a] > depth[root_b]
    parent[root_b] = root_a
  elsif depth[root_a] < depth[root_b]
    parent[root_a] = root_b
  else
    parent[root_a] = root_b
    depth[root_b] += 1
  end
end