class Djikstra::Graph

Attributes

edges[R]
nodes[R]
shortest_path_distance[R]

Public Class Methods

new(edges=[]) click to toggle source
# File lib/djikstra/graph.rb, line 5
def initialize(edges=[])
  @nodes = {}
  @edges = []
  
  edges.each do |e|
    args = e.unshift self
    
    @edges.push Edge.new(*args)
  end
end

Public Instance Methods

closest(universe) click to toggle source
# File lib/djikstra/graph.rb, line 79
def closest(universe)
  u = universe.first
  
  universe.each do |node|
    u = node if u > node.distance
  end
  u
end
collect_shortest_path_between(start_node,end_node) click to toggle source
# File lib/djikstra/graph.rb, line 65
def collect_shortest_path_between(start_node,end_node)
  # artifact, the distance is the end_node distance
  @shortest_path_distance = end_node.distance

  # walk from the end node down the previous_node list
  node = end_node
  path = [node.name]
  while node && node != start_node
    node = node.previous_node
    path.insert 0, node.name
  end
  path
end
find_node(name,raise_if_note_found=false) click to toggle source
# File lib/djikstra/graph.rb, line 16
def find_node(name,raise_if_note_found=false)
  node = @nodes[name]
  return node if node
  
  raise GraphError, %Q(Node "#{name}" not found!) if raise_if_note_found
  
  node = Node.new name
  @nodes[name] = node
  node
end
shortest_path_between(start,stop) click to toggle source
# File lib/djikstra/graph.rb, line 27
def shortest_path_between(start,stop)
  universe = []
  
  @nodes.each do |key,node|
    node.reset
    
    universe.push node
  end
  
  start_node = find_node(start, true)
  start_node.distance = 0
  
  while universe.size > 0
    start_node.neighbors.each do |neighbor|
      next unless universe.include? neighbor #skip visited nodes
      
      # untraversable branch
      raise GraphError, %Q(Node "#{start_node.name}" is not reachable) if start_node.infinite?
      
      dist = start_node.distance + start_node.distance_to(neighbor)
      
      if neighbor > dist
        neighbor.distance = dist
        neighbor.previous_node = start_node # collect the shortest path back
      end
    end
    
    universe.delete start_node
    
    start_node = closest(universe)
  end
  
  # walk backwards
  start_node = find_node(start, true)
  stop_node  = find_node(stop, true)
  collect_shortest_path_between(start_node,stop_node)
end