A sloppy shortest-path-first example

spf.rb

#!/usr/bin/env ruby

class Connection
  include Comparable

  attr_reader :node
  attr_accessor :metric
  def initialize(node, metric)
    @node = node
    @metric = metric
  end

  def <=>(other)
    metric <=> other.metric
  end
end

class Node
  attr_reader :name, :connections

  # This is how you make a new node
  def initialize(name)
    @name = name
    @connections = []
  end

  def neighbors
    @connections.collect(&:node)
  end

  # Add a direct neighbor to this node
  def add_neighbor(neighbor, metric = 1)
    # has to be an actual node...
    raise "InvalidNeighbor" unless neighbor.is_a?(Node)
    raise "InvalidMetric" unless metric.is_a?(Integer)

    # skip duplicates
    unless neighbors.include?(neighbor)
      # Add the membership
      @connections << Connection.new(neighbor, metric)
      # both sides should know about the relationship
      neighbor.add_neighbor(self, metric)
    end
  end

  def to_s
    name
  end

  # returns the metric value for a connection to a given node
  def metric_to(node)
    raise "InvalidNode" unless node.is_a?(Node)
    return 0 if node == self

    # check for a direct connection
    @connections.each do |connection|
      return connection.metric if connection.node == node
    end

    # otherwise, get the path to that node
    metric_summation to(node)
  end

  # recursively find a path to a destination node
  def to(node, current_path = [])
    raise "InvalidNode" unless node.is_a?(Node)
    raise "InvalidPath" unless current_path.is_a?(Array)

    # No loops
    return nil if current_path.include?(self)

    # Don't bother with the graph for a path to myself
    return [] if node == self

    # A place to store multiple paths
    paths = []

    # iterate over connections, looking for paths to our destination
    @connections.each do |connection|
      if connection.node == node
        # If we've found a direct neighbor
        paths << current_path + [self, node]
      else
        # Otherwise, look for a path to the destination
        path_from_neighbor = connection.node.to(node, current_path + [self])
        paths << path_from_neighbor if path_from_neighbor
      end
    end

    # select only the shortest path to our destination (lowest total metric)
    shortest_path = paths.min {|x,y| metric_summation(x) <=> metric_summation(y) }
  end

  private

  # Sum all the metrics along a path
  def metric_summation(path)
    path_metrics = [] # We'll gather all the individual metrics in here
    # look at the metric between each node, skipping the last node (no further connections)
    path.each_with_index {|n, i| path_metrics << n.metric_to(path[i + 1]) if path[i + 1] }
    # Ruby syntactic sugar to add all the items in an array
    path_metrics.inject(&:+)
  end
end

# Given nodes a..g (inclusive) and the following connections:
#
#   [a, b], [b, c], [b, d], [c, d], [d, e],
#   [d, h], [e, f], [h, g]
#
#   Represented as a graph:
#
#   a - b - c
#        `---`- d - e - f
#                `- h - g
#
# Find the shortest path from node a to node g

a = Node.new('a')
b = Node.new('b')
c = Node.new('c')
d = Node.new('d')
e = Node.new('e')
f = Node.new('f')
g = Node.new('g')
h = Node.new('h')
a.add_neighbor(b)
b.add_neighbor(c)
b.add_neighbor(d)
c.add_neighbor(d)
d.add_neighbor(e)
d.add_neighbor(h)
e.add_neighbor(f)
h.add_neighbor(g)

puts a.to(g).join(' => ')
#  a => b => d => h => g

Now with metrics!

Try changing b.add_neighbor(d) to b.add_neighbor(d, 4) (adding a metric of '4' to that connection) and watch the path change!