Class: Silicium::Graphs::UnionFind

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

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ UnionFind

Returns a new instance of UnionFind.



5
6
7
8
9
10
 
# File 'lib/graph/kruskal.rb', line 5

def initialize(graph)
  @parents = []
  graph.vertices.keys.each do |vertex|
    @parents[vertex] = vertex
  end
end

Instance Method Details

#connected?(vertex1, vertex2) ⇒ Boolean

Returns:

  • (Boolean) 


12
13
14
 
# File 'lib/graph/kruskal.rb', line 12

def connected?(vertex1, vertex2)
  @parents[vertex1] == @parents[vertex2]
end

#union(vertex1, vertex2) ⇒ Object 



16
17
18
19
 
# File 'lib/graph/kruskal.rb', line 16

def union(vertex1, vertex2)
  parent1, parent2 = @parents[vertex1], @parents[vertex2]
  @parents.map! { |i| i == parent1 ? parent2 : i }
end