class SearchAlgorithm

Author: Johnny Lee Othon

Attributes

goal[R]
history[R]
space[R]
start[R]
traversal[R]
tree[R]

Public Class Methods

new(space, start, goal, caches=true) click to toggle source

Initializes a search algorithm. Parameters:

space

a graph

start

the id or name of the starting node

goal

the id or name of the goal node

cache

true a cache of visited nodes is desired

# File lib/usearchtree/search.rb, line 12
def initialize space, start, goal, caches=true
    @space = space
    @start = space.node(start)
    @goal = space.node(goal)
    # node.key => node
    @cache = (Hash.new if caches)
    # order in which the graph nodes were traversed
    @traversal = Array.new
    # parent => parent_node
    @tree = {@start => nil}
    # lazy list of nodes from start to goal
    @path = Array.new
    # lazy total of cost from start to goal
    @cost = nil
    # history to see the history of the stack
    @history = Array.new
end

Public Instance Methods

cost() click to toggle source

Retruns the total cost from start to goal following the path specifed in SearchAlgorithm#Path.

# File lib/usearchtree/search.rb, line 52
def cost
    self.path if @path.empty?
    return @cost
end
path() click to toggle source

Returns a list of all nodes in order from start to goal.

# File lib/usearchtree/search.rb, line 37
def path
    return @path if @path.any?
    node = @goal
    @cost = 0
    while node
        parent = @tree[node]
        @path.insert(0, node)
        @cost += parent ? parent.cost(node) : 0
        node = parent
    end
    return @path
end