class Ogr::MinimumSpanningTree

Class implements Kruskal algorithm for finding Minimum Spanning Tree

Attributes

graph[R]
uf[R]

Public Class Methods

new(graph) click to toggle source
# File lib/ogr/minimum_spanning_tree.rb, line 7
def initialize(graph)
  @graph = graph
  @uf = UnionFind.new(@graph.vertexes.size)
end

Public Instance Methods

calculate() click to toggle source
# File lib/ogr/minimum_spanning_tree.rb, line 12
def calculate
  tree = []
  while edge = edges.shift
    from = graph.index(edge.from)
    to = graph.index(edge.to)

    unless uf.connected?(from, to)
      uf.union(from, to)
      tree << edge
    end
  end
  tree
end

Private Instance Methods

edges() click to toggle source
# File lib/ogr/minimum_spanning_tree.rb, line 28
def edges
  @edges ||= @graph.edges.sort_by(&:weight)
end