class Silicium::Graphs::UnionFind

Public Class Methods

new(graph) click to toggle source
# File lib/graph/kruskal.rb, line 5
def initialize(graph)
  @parents = []
  graph.vertices.keys.each do |vertex|
    @parents[vertex] = vertex
  end
end

Public Instance Methods

connected?(vertex1, vertex2) click to toggle source
# File lib/graph/kruskal.rb, line 12
def connected?(vertex1, vertex2)
  @parents[vertex1] == @parents[vertex2]
end
union(vertex1, vertex2) click to toggle source
# 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