This is a ruby script that finds the best path between two arbitrary London underground stations.
The underground is represented by an undirected graph structure. The best path is found using the Dijstra algorithm.
Stations are linked between each other with edges of weight 1. If there are stations that span multiple lines, an edge of weight 1 is drawn between all of them.
There are three classes used in the script.
- Graph: Data structure responsible for storing the tube stations in a graph. Implements the Dijstra algorithm for finding the best path between two nodes in the graph.
- TubeParser: Helper class which parses a text file (of the London underground stations) and creates a Graph object with the extracted information.
- Shell: Object responsible for parsing user commands and displaying messages to the console.
The source code and file containing the station names and lines can be found here.
#!/usr/bin/env ruby
# Author: Carlos Garcia
# Generic undirected graph which stores information about nodes, edges
# ... and the weight associated with each edge.
class Graph
# Constructor
def initialize
# The graph
# Format: {node => { edge1 => weight, edge2 => weight, ...}, node2 => ...}
@g = {}
# Array of individual nodes.
@nodes = Array.new
# The maximum length a node can have.
@Inf = 1 << 64
end
# Add a new set of edges and nodes into the graph.
def addEdge(source,target,weight)
# Have we added a source and target before?
if (not @g.has_key?(source))
@g[source] = {target=>weight}
else
@g[source][target] = weight
end
# This makes the graph non-directed. Reverse the direction of source and target
if (not @g.has_key?(target))
@g[target] = {source=>weight}
else
@g[target][source] = weight
end
# Store the included nodes for posterity's sake.
if (not @nodes.include?(source))
@nodes << source
end
if (not @nodes.include?(target))
@nodes << target
end
end
# Based on the algorithm in http://en.wikipedia.org/wiki/Dijkstra's_algorithm
def dijkstra(source, target)
# Distances from the source to any other node.
@distance = {}
@prev = {}
@nodes.each do |node|
@distance[node] = @Inf
@prev[node] = -1
end
# Initial distance from the source node to itself.
@distance[source] = 0
# Set of nodes yet to be processed.
dirty_nodes = @nodes.compact
while (dirty_nodes.size > 0)
# Find the closest node from the source in @distance.
closest_node = nil;
dirty_nodes.each do |node|
if (not closest_node) or (@distance[node] and @distance[node] < @distance[closest_node])
closest_node = node
end
end
if (@distance[closest_node] == @Inf)
# Remaining nodes are inaccessible.
break
end
# Have we reached our target?
if closest_node == target
# Get out of here, we have a solution.
break
end
dirty_nodes = dirty_nodes - [closest_node]
@g[closest_node].keys.each do |destination|
total_distance = @distance[closest_node] + @g[closest_node][destination]
if (total_distance < @distance[destination])
@distance[destination] = total_distance
@prev[destination] = closest_node
end
end
end
end
# Obtain the path from source to target (only after computing Dijkstra).
def getPath(source, target)
path = []
current_node = target
# Find the path to the target by following backwards the best route.
while @prev[current_node] != -1
path.insert(0, current_node)
current_node = @prev[current_node]
end
path.insert(0, current_node)
return path
end
def findNodes(node_name)
# Find all nodes that start with node_name.
return @nodes.grep(/^#{Regexp.quote(node_name)}\$/)
end
end
# Parses a text file of underground stations into a Graph object.
class TubeParser
# Constructor
def initialize(file_name)
# File containing the underground info.
@file_name = file_name
# All the lines a particular station belongs to.
@station_lines = Hash.new
# The yet to be graph of the london underground.
@tube_graph = Graph.new
end
def parse
file = File.open(@file_name, 'r')
# Parse each line of the file.
file.each do |line|
# Match a regular expression to get the nodes and their connections.
match = line.scan(/\((.+),(.+),(.+)\)/)[0]
# Was this a valid line?
if match == nil
# Invalid line, go to the next one.
next
end
source = match[0].strip.downcase
destination = match[1].strip.downcase
tube_line = match[2].strip.downcase
# Add the tube_line to the source station.
addLineToStation(source, tube_line)
# Add the source node with an edge to the destination with a weight of 1.
@tube_graph.addEdge("#{source}$#{tube_line}", "#{destination}$#{tube_line}", 1);
end
# Create the nodes for the lines and stations.
connectLinesAndStations()
# Return the generated graph.
return @tube_graph
end
def addLineToStation(station, line)
# Store the lines a particular station belongs to.
if @station_lines.key?(station) == false
# Create the array where we store the tube lines.
@station_lines[station] = Array.new
end
# Add the station to the list of stations without duplicates.
@station_lines[station] = @station_lines[station] | [line]
end
def connectLinesAndStations()
# Create a fully connected subgraph of stations and the lines so that
# ... we can represent changing lines.
# Iterate over all stations (stations).
@station_lines.each do |station, lines|
# Iterate over all lines but the last one.
for i in 0...lines.size-1
# Connect the line i with all the other lines (including the last one).
for j in (i+1)...lines.size
@tube_graph.addEdge("#{station}$#{lines[i]}", "#{station}$#{lines[j]}", 1)
end
end
end
end
end
# The basic shell interface that parses the user input.
class Shell
attr_accessor :source_station
attr_accessor :target_station
# Constructor
def initialize
@source_station = ''
@target_station = ''
# Flag: is the user input valid?
@valid_input = false
end
def getUserInput
print "\n\nIndicate a pair of stations separated by commas (quit with 'q'): \n >> "
$stdout.flush
input = gets
# Shall we quit?
if input.strip == 'q'
@valid_input = true
return true
end
# Was the input valid?
match = input.scan(/^([\w\s]+),([\w\s]+)$/)[0]
if match == nil
# Input was not valid.
print "\nError 1:: The supplied stations are not valid. "
$stdout.flush
@valid_input = false
return false
end
# The input seems valid (lower case and replace spaces).
@source_station = match[0].strip.downcase.gsub(/\s/,'_')
@target_station = match[1].strip.downcase.gsub(/\s/,'_')
@valid_input = true
# Do not quit yet.
return false
end
def validInput?
return @valid_input
end
# Print a friendly message telling the user the supplied input was
# ... not valid.
def illegalInput
print "\nError 2:: The stations could not be found in the map. "
print "Try with different ones or check your spelling. "
$stdout.flush
end
# Print the defined route to the user (without repetitions).
def printRoute(route)
# puts "Debug:: " << route.join(', ')
# Remove the underground lines from the station names.
route.map! {|node| node.split('$').first}
# Remove duplicates.
route.uniq!
# Capitalize and replace underscore with space.
route.map! {|x| x.split('_').map(&:capitalize).join(' ')}
# Print the route joining them with commas.
print ' ** '
print route.join(', ')
$stdout.flush
end
end
if __FILE__ == $0
# Create the parser that constructs the graph of the underground.
tube_parser = TubeParser.new("tube_edges.txt")
# Perform the actual parsing.
london_tube_graph = tube_parser.parse()
# Instantiate the interpreter that will parse the user input.
shell = Shell.new
while true
# Ask the user for input
quit = shell.getUserInput()
if quit
# The user doesn't want to play anymore; quit.
break
end
# Was the input valid?
if not shell.validInput?
# We skip this iteration. (Instead of terminating the program)
next
end
# The user input.
source_input = shell.source_station
target_input = shell.target_station
# Find nodes that match the user selection
source_stations = london_tube_graph.findNodes(source_input)
target_stations = london_tube_graph.findNodes(target_input)
# Does the supplied stations exist?
if source_stations.size == 0 or target_stations.size == 0
# They don't exist.
shell.illegalInput()
next
end
# Calculate distance from a source station to the target station.
# ... Select the underground line randomly.
source = source_stations[rand(source_stations.size)]
target = target_stations[rand(target_stations.size)]
# Perform the Dijkstra search.
london_tube_graph.dijkstra(source, target)
# Obtain the route.
best_route = london_tube_graph.getPath(source, target)
# Print he route to the user.
shell.printRoute(best_route)
end
end