Class: NetworkX::UnionFind

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

Overview

Union Find Tree

Reference - ac-library-rb DSU (CC0) - Python NetworkX UnionFind

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(nodes = nil) ⇒ UnionFind

Constructor for initializing Union Find Tree

Parameters:

  • nodes (?Array[Object]) (defaults to: nil) —

    nodes



19
20
21
22
23
24
25
26
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 19

def initialize(nodes = nil)
  @weights = {}
  @parents = {}
  nodes&.each do |node|
    @weights[node] = 1
    @parents[node] = node
  end
end

Instance Attribute Details

#parents ⇒ Hash{ Object => Object }

Return parent of each element

Returns:

  • (Hash{ Object => Object }) —

    the current value of parents



11
12
13
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 11

def parents
  @parents
end

#weights ⇒ Hash{ Object => Integer }

Return weight of each element

Returns:

  • (Hash{ Object => Integer }) —

    the current value of weights



11
12
13
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 11

def weights
  @weights
end

Instance Method Details

#[](node) ⇒ Object

Return the root of node

Parameters:

  • node (Object) —

    node

Returns:

  • (Object) —

    root of node, leader of node



33
34
35
36
37
38
39
40
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 33

def [](node)
  if @parents.has_key?(node)
    @parents[node] == node ? node : (@parents[node] = self[@parents[node]])
  else
    @weights[node] = 1
    @parents[node] = node
  end
end

#connected?(node1, node2) ⇒ bool Also known as: same?

Is each root of two nodes the same?

Parameters:

  • node1 (Object) —

    node

  • node2 (Object) —

    node

Returns:

  • (bool) —

    Is each root of node1 and nodes_2 the same?



68
69
70
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 68

def connected?(node1, node2)
  root(node1) == root(node2)
end

#each(&block) ⇒ Object 



53
54
55
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 53

def each(&block)
  @parents.each_key(&block)
end

#merge(node1, node2) ⇒ Object 



94
95
96
97
98
99
100
101
102
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 94

def merge(node1, node2)
  x = self[node1]
  y = self[node2]
  return if x == y

  x, y = y, x if @weights[x] < @weights[y]
  @weights[x] += @weights[y]
  @parents[y] = x
end

#root(node) ⇒ Object

Return the root of node

Parameters:

  • node (Object) —

    node

Returns:

  • (Object) —

    root of node, leader of node



47
48
49
50
51
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 47

def root(node)
  @parents.has_key?(node) or raise ArgumentError.new, "#{node} is not a node"

  @parents[node] == node ? node : (@parents[node] = root(@parents[node]))
end

#to_sets ⇒ Object Also known as: groups 



57
58
59
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 57

def to_sets
  each.group_by { |node| root(node) }.values
end

#union(*nodes) ⇒ Object | nil Also known as: unite

Unite nodes.

Parameters:

  • nodes (Array[Object]) —

    nodes

Returns:

  • (Object | nil) —

    root of united nodes



78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 78

def union(*nodes)
  return merge(*nodes) if nodes.size == 2

  roots = nodes.map { |node| self[node] }.uniq
  return if roots.size == 1

  roots.sort_by! { |root| @weights[root] }
  root = roots[-1]
  roots[0...-1].each do |r|
    @weights[root] += @weights[r]
    @parents[r] = root
  end
  root
end