The London Underground network, or any metro system for that matter, is an excellent way of explaining pathfinding. In fact, it is often used in company interviews as a way of testing the candidate’s knowledge of graph data structures and shortest path algorithms.
For my end-of-year mathematics video presentation project entitled “Finding Routes in Networks” I chose to use the London Underground as a visual aid in explaining shortest path algorithms such as BFS, DFS, Dijkstra and A*. I recommend watching the video first before reading my explanations on how I created the animations.
Turning the tube map into an SVG
The tube map is available as a PDF from TfL’s website, in very good resolution. In fact, I assume it must have been made in Illustrator or some similar vector graphics software because conversion from PDF into Inkscape SVG format proved to be easy.
After removing lines on the tube map that are not tube lines, that is Thameslink, Crossrail, Trams, Overground and the cable car, as well as ferry terminals and national rail interchange symbols, I proceeded to individually select every station name and corresponding blob, grouping them together and assigning a unique ID.
With the SVG map ready and imported into Python, a simple XPath gets us a reference to any station on the map.
//*[name()='svg'] part is necessary, otherwise
lxml does not recognise the
svg root element and returns no matches.
Importing the tube network as a graph
I used the NetworkX library, which one could argue is completely overkill for a project like this. On the other hand, this is a maths project and not a graph data structure implementation exercise.
Thanks to this FOI request I was able to get a nice XLSX file with all the stations and the travel time between them. I slimmed this down to a CSV file with only relevant information and imported it as a weighted directed graph using NetworkX. Since journey times vary depending on time of day, I took the inter-peak travel times (off-peak in the middle of the day, usually somewhere between 10am and 4pm) as the truth.
I used NetworkX to visualise the graph. No line colours, no layout: just the stations and how they are linked.
Animating pathfinding algorithms
Although NetworkX provides a smörgåsbord of shortest path algorithms, since during their execution I wanted to have custom code to hide / show stations, I had to roll my own.
Initially all stations’ visibility is set to
hidden. For each station visited, the algorithm changes the SVG’s grouped station element with the relevant ID to
visible. Once the shortest path is found, all visited stations are dimmed and as the algorithm retraces its steps, it returns those stations that are on the path to full opacity.
For each of the changes to the SVG described above, a copy of the SVG file is made, thus generating a frame. It amounts to one frame per station plus some more for displaying the shortest path. FFMPEG, if compiled with SVG support (and usually it is) can natively take in the SVG ‘frames’ and output them into an video format.
ffmpeg -r 10 -i out/frames/%05d.svg -vf format=yuv420p out/animation.mp4
And that’s it! Of course this process involved plenty of research on the internet and the sources are too many to feasibly list here (hint: stackoverflow was of good help). All my source code for the project is available on GitHub.