Class: DisjointUnionInternal

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures_rmolinari/disjoint_union_internal.rb

Overview

A “disjoint set union” that represents a set of elements that belonging to disjoint subsets. Alternatively, this expresses a partion of a fixed set.

The data structure provides efficient actions to merge two disjoint subsets, i.e., replace them by their union, and determine if two elements are in the same subset.

The elements of the set must be 0, 1, …, n-1. Client code can map its data to these representatives. The code uses several ideas from Tarjan and van Leeuwen for efficiency

See en.wikipedia.org/wiki/Disjoint-set_data_structure for a good introduction.

  • Tarjan, Robert E., van Leeuwen, Jan (1984). “Worst-case analysis of set union algorithms”. Journal of the ACM. 31 (2): 245–281.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ DisjointUnionInternal

Returns a new instance of DisjointUnionInternal.

Parameters:

  • size —

    the size of the universe, which must be known at the time of construction. The elements 0, 1, …, size - 1 start out in disjoint singleton subsets.



18
19
20
21
22
23
24
25
 
# File 'lib/data_structures_rmolinari/disjoint_union_internal.rb', line 18

def initialize(size)
  @size = size
  # Initialize to
  @d = (0...size).to_a
  @rank = [0] * size

  @subset_count = size
end

Instance Attribute Details

#subset_count ⇒ Object (readonly)

Returns the value of attribute subset_count.



14
15
16
 
# File 'lib/data_structures_rmolinari/disjoint_union_internal.rb', line 14

def subset_count
  @subset_count
end

Instance Method Details

#find(e) ⇒ Integer

The canonical representative of the subset containing e. Two elements d and e are in the same subset exactly when find(d) == find(e).

Parameters:

  • e —

    must be one of 0, 1, …, size-1.

Returns:

  • (Integer) —

    one of 0, 1, …, size-1.



47
48
49
50
51
52
 
# File 'lib/data_structures_rmolinari/disjoint_union_internal.rb', line 47

def find(e)
  # We implement find with "halving" to shrink the length of paths to the root. See Tarjan and van Leeuwin p 252.
  x = e
  x = @d[x] = @d[@d[x]] while @d[@d[x]] != @d[x]
  @d[x]
end

#unite(e, f) ⇒ Object

Declare that e and f are equivalent, i.e., in the same subset. If they are already in the same subset this is a no-op.

Each argument must be one of 0, 1, …, size-1.



30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/data_structures_rmolinari/disjoint_union_internal.rb', line 30

def unite(e, f)
  check_value(e)
  check_value(f)
  raise 'Uniting an element with itself is meaningless' if e == f

  e_root = find(e)
  f_root = find(f)
  return if e_root == f_root

  @subset_count -= 1
  link(e_root, f_root)
end