Class: Ogr::UnionFind

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/union_find.rb

Overview

Class implements Union Find algorithm

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ UnionFind

Returns a new instance of UnionFind.



7
8
9
10
 
# File 'lib/ogr/union_find.rb', line 7

def initialize(n)
  @store = (0..n).to_a
  @sizes = [1] * n
end

Instance Method Details

#connected?(x, y) ⇒ Boolean

Returns:

  • (Boolean) 


12
13
14
 
# File 'lib/ogr/union_find.rb', line 12

def connected?(x, y)
  root(x) == root(y)
end

#union(x, y) ⇒ Object 



16
17
18
19
20
21
22
23
24
 
# 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