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