Travelling with graphs : from konigsberg to the paris subway

The classical problem of the graph theory was framed by Leonhard Euler. He wanted to know whether someone could visit the city of Königsberg without crossing twice any of its 7 bridges. This little brainteaser for mathematicians inspired Euler with creating the concept of “graph”. The concept itself is abstract but graph theory has many concrete applications.

Graphs are very useful to think about physical networks for example. Have you looked at a map of Paris’ subway? It looks a bit like a spaghetti plate but it is also a graph. It is made of subway stations (nodes) which are linked together by rail tracks (relationships).

What does it mean though? If you model this network as a graph, it becomes easier to analyse it. Simply by modeling the relationships between the subway stations and adding the distance between them, we can :

• calculate the shortest path between point A and point B ;
• find alternative routes if a given node (a subway station) is removed from the network ;
• find the route from point A to point B that minimizes transfers ;
• etc…
  
  

These are all basic questions that a graph model representing a physical network can answer. Writing and performing these queries is very fast, even if your network is large and complicated.

What’s interesting is that we can enrich our graph model of Paris subway to add more information. We can for example add statistics about the occupancy of subway lines or the position of cultural landmarks. This way we can make sure when we plan a trip that avoids the over-crowded lines while hitting the major cultural landmarks.

On the Neo4j GraphGists website you can find concrete examples of communication networks modeled as graphs. Neo4j GraphGists are a way to share documents including Cypher queries. Here are few interesting examples :

• Roads, Nodes and Automobiles or How a sat-nav could use a graph database
• Asturias Highway network
• Bombay Railway Routes

The next time you will travel, think about the graph you are exploring!