Class: DepthFirstSearch

Inherits:
SearchAlgorithm show all
Defined in:
lib/usearchtree/depth.rb

Instance Attribute Summary

Attributes inherited from SearchAlgorithm

#goal, #history, #space, #start, #traversal, #tree

Instance Method Summary collapse

Methods inherited from SearchAlgorithm

#cost, #initialize, #path

Constructor Details

This class inherits a constructor from SearchAlgorithm

Instance Method Details

#search ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/usearchtree/depth.rb', line 2

def search
    @list = [@start]
    until @list.empty?
        @history << @list.clone
        parent_node = @list.pop
        @traversal << parent_node
        @cache[parent_node.key] = parent_node
        if parent_node == @goal
            return
        end
        parent_node.edges.reverse_each do |edge|
            node = edge.node
            cost = edge.cost
            if not @cache or not @cache.has_key? node.key
                @cache[node.key] = node
                @tree[node] = parent_node
                @list.push node
            end
        end
    end
end