Journey planning by adam cowley

[fraboi87]

I watched the video by adam cowley

Neo4j Graph Database Platform – 21 Nov 18

Journey Planning... And Why I Love Cypher

Discover how Neo4j's graph database query language, Cypher, was used to create a reliable journey-planning tool for UK travelers.

explaining how to design a path-planner in Neo4j. However I am missing different details such as what is a Leg node? What does it represent? The graph and query he uses are very complex and require more detail: is there any reference?

[adam_cowley]

Hey @fraboi87,

This was a long time ago but I've worked on a project in the last few weeks that used a very similar process. Essentially you want to traverse through a path of valid nodes to get from one node to another.

In this example, you had :Stop or :Station nodes that were the starting point of a traversal. You'd find the best starting points based in the user's location (for example, the closest bus stop to the office). From there you would traverse through until you can alight a :Service (ie 09:00 from London Paddington on 30 July) at a :Leg.

Legs are individual segments of a service which go from one place to another - in this case a train journey from Bristol to London would take the route Bristol > Bath > Chippenham > Swindon > Didcot Parkway > Reading > London Paddington.

You'd then stay on a Leg for as long as possible (traversing through the -[:NEXT_LEG]-> relationships until you reach a platform at your destination.

The downside to using Cypher in this approach is that it would first need to traverse all paths before you could filter the results. The Traversal framework gives you greater control on what you expand, so you don't traverse off in the wrong direction.

I only had 10 minutes for the talk so I couldn't go into too much detail.

Max De Marzi has some great examples on how to use the traversal framework:

• Calculating the Best Rail Road paths in Neo4j
• Modeling Airline Flights in Neo4j

I hope that helps. What are you trying to build?

[fraboi87]

Hi thank you for your reply. The presentation was great. I will look into the links. I am trying to do something similar to what you have already done but for buses only. I came across your project and was looking to having further details, especially for the very complex query explained in the presentation

Just one question though: in the query when you do

size(legs)

What is legs? is it the collection of all the nodes in your path?

[adam_cowley]

Yeah that's right, I don't have the exact query to hand right now but for a single service it'd be something like:

// From a start node, find all of the possible legs
MATCH (startLocationNode)-[:CAN_BOARD]->(first:Leg)
WHERE /* Some sort of time criteria */
MATCH path = (first)-[:NEXT_LEG*1..100]->(end:Left) WHERE (end)-[:CAN_ALIGHT]-> (endLocationNode)
WITH nodes(path) AS legs // [ Leg1, Leg2, Leg3 ]

You traverse along the path of :NEXT_NODE relationships until you end up at a :Leg node where you can alight to the end location. In the final query I traversed through many relationship types.

Max's blog posts will help though, they show some really useful tips for modelling and performance. You could probably run it in a single cypher query if you spent enough time tunig the model.