############ | |
#Class Hash# | |
############ | |
#Dijkstra's algorythm requires a priority queue, the easiest way to make one is to add a method | |
#to hash that pops the key/value pair with the lowest value. | |
class Hash | |
#Return the key/value pair with the lowest value as an array, deletes the pair. | |
def pop_lowest_value! | |
smallest_pair = self.min{ |a,b| a[1] <=> b[1]} | |
self.delete(smallest_pair[0]) if smallest_pair | |
smallest_pair | |
end | |
end | |
############# | |
#Class Graph# | |
############# | |
#A graph is represented as a collection of Edges, an edge representing the relationship between a pair of vertices. | |
#This implementation assumes the Graph is connected ie. every vertex can be reached from every other vertex by | |
#some collection of edges. Failure to supply a graph structure that follows this rule will most likely cause spurious | |
#results, or more likely, outright failures. | |
# | |
#A Graph is instanciated with a array of arrays, where each internal array is a tupple representing an edge in the | |
#form ["name of vertex a", "name of vertex b", distance] | |
# | |
#After the dijkstra method has been run on the graph, for any given end vertex you can print the shortest path, | |
#print the set of unused edges, or return a set of the unused edges as an array similar to the input of Graph.new. | |
# | |
#Usage: | |
#edges = [ | |
# [ "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], | |
# ] | |
#graph = Graph.new edges | |
#graph.dijkstra "A" | |
#graph.print_shortest_path "G" | |
#graph.print_unused_edges "G" | |
#graph.unused_edges_as_array "G" | |
# | |
class Graph | |
#Edge data structure, represents an edge in a graph | |
Edge = Struct.new(:vertices, :distance) | |
#Builds the underlying datastructures required to process a graph. | |
def initialize edges | |
#The edges in this graph | |
@edges = [] | |
edges.each do |e| | |
@edges << Edge.new([e[0], e[1]], e[2]) | |
end | |
puts "The following edges make up the full graph:" | |
print_edges_as_array @edges | |
end | |
#Runs Dijkstra's algorythm on the graph to generate the least cost tree(@previous) | |
def dijkstra start | |
puts "Generating least cost tree from vertex #{start}." | |
@previous = {} #The least cost tree generated by Dijkstra's algorythm | |
@final_distances = {} #The hash of final distances to all vertices after running Dijkstra's algorythm | |
queue = {} #The queue of verticies to process | |
queue[start] = 0 | |
#The actual algorythm | |
while !queue.empty? do | |
vertex, distance = *queue.pop_lowest_value! | |
@final_distances[vertex] = distance | |
get_neighbors(vertex).each do | neighbor | | |
next if @final_distances.has_key? neighbor | |
distance_to_neighbor = @final_distances[vertex] + get_edge(vertex, neighbor).distance | |
if (queue[neighbor].nil? or distance_to_neighbor < queue[neighbor]) then | |
queue[neighbor] = distance_to_neighbor | |
@previous[neighbor] = vertex | |
end | |
end | |
end | |
end | |
#Returns (as an Array of Arrays) the set of unused Edges for any given end vertex | |
def unused_edges_as_array finish | |
unused_edges(finish).inject([]) do |memo, edge| | |
memo << [edge.vertices[0], edge.vertices[1], edge.distance] | |
end | |
end | |
#Prints the unused edges with nice formating | |
def print_unused_edges finish | |
puts "The following edges are unused:" | |
print_edges_as_array unused_edges(finish) | |
end | |
#Prints the shortest path with nice formating | |
def print_shortest_path finish | |
puts "The shortest path to #{finish} is:" | |
puts shortest_path(finish).join("->") | |
end | |
################# | |
#Private Methods# | |
################# | |
private | |
#Prints an array of Edges with the Array formatting used on Ruby Learning's RPCFN | |
def print_edges_as_array edges | |
puts "[" | |
edges.each do |edge| | |
puts " [ \"#{edge.vertices[0]}\", \"#{edge.vertices[1]}\", #{edge.distance}, ]\n" | |
end | |
puts "]" | |
end | |
#Returns (as an Array of Edge objects) the set of unused Edges for any given end vertex | |
def unused_edges finish | |
used_edges = [] | |
#find all the used edges | |
current_vertex = finish | |
while @previous[current_vertex] | |
edge = get_edge current_vertex, @previous[current_vertex] | |
used_edges << edge | |
current_vertex = @previous[current_vertex] | |
end | |
#find the unused edges | |
@edges.select{ |e| ! used_edges.include? e } | |
end | |
#Returns an Array of vertex names (as Strings) representing the shortest path to finish | |
def shortest_path finish | |
path = [] | |
current_vertex = finish | |
path << current_vertex | |
while @previous[current_vertex] | |
path << @previous[current_vertex] | |
current_vertex = @previous[current_vertex] | |
end | |
path.reverse | |
end | |
#Returns the Edge joining vertex_a and vertex_b | |
def get_edge vertex_a, vertex_b | |
@edges.select{ |e| (e.vertices.include? vertex_a) && (e.vertices.include? vertex_b) }.first | |
end | |
#Returns an Array of names (as Strings) of verticies neighboring the given vertex | |
def get_neighbors vertex | |
@edges.inject([]) do |neighbors, edge| | |
neighbors.push(edge.vertices.reject{ |v| v == vertex }) if edge.vertices.include? vertex | |
neighbors.flatten | |
end.uniq | |
end | |
end | |
################## | |
#Class GraphTests# | |
################## | |
require 'test/unit' | |
require 'stringio' | |
class GraphTests < Test::Unit::TestCase | |
def setup | |
@default_graph_edges ||= [ | |
[ "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], | |
] | |
@easy_graph_edges ||= [ | |
[ "A", "B", 50] | |
] | |
@circular_graph_edges ||= [ | |
[ "A", "B", 50 ], | |
[ "B", "C", 50 ], | |
[ "C", "D", 50 ], | |
[ "D", "E", 50 ], | |
[ "E", "F", 50 ], | |
[ "F", "A", 50 ], | |
] | |
end | |
def test_default_graph | |
start = "A" | |
finish = "G" | |
expected = [ | |
[ 'A', 'B', 50 ], | |
[ 'B', 'C', 250], | |
[ 'B', 'E', 250], | |
[ 'C', 'E', 350], | |
[ 'D', 'F', 400], | |
[ 'E', 'G', 200], | |
] | |
run_unused_edge_test @default_graph_edges, start, finish, expected | |
end | |
def test_easy_graph | |
start = "A" | |
finish = "B" | |
expected = [] | |
capture_console do #suppres the console chatter | |
run_unused_edge_test @easy_graph_edges, start, finish, expected | |
end | |
end | |
def test_circular_graph | |
start = "A" | |
finish = "E" | |
expected = [ | |
[ "A", "B", 50 ], | |
[ "B", "C", 50 ], | |
[ "C", "D", 50 ], | |
[ "D", "E", 50 ], | |
] | |
capture_console do #suppres the console chatter | |
run_unused_edge_test @circular_graph_edges, start, finish, expected | |
end | |
end | |
def test_print_methods_for_default_graph | |
start = "A" | |
finish = "G" | |
expected = "The shortest path to #{finish} is:\n" + | |
"A->D->C->F->G\n" + | |
"The following edges are unused:\n" + | |
"[\n" + | |
" [ \"A\", \"B\", 50, ]\n" + | |
" [ \"B\", \"C\", 250, ]\n" + | |
" [ \"B\", \"E\", 250, ]\n" + | |
" [ \"C\", \"E\", 350, ]\n" + | |
" [ \"D\", \"F\", 400, ]\n" + | |
" [ \"E\", \"G\", 200, ]\n" + | |
"]\n" | |
run_print_test @default_graph_edges, start, finish, expected | |
end | |
def test_print_methods_for_easy_graph | |
start = "A" | |
finish = "B" | |
expected = "The shortest path to #{finish} is:\n" + | |
"A->B\nThe following edges are unused:\n" + | |
"[\n" + | |
"]\n" | |
run_print_test @easy_graph_edges, start, finish, expected | |
end | |
def test_print_methods_for_circular_graph | |
start = "A" | |
finish = "E" | |
expected = "The shortest path to #{finish} is:\n" + | |
"A->F->E\n" + | |
"The following edges are unused:\n" + | |
"[\n" + | |
" [ \"A\", \"B\", 50, ]\n" + | |
" [ \"B\", \"C\", 50, ]\n" + | |
" [ \"C\", \"D\", 50, ]\n" + | |
" [ \"D\", \"E\", 50, ]\n" + | |
"]\n" | |
run_print_test @circular_graph_edges, start, finish, expected | |
end | |
#Tests the addition to Hash that pops the key/value pair with the lowest value | |
def test_pop_lowest_value | |
hash = {} | |
hash["highestvalue"] = 100 | |
hash["smallestvalue"] = 0 | |
hash["middlevalue"] = 50 | |
expected = "smallestvalue" | |
actual, value = *hash.pop_lowest_value! | |
assert_equal expected, actual | |
end | |
################# | |
#Private Methods# | |
################# | |
private | |
#Given the parameters of the test and a set of edges, generates the graph and tests the unused edges are correct | |
def run_unused_edge_test edges, start, finish, expected | |
graph = Graph.new edges | |
graph.dijkstra start | |
graph.print_shortest_path finish | |
graph.print_unused_edges finish | |
actual = graph.unused_edges_as_array finish | |
assert_equal expected, actual | |
end | |
#Given the parameters of the test and a set of edges, generates the graph and tests the print methods are correct | |
def run_print_test edges, start, finish, expected | |
graph = nil | |
capture_console do #suppres the console chatter | |
graph = Graph.new edges | |
graph.dijkstra start | |
end | |
actual = capture_console do | |
graph.print_shortest_path finish | |
graph.print_unused_edges finish | |
end | |
assert_equal expected, actual | |
end | |
#Captures anything printed to the console during a method execution and returns it as a string. | |
#Takes a block, and for the duration of the execution of that block swaps the $stdout for a temp | |
#StringIO object. Can be used to suppress console chatter by wrapping an offending block. | |
# | |
#Returns whatever was captured by the temp StringIO as a String | |
def capture_console(&block) | |
stdout = $stdout | |
$stdout = temp = StringIO.new | |
begin | |
yield if block_given? | |
ensure | |
$stdout = stdout | |
end | |
temp.string | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment