Class: Wukong::Widget::DisjointForest

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

Overview

Implements a disjoint-set data structure:

See Also:

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DisjointForest

Returns a new instance of DisjointForest.



13
14
15
16
 
# File 'lib/wu/graph/union_find.rb', line 13

def initialize
  @parent = {}
  @rank   = {}
end

Instance Attribute Details

#parent ⇒ Object (readonly)

Tree each node belongs to



9
10
11
 
# File 'lib/wu/graph/union_find.rb', line 9

def parent
  @parent
end

#rank ⇒ Object (readonly)

Depth of node in that tree



11
12
13
 
# File 'lib/wu/graph/union_find.rb', line 11

def rank
  @rank
end

Instance Method Details

#add(val) ⇒ Object Also known as: << 



18
19
20
21
 
# File 'lib/wu/graph/union_find.rb', line 18

def add(val)
  parent[val] = val
  rank[val]   = 0
end

#find(val) ⇒ Object Also known as: []

Returns the root (the identifying member) of the set that the given value belongs to.



28
29
30
31
 
# File 'lib/wu/graph/union_find.rb', line 28

def find(val)
  return val if root?(val)
  parent[val] = find parent[val]
end

#include?(val) ⇒ Boolean

Returns:

  • (Boolean) 


57
58
59
 
# File 'lib/wu/graph/union_find.rb', line 57

def include?(val)
  parent.include?(val)
end

#root?(val) ⇒ Boolean

Returns:

  • (Boolean) 


53
54
55
 
# File 'lib/wu/graph/union_find.rb', line 53

def root?(val)
  parent[val] == val
end

#union(val_a, val_b) ⇒ Object Also known as: merge 



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/wu/graph/union_find.rb', line 34

def union(val_a, val_b)
  add(val_a) if !include?(val_a)
  add(val_b) if !include?(val_b)
  root_a = find(val_a)
  root_b = find(val_b)
  return if root_a == root_b
  # a and b are in different sets; merge the smaller to the larger
  # Log.debug("Merging #{val_a} (root #{root_a} depth #{rank[root_a]} and #{val_b} (root #{root_b} depth #{rank[root_b]})")
  if    rank[root_a] < rank[root_b]
    parent[root_a] = root_b
  elsif rank[root_a] > rank[root_b]
    parent[root_b] = root_a
  else
    parent[root_a] = root_b
    rank[root_b] += 1
  end
end