class PrettyAssociationInspect::Graph

Public Class Methods

new(data) click to toggle source
# File lib/pretty_association_inspect.rb, line 20
def initialize(data)
  @nodes = data.map do |node_id, edges|
    edges.map!{|edge| Edge.new(*edge)}
    Node.new(node_id, edges)
  end
end

Public Instance Methods

minimum_route(start_id, goal_id, max_cost) click to toggle source
# File lib/pretty_association_inspect.rb, line 42
def minimum_route(start_id, goal_id, max_cost)
  search_by_dikstra(start_id, goal_id, max_cost)
  passage = @nodes.find { |node| node.id == goal_id }
  route = [passage]
  while passage = @nodes.find { |node| node.id == passage.from }
    route << passage
  end
  route
end
print_route(route) click to toggle source
search_by_dikstra(start_id, goal_id, max_cost) click to toggle source
# File lib/pretty_association_inspect.rb, line 52
def search_by_dikstra(start_id, goal_id, max_cost)
  @nodes.each do |node|
    node.cost = node.id == start_id ? 0 : nil
    node.done = false
    node.from = nil
  end
  loop do
    next_node = nil
    @nodes.each do |node|
      next if node.done || node.cost.nil?
      next_node = node if next_node.nil? || node.cost < next_node.cost
    end
    break if next_node.nil?
    next_node.done = true
    next_node.edges.each do |edge|
      reachble_node = @nodes.find { |node| node.id == edge.node_id }
      reachble_cost = next_node.cost + edge.cost
      next if reachble_node.nil?
      next if reachble_cost > max_cost
      if reachble_node.cost.nil? || reachble_cost < reachble_node.cost
        reachble_node.cost = reachble_cost
        reachble_node.from = next_node.id
      end
    end
  end
end