Class: RootedTree::Node

Inherits:
Linked::Item
  • Object
show all
Extended by:
Forwardable
Includes:
Linked::List
Defined in:
lib/rooted_tree/node.rb

Overview

Nodes are mutable by default, since creating anyting but simple leafs would otherwise be imposible. Calling #freeze on a node makes the entire subtree immutable. This is used by the Tree class which only operates on frozen node structures.

The following is an example of a rooted tree with maximum depth 2.

    r         - r, a, b, c, and d are internal vertices
 +--+---+     - vertices e, f, g, h, i, and j are leaves
 a  b   c     - vertices g, h, and i are siblings
+++ | +-+-+   - node a is an ancestor of j
d e f g h i   - j is a descendant of a
|
j

The terminology is mostly referenced from www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf.

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.[](value = nil) ⇒ Node

Creates a new node with the given object as its value, unless a Node is passed, in which case it will be returned.



34
35
36
37
 
# File 'lib/rooted_tree/node.rb', line 34

def self.[](value = nil)
  return value if value.is_a? self
  new value
end

Instance Method Details

#+(other) ⇒ Node

Add two roots together to create a larger tree. A new common root will be created and returned. Note that if the any of the root nodes are not frozen they will be modified, and as a result seize to be roots.



215
216
217
218
219
220
221
222
223
224
225
 
# File 'lib/rooted_tree/node.rb', line 215

def +(other)
  unless root? && other.root?
    raise StructureException, 'Only roots can be added'
  end

  a = frozen? ? dup : self
  b = other.frozen? ? other.dup : other

  ab = self.class.new
  ab << a << b
end

#==(other) ⇒ true

Compare one node (sub)structure with another.



232
233
234
235
236
237
238
 
# File 'lib/rooted_tree/node.rb', line 232

def ==(other)
  return false unless other.is_a? self.class
  return false unless degree == other.degree
  return false unless value == other.value

  children.to_a == other.children.to_a
end

#ancestors {|Node| ... } ⇒ Enumerator

Iterates over the nodes above this in the tree hierarchy and yields them to a block. If no block is given an enumerator is returned.

Yields:

  • (Node) —

    each parent node.



70
 
# File 'lib/rooted_tree/node.rb', line 70

def_delegator :ancestors, :count, :depth

#child(index = nil) ⇒ Node Also known as: []

Accessor method for any of the n children under this node. If called without an argument and the node has anything but exactly one child an exception will be raised.

Raises:

  • (RangeError) 


139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/rooted_tree/node.rb', line 139

def child(index = nil)
  unless index
    raise ArgumentError, 'No index for node with degree != 1' if degree != 1
    return first
  end

  rtl, index = wrap_index index

  raise RangeError, 'Child index out of range' if index >= degree

  children(rtl: rtl).each do |c|
    break c if index.zero?
    index -= 1
  end
end

#children(rtl: false, &block) ⇒ Object

Yields each of the node children. The default order is left-to-right, but by passing rtl: true the order is reversed. If a block is not given an enumerator is returned.

Note that the block will catch any StopIteration that is raised and terminate early, returning the value of the exception.



127
128
129
 
# File 'lib/rooted_tree/node.rb', line 127

def children(rtl: false, &block)
  rtl ? reverse_each_item(&block) : each_item(&block)
end

#each {|Node| ... } ⇒ Enumerator

Returns if no block is given.

Yields:

  • (Node) —

    first self is yielded and then the children who in turn yield their children.



160
161
162
163
164
 
# File 'lib/rooted_tree/node.rb', line 160

def each(&block)
  return to_enum(__callee__) unless block_given?
  yield self
  children { |v| v.each(&block) }
end

#edges {|Array<Node>| ... } ⇒ Enumerator

Iterates over each edge in the tree.

Yields:

  • (Array<Node>) —

    each connected node pair.



200
201
202
203
204
205
206
207
 
# File 'lib/rooted_tree/node.rb', line 200

def edges(&block)
  return to_enum(__callee__) unless block_given?

  children do |v|
    yield self, v
    v.edges(&block)
  end
end

#leafs(rtl: false, &block) ⇒ Object

Iterates over each of the leafs.



190
191
192
193
194
 
# File 'lib/rooted_tree/node.rb', line 190

def leafs(rtl: false, &block)
  return to_enum(__callee__, rtl: rtl) unless block_given?
  return yield self if leaf?
  children(rtl: rtl) { |v| v.leafs(rtl: rtl, &block) }
end

#max_degree ⇒ Integer 



82
83
84
 
# File 'lib/rooted_tree/node.rb', line 82

def max_degree
  children.map(&:degree).push(degree).max
end

#max_depth(offset = depth) ⇒ Integer 



75
76
77
78
79
 
# File 'lib/rooted_tree/node.rb', line 75

def max_depth(offset = depth)
  return offset if leaf?

  children.map { |c| c.max_depth offset + 1 }.max
end

#parent ⇒ Node

Access the parent node. Raises a StopIteration if this node is the root.

Raises:

  • (StopIteration) —

    if this node is the root.



99
100
101
102
 
# File 'lib/rooted_tree/node.rb', line 99

def parent
  raise StopIteration if root?
  list
end

#root ⇒ Node 



64
65
66
67
 
# File 'lib/rooted_tree/node.rb', line 64

def root
  return self if root?
  loop.reduce(self) { |node,| node.parent }
end

#size ⇒ Integer

Calculate the size in vertecies of the subtree.



89
90
91
 
# File 'lib/rooted_tree/node.rb', line 89

def size
  children.reduce(1) { |a, e| a + e.size }
end

#to_a(flatten: false) ⇒ Array<Node, Array>

Converts the tree structure to a nested array of the nodes. Each internal node is placed at index zero of its own array, followed by an array of its children. Leaf nodes are not wraped in arrays but inserted directly.

Example

  r
 / \
a   b  => [r, [[a, [c]], b]]
|
c



180
181
182
183
184
 
# File 'lib/rooted_tree/node.rb', line 180

def to_a(flatten: false)
  return each.to_a if flatten
  return self if leaf?
  [self, children.map(&:to_a)]
end