Planning, Logistics and Operations: Modelling the London Tube Network in Grakn

James Fletcher
Jun 6, 2018 · 5 min read

We know Grakn can be leveraged to model highly complex data, but how do we go about building a detailed model of a real-world system?

Here we delve in to Transport for London (TFL) data to understand and gain insights into the operation of the London Underground Network.

We go on to build surely the most desirable tool for such a network: a journey planner. (Because who doesn’t want to shave 0.3 minutes off their commute?)

All of the code is written in Python and Graql, using the Grakn Python Client, and is available on GitHub.

The schema

In case you really want to get in deep with this example, you’ll need to know the schema that we’re using.

The Tube Network Schema. Boxes are entities, diamonds are relationships and ellipses are attributes.

The first thing you notice about this schema (source code) is that it’s compact, considering that it holds a fundamental representation of a whole transportation network.

The reason for this is that Graql is very expressive, allowing us to quickly interrelate concepts that we are already familiar with. More on how to design an intuitive schema in an upcoming blog post.

What does Grakn give us?

Let’s dive straight in to show how short Graql queries can reason to answer questions that would be strenuous to achieve with any other system.

Maybe we want to know the points where we can change to another line as a shortcut. So we have a question such as:

“Which stations are common to the Piccadilly and Victoria lines?”

Answer: Finsbury Park, King’s Cross St. Pancras, Green Park

If we’re an employee at TFL analysing the tube, we might want to find discrepancies in the timetable data. Specifically we might look for tube lines that are predicted to take different amounts of time between the same 2 stations. This might indicate a problem with one line compared to another.

We find that there are many points on the network where this occurs. For example, from Notting Hill Gate to High Street Kensington takes 1 minute less for the Circle line than it does the District line. (Although this may not surprise you…)

Journey Planner

We can use Grakn to build rich applications, leveraging Grakn at runtime for database queries. This tool is available in the repo at visualisation/app.py

Geographic map of the tube network, with live interaction from the backend Knowledge Graph

The map is built by querying for the latitude and longitude of each station, and querying for tunnels that interconnect pairs of stations. Then we ask for the tube lines that pass through a tunnel, in order to render a coloured line for each tube-line.

You can see that although Grakn is storing complex data in a complex structure, it is quite straightforward to generate a simplified representation similar to the map issued by TFL.

Centrality of stations, by degree. Score indicated by the relative circle radii.

Centrality

Once we have the map, we can use Grakn’s distributed analytics to glean, by a certain metric, the most inter-connected stations. (For a deep dive into analytics, see Jason’s blog post.)

Very useful for research for when you realise your neighbour/flatmate is unbearable and you need to move somewhere well-connected in a hurry.

With the map running press d to see, infographic style, the number of other stations each station is directly connected to.

Clear winners are stations such as King’s Cross St. Pancras, Baker Street and Oxford Circus. There are several other methods available in Grakn to measure centrality. To query for this in Grakn is as simple as:

compute centrality of station, in [station, tunnel], using degree;

Shortest Path for Journey Planning

This app also uses Grakn to let a user visualise the shortest number of stops to get from A to B.

Shortest number of stations from Green Park to Temple, indicated by the dashed train tracks.

It’s as simple as shift+clicking on the start and end stations. The Python app finds the ids of the stations and asks Grakn:

compute path from "V90192", to "V1191984", in [station, tunnel];
Two equal-length paths from Green Park to Goodge Street

It doesn’t stop there, because clearly there may be more than one way to get make a journey in the same number of stops. Grakn returns all of them, and the app plots them all.

This way, akin to Citymapper, the user can find a variety of options, one of which might be more beneficial for them in their circumstance.

What about from A to B to C?

Shopping at Oxford Circus before you head to King’s Cross St. Pancras for your Cambridge train?

Easy, just shift-click on a third station to add the path from B to C to the map.

From Waterloo to Oxford Circus, then onwards to King’s Cross St. Pancras via either of two options.

Your Graknable Ideas

Hopefully this use-case has given you some new thoughts on how to use Grakn to power your own projects, whether or not they’re more glamorous than the tube network.

Feel free to get in touch me on james at grakn dot ai to tell us about your project, including how we can help you to accomplish your mission via new features, support or advice. Don’t forget to join our Community Slack channel, or via our discussion forum.

Of course, be sure to check out the code as a Python basis for your own ideas.

Find out more from https://grakn.ai.

Vaticle

Creators of TypeDB and TypeQL