README.rdoc

rpcfn-3-shortest_path¶ ↑

My submission for Ruby Challenge #3: Short Circuit

rubylearning.com/blog/2009/10/30/rpcfn-short-circuit-3/

Features¶ ↑

• 100% RSpec test coverage

• Works in both Ruby 1.8 and 1.9

Explanation¶ ↑

I decided to play with a couple different concepts in this submission:

• Rather than using a known shortest path algorithm such as Dijkstra’s, I wanted to write my own from scratch with the goal of it being simple (even if it meant being computationally expensive).

• I wanted to make the algorithm recursive because I so rarely use recursion when building websites (my day job).

• I wanted to use Ruby’s infinity to represent the distance of an empty/dead-end path. It had a nice side effect of allowing me to remove all nil checks from the code.

Usage¶ ↑

require 'shortest_path'
include ShortestPath
shortest_path('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => [['A', 'B', 40]]
unused_paths('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => [['A', 'B', 50]]

shortest_path.rb

module ShortestPath
  
  NODES = 0..1 # Nodes are in positions 0 and 1 ['A', 'B', 20]
  LENGTH = 2   # Length is in position 2 
  INFINITY = 1.0/0 # http://weblog.jamisbuck.org/2007/2/7/infinity
  
  # Adds distance method to compute the distance of the current path 
  class Path < Array
    def distance
      (any?)? inject(0) { | sum, edge | sum += edge[LENGTH] } : INFINITY
    end
  end

  # Returns the unused edges between start_node and end_node
  # unused_paths('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => ['A', 'B', 50]  
  def unused_paths(start_node, end_node, graph)
    graph - shortest_path(start_node, end_node, graph)
  end

  # Returns the shortest path between start_node and end_node
  # shortest_path('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => ['A', 'B', 40]
  def shortest_path(start_node, end_node, graph)
    adjacent_edges = graph.select{ | edge | edge[NODES].include?(start_node) }
    remaining_edges = graph - adjacent_edges
    shortest_path = Path.new
    adjacent_edges.each do | edge |
      path = Path.new [edge]
      neighbor_node = (edge[NODES] - [start_node])[0] # ['A', 'B'] - ['A'] => ['B']
      unless neighbor_node == end_node
        path_ahead = shortest_path(neighbor_node, end_node, remaining_edges)
        (path_ahead.empty?)? path.clear : path.concat(path_ahead)
      end      
      shortest_path = path if path.distance < shortest_path.distance
    end
    shortest_path
  end
      
end

shortest_path_spec.rb

require File.dirname(__FILE__) + '/spec_helper.rb'

describe ShortestPath do
  include ShortestPath
  
  describe "when testing with the RPCFN 3 example graph" do
    before(:each) do
      @rpcfn_graph = [
        ['A', 'B', 50], ['A', 'D', 150], ['B', 'C', 250], ['B', 'E', 250], ['C', 'E', 350],
        ['C', 'D', 50], ['C', 'F', 100], ['D', 'F', 400], ['E', 'G', 200], ['F', 'G', 100]
      ]
    end
    
    it "should find the unused paths" do
      unused_paths('A', 'G', @rpcfn_graph).should eql([
        ["A", "B", 50], ["B", "C", 250], ["B", "E", 250], ["C", "E", 350], ["D", "F", 400], 
        ["E", "G", 200]
      ])
    end

    it "should find the shortest path" do
      path = shortest_path('A', 'G', @rpcfn_graph)
      path.should eql([["A", "D", 150], ["C", "D", 50], ["C", "F", 100], ["F", "G", 100]])
      path.distance.should eql(400)
    end
  end

  # This is where my TDD process started, trying to solve the simplest case and building on it
  it "should return an empty path if we can't complete the path" do
    shortest_path('A', 'X', [[ 'A', 'B', 50]]).empty?.should be_true
  end
  
  it "should find the shortest path with only 2 nodes and 1 edge" do
    graph = [[ 'A', 'B', 50]]
    shortest_path('A', 'B', graph).should eql(graph)
  end
  
  it "should find the shortest path with multiple legs strung together" do
    graph = [[ 'A', 'B', 50], ['B', 'C', 50], ['C', 'D', 50]]
    path = shortest_path('A', 'D', graph)
    path.should eql(graph)
    path.distance.should eql(150)
  end
  
  it "should find the shortest path with 2 nodes and 2 edges" do
    short = [['A', 'B', 40]]
    long = [['A', 'B', 50]]
    path = shortest_path('A', 'B', short + long)
    path.should eql(short)
    path.distance.should eql(40)
  end
  
  it "should choose a shortest path when 2 paths are equal" do
    path_a = [['A', 'B', 10], ['B', 'D', 20]]
    path_b = [['A', 'C', 20], ['C', 'D', 10]]
    path = shortest_path('A', 'D', path_a + path_b)
    path.should eql(path_a)
    path.distance.should eql(30)
  end

  it "should find the shortest path with multiple legs, multiple routes, and a dead end" do
    short = [['A', 'D', 20], ['D', 'E', 5]] # 25
    long = [[ 'A', 'B', 10], ['B', 'C', 10], ['B', 'Z', 1], ['C', 'E', 10]] # 30
    path = shortest_path('A', 'E', short + long)
    path.should eql(short)
    path.distance.should eql(25)
  end

end