Class: NetworkX::UnionFind

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

Instance Method Summary collapse

Constructor Details

#initialize(nodes) ⇒ UnionFind

Returns a new instance of UnionFind.



3
4
5
6
7
8
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 3

def initialize(nodes)
  @unions = {}
  nodes.each_with_index do |node, index|
    @unions[node] = index
  end
end

Instance Method Details

#connected?(node_1, node_2) ⇒ Boolean

Returns:

  • (Boolean) 


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

def connected?(node_1, node_2)
  @unions[node_1] == @unions[node_2]
end

#union(node_1, node_2) ⇒ Object 



14
15
16
17
18
19
20
21
22
 
# File 'lib/networkx/auxillary_functions/union_find.rb', line 14

def union(node_1, node_2)
  return if connected?(node_1, node_2)
  node1_id = @unions[node_1]
  node2_id = @unions[node_2]

  @unions.each do |node, id|
    @unions[node] = node1_id if id == node2_id
  end
end