public
Last active — forked from thuss/README.rdoc

  • Download Gist
README.rdoc
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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
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
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.