Q3. A classic but interesting to write program: Write a Java program to find the route between any
two stations on the London Underground network (and now London Overground). The user should
be able to select a start and destination station and the program then finds the route between
them, printing out travel instructions such as which line to take, where to change lines, and so on.
The data describing the network should be stored in one or more files, and read when the program
is run.
Of course I hadn’t reckoned on how hard it would be.
First off, I hadn’t previously considered the nature of a graph data structure.
A graph (in computer science) is a collection of nodes and edges. Nodes in my case represent stations. Each node has a set of items called edges. Edges represent the links between the nodes, in a way that reflects the true inter-connectedness of the tube network.
Each edge comes with three parts to it. There’s the name of the starting node, the name of the endpoint node (on the other end), and the name of the line that the edge is describing.
So you see, a working route finder is very dependent on having the right data available.
First off I had to get my data in manageable format. I extracted the data, and organized it in such a way as to make it useable. I used this data to create what is know as an ‘adjacency list’. This special type of list contains information about the entire network using a Hash Map. The use of a Hash Map helped in improving the efficiency of the adjacency list as it meant avoiding a full traversal to locate items within it. This aspect was very important.
One key reason for creating the Breadth First Search.
The Breadth First Search algorithm (BFS) is, unlike its counter part Depth First, useful in traversing adjacency lists that do not include any weighted edge data. My data only represented the nodes and not the distance between them.
If I’d had distance data then I would have used Dijkstra’s algorithm or possibly A* to do the traversing.
So I spent some time mulling over just how I was going to get back the shortest path for any two stops. It was hard work and involved several re-writes to get it.
The real breakthrough was in understanding the nature of tree traversal. Although the breadth-first algorithm is designed to traverse a graph of any shape, the resulting path it makes is one involving all sibling nodes on any given level. Therefore I had to track which level the search was at in the tree.
Knowing this meant I could then retrace the steps from which I had come, because the parent of any node was any node that was exactly one level less than the current. I was then able to create a list of all stations visited (in reverse order). So, finished by flipping those round and the output is there including all stations and lines involved. ☺
Please take a look over the code I wrote to see what you think.
Here's the whole class file with everything including data and simple UI for compilation. Please note the package name as it might cause problems.
