Class: DataStructuresRMolinari::DisjointUnion

Inherits:
Object
  • Object
show all
Includes:
Shared
Defined in:
lib/data_structures_rmolinari/disjoint_union.rb

Overview

TODO:

  • allow caller to expand the size of the universe. This operation is called “make set”.

    • All we need to do is increase the size of @d, set the parent pointers, define the new ranks (zero), and update @size.

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 are 0, 1, …, n-1, where n is the size of the universe. Client code can map its data to these representatives.

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

The code uses several ideas from Tarjan and van Leeuwen for efficiency. We use “union by rank” in unite and path-halving in find. Together, these make the amortized cost of each opperation effectively constant.

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

Constant Summary

Constants included from Shared

Shared::INFINITY

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Shared

#contains_duplicates?

Constructor Details

#initialize(initial_size = 0) ⇒ DisjointUnion

subsets.

Parameters:

  • initial_size (defaults to: 0) —

    the initial size of the universe. The elements 0, 1, …, initial_size - 1 start out in disjoint singleton



28
29
30
31
32
33
34
 
# File 'lib/data_structures_rmolinari/disjoint_union.rb', line 28

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

  @subset_count = initial_size
end

Instance Attribute Details

#subset_count ⇒ Object (readonly)

The number of subsets in the partition.



24
25
26
 
# File 'lib/data_structures_rmolinari/disjoint_union.rb', line 24

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 in the universe of elements

Returns:

  • (Integer) —

    one of the universe of elements



69
70
71
72
73
74
75
76
 
# File 'lib/data_structures_rmolinari/disjoint_union.rb', line 69

def find(e)
  check_value(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

#make_set(new_v) ⇒ Object

Add a new subset to the universe containing the element new_v

Parameters:

  • new_v —

    the new element, starting in its own singleton subset

    • it must be a non-negative integer, not already part of the universe of elements.

Raises:



39
40
41
42
43
44
45
46
 
# File 'lib/data_structures_rmolinari/disjoint_union.rb', line 39

def make_set(new_v)
  raise DataError, "Element #{new_v} must be a non-negative integer" unless new_v.is_a?(Integer) && !new_v.negative?
  raise DataError, "Element #{new_v} is already present" if @d[new_v]

  @d[new_v] = new_v
  @rank[new_v] = 0
  @subset_count += 1
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 in the universe of elements



51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/data_structures_rmolinari/disjoint_union.rb', line 51

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