public
Last active — forked from newporta/gist:237354

  • Download Gist
gistfile1.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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
############
#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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.