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