Skip to content

@newporta /gist:237354
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
############
#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
Something went wrong with that request. Please try again.