class Ogr::UnionFind
Class implements Union Find algorithm
Attributes
sizes[R]
store[R]
Public Class Methods
new(n)
click to toggle source
# File lib/ogr/union_find.rb, line 7 def initialize(n) @store = (0..n).to_a @sizes = [1] * n end
Public Instance Methods
connected?(x, y)
click to toggle source
# File lib/ogr/union_find.rb, line 12 def connected?(x, y) root(x) == root(y) end
union(x, y)
click to toggle source
# File lib/ogr/union_find.rb, line 16 def union(x, y) root_x = root(x) root_y = root(y) if sizes[root_y] > sizes[root_x] update_sizes(root_x, root_y) else update_sizes(root_y, root_x) end end
Private Instance Methods
root(x)
click to toggle source
# File lib/ogr/union_find.rb, line 33 def root(x) parent = store[x] parent = store[parent] while parent != store[parent] parent end
update_sizes(x, y)
click to toggle source
# File lib/ogr/union_find.rb, line 28 def update_sizes(x, y) store[x] = y sizes[y] += sizes[x] end