Module: BehaviorTree::TreeStructure::Algorithms

Included in:
BehaviorTree::Tree
Defined in:
lib/behavior_tree/concerns/tree_structure/algorithms.rb

Overview

Basic tree algorithms.

Instance Method Summary collapse

Instance Method Details

#cycle? ⇒ Boolean

Returns:

  • (Boolean) 


28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# 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) ⇒ Object

Raises:

  • (ArgumentError) 


44
45
46
47
48
49
50
51
 
# 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 ⇒ Object 



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


24
25
26
 
# File 'lib/behavior_tree/concerns/tree_structure/algorithms.rb', line 24

def uniq_nodes?
  repeated_nodes.empty?
end