class Newral::Graphs::TreeSearch

the algorithms are heavily inspired by the Udacity course from Sebastian Thrun classroom.udacity.com/courses/cs271

Attributes

frontier[R]

Public Class Methods

new( graph: nil, start_node: nil, end_node: nil ) click to toggle source
# File lib/newral/graphs/tree_search.rb, line 10
def initialize( graph: nil, start_node: nil, end_node: nil  )
  @graph = graph 
  @start_node = start_node
  @end_node = end_node 
  path = Path.new(edges:[ Edge.new( start_node: start_node, end_node: start_node, directed: true, cost:0 )])
  @explored = {end_node: 0 }
  @frontier = [ path ]
end

Public Instance Methods

measure( path ) click to toggle source

the standard approach is breath first

# File lib/newral/graphs/tree_search.rb, line 54
def measure( path )
  path.length
end
remove_choice() click to toggle source
# File lib/newral/graphs/tree_search.rb, line 45
def remove_choice
  @frontier.sort! do |path1,path2|
    measure( path2 ) <=> measure( path1 ) # reverse
  end
  puts "frontier: #{@frontier.length}"
  @frontier.pop # pops shortest
end
run() click to toggle source
# File lib/newral/graphs/tree_search.rb, line 19
def run

  while @frontier.length > 0 
    path = remove_choice
    return path if path.end_node == @end_node
    edges = @graph.find_edges( path.end_node)
    puts "no edges found for #{path.end_node.name} #{@graph.edges.length}" unless edges.length > 0
    edges.each do |edge|
      begin
        end_node = edge.start_node == path.end_node ? edge.end_node : edge.start_node
        new_edge = Edge.new( start_node: path.end_node, end_node: end_node, directed: true, cost: edge.cost )
        puts( "n:#{ new_edge.to_s } e:#{edge} n:#{end_node} s:#{path.end_node} #{edge.start_node == new_edge.end_node } #{edge.end_node}")
        new_path = Path.new(edges:path.edges).add_edge( new_edge )
        if  @explored[new_path.end_node].nil? ||  measure( path  ) < @explored[new_path.end_node]
          @frontier << new_path
          @explored[ new_path.end_node ] = measure( new_path )
        end
      rescue Errors::CircularPath
        puts "circular #{ new_path.to_s }"
        # no need to check this path
      end
    end
  end
  raise Errors::FrontierEmpty 
end