Journey Planner Implementation
This document envisages the creation of a computer software application which enables a user to identify the shortest route between two given stations on the London Underground system. The application itself, is to be written in the Ruby scripting language and the schema of the Underground is to be stored on a MySQL database. In order to be effective, the application would provide an implementation of Dijkstra’s shortest path algorithm . An initial prototype of the application would be a console based application i.e. a non-gui style application. This could be further developed into a graphical user interface (gui) application or possibly even a web-based application. The application should also provide administrative options to backup and restore the database, and make use of MySQL scripts to create and populate the database schema.
Rationale behind software choices
Ruby was selected as the main scripting language because the problem space maps well to real life objects and Ruby is highly object oriented. A solution to the shortest path algorithm will spend its time scanning ‘Nodes’ in our case Tube line stations, and ‘Edges’ a connection between two adjacent stations. Ruby should make easy work of applying Dijkstra’s algorithm to generate code. MySQL was selected as the target database because MySQL is open source, readily available and works well in tandem with Ruby.
Environment and Project Design
The project would be created on the Linux distribution Ubuntu and should make use of modern design practises such as entity relationship diagram modelling for the database schema. The application itself should be object oriented and be designed with the aid of The Unified Modelling Language (UML). Specifically, Use case diagrams, class diagrams, and sequence diagrams should be produced prior to the production of actual Ruby code. Again following best practises, the Ruby script itself should be developed as part of a test driven development approach (TDD). Here ‘rpec’ is the testing framework of choice.
The London Underground comprises 270 stations, reference: http://en.wikipedia.org/wiki/London_underground
Any algorithm attempting to calculate multiple routes of a network with so many nodes could be dealing with a staggering number of permutations. Previous software writers attempting to process the London underground with their own algorithms may encounter two issues. Firstly that ill-thought out solutions exhaust the computer’s memory. Secondly, their approach takes an unacceptable time to process the full number of combinations possible for a given journey. For this reason, it was felt preferable to employ an existing algorithm that is proven. Examples of existing shortest path algorithms include Dijkstra’s, the Bellman-Ford algorithm, and the A* algorithm. Dijkstra’s algorithm is popular and well utilized in route planning software, and was therefore selected.