-
-
Save RLGGHC/239937 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
############ | |
#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