Class: Wallace::Koza::Builder::FullBuilder

Inherits:
Wallace::Koza::Builder show all
Defined in:
lib/modules/koza/builder/full_builder.rb

Overview

The Full builder constructs Koza trees according to a slight variant of Koza’s FULL method. Unlike Koza’s original FULL method, this FULL method allows single node trees to be constructed.

A random integer d is selected as the depth of the tree, between the minimum and maximum depth limits inclusively. A full tree of exactly depth d is then generated.

Instance Attribute Summary

Attributes inherited from Wallace::Koza::Builder

#depth_limits, #non_terminals, #terminals

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Wallace::Koza::Builder

#prepare

Class Method Details

.full_subtree(terminals, non_terminals, depth, opts = {}) ⇒ Object

Builds a full subtree of a given depth using a variant of Koza’s FULL method (where single element sub-trees are acceptable).

Parameters:

  • terminals, the list of terminals.

  • non_terminals, the list of non-terminals.

  • depth, the depth of the sub-tree.

  • opts, a hash of keyword options for this method. -> random, the RNG to use for building the subtree.

Returns: The root node of the built sub-tree.



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/modules/koza/builder/full_builder.rb', line 22

def self.full_subtree(terminals, non_terminals, depth, opts = {})

  opts[:random] ||= Random.new

  # If we require a sub-tree of depth one then we simply return a node with a value
  # sampled from the set of terminals.
  return Wallace::Koza::KozaNode.new(terminals.sample(random: opts[:random])) if depth == 0

  # Construct the children of each node in the queue until there are no nodes
  # left to process. We assume that the node to be processed has children. This
  # is fine to assume since sub-trees of length one are created and returned above, and
  # terminal nodes aren't added to the queue for processing.
  root = Wallace::Koza::KozaNode.new(non_terminals.sample(random: opts[:random]), depth: 0)
  queue = [root]
  until queue.empty?

    parent = queue.shift
    parent.children = Array.new(parent.arity) do

      # To achieve a full tree we simply sample from the non-terminal set until the child
      # is at the maximum depth.
      if (parent.depth + 1) == depth
        value = terminals.sample(random: opts[:random])
      else
        value = non_terminals.sample(random: opts[:random])
      end

      # Build the node and add it to the queue (provided it isn't terminal).
      node = Wallace::Koza::KozaNode.new(value, parent: parent, depth: parent.depth + 1)
      queue << node unless node.terminal?
      node

    end unless parent.terminal?

  end
  return root

end

Instance Method Details

#build_subtree(depth, opts = {}) ⇒ Object

Builds a full subtree of a given maximum depth.

Parameters:

  • depth, the maximum depth of the sub-tree.

  • opts, a hash of keyword options for this method. -> random, the RNG to use for building the subtree.

Returns: The root node of the built sub-tree.

See FullBuilder.full_subtree



88
89
90
 
# File 'lib/modules/koza/builder/full_builder.rb', line 88

def build_subtree(depth, opts = {})
  self.class.full_subtree(@terminals, @non_terminals, depth, opts)
end

#build_tree(opts = {}) ⇒ Object

Builds a full tree whose depth is between the minimum and maximum depths inclusively and every sub-tree is full.

Parameters:

  • opts, a hash of keyword options for this method. -> random, the RNG to use for building the tree.

Returns: The built tree.



70
71
72
73
74
 
# File 'lib/modules/koza/builder/full_builder.rb', line 70

def build_tree(opts = {})
  opts[:random] ||= Random.new
  depth = opts[:random].rand(@depth_limits)
  Wallace::Koza::KozaTree.new(build_subtree(depth, random: opts[:random]))
end