module BehaviorTree::TreeStructure::Algorithms

Basic tree algorithms.

Constants

TRAVERSAL_TYPES

Public Instance Methods

cycle?() click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 28
def cycle?
  current_path = Set.new

  dfs = ->(node) {
    break true if current_path.include?(node)

    current_path << node
    result = node.children.any?(&dfs)
    current_path.delete node

    result
  }

  dfs.(chainable_node)
end
each_node(traversal_type = TRAVERSAL_TYPES.first, &block) click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 44
def each_node(traversal_type = TRAVERSAL_TYPES.first, &block)
  return enum_for(:each_node, traversal_type) unless block_given?

  raise ArgumentError, "Traversal type must be in: #{TRAVERSAL_TYPES}" unless TRAVERSAL_TYPES.any?(traversal_type)

  send("#{traversal_type}_node_yielder", &block)
  nil
end
repeated_nodes() click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 7
def repeated_nodes
  visited = Set.new
  repeated_nodes = Set.new

  dfs = ->(node) {
    break repeated_nodes << node if visited.include?(node)

    visited << node

    node.children.each(&dfs)
  }

  dfs.(chainable_node)

  repeated_nodes
end
uniq_nodes?() click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 24
def uniq_nodes?
  repeated_nodes.empty?
end

Private Instance Methods

breadth_node_yielder() { |node, depth, idx, parent_node| ... } click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 55
def breadth_node_yielder
  queue = [[chainable_node, 0, self]]
  idx = 0
  depth = 0
  until queue.empty?
    node, depth, parent_node = queue.shift # Remove first
    # Enqueue node with depth and parent.
    queue.concat(node.children.map { |child| [child, depth + 1, node] })
    yield(node, depth, idx, parent_node)
    idx += 1
  end
end
depth_postorder_node_yielder() { |node, depth, idx, parent_node| ... } click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 68
def depth_postorder_node_yielder
  idx = 0

  dfs = ->(node, depth, parent_node) {
    node.children.each { |child| dfs.(child, depth + 1, node) }
    yield(node, depth, idx, parent_node)
    idx += 1
  }

  dfs.(chainable_node, 0, self)
end
depth_preorder_node_yielder() { |node, depth, idx, parent_node| ... } click to toggle source
# File lib/behavior_tree/concerns/tree_structure/algorithms.rb, line 80
def depth_preorder_node_yielder
  idx = 0

  dfs = ->(node, depth, parent_node) {
    yield(node, depth, idx, parent_node)
    idx += 1
    node.children.each { |child| dfs.(child, depth + 1, node) }
  }

  dfs.(chainable_node, 0, self)
end