ROCK 'n' ROLL TRAFFIC ROUTING, WITH NEO4J

This post is the first of my #saxeburg-series, for young entrepreneurs (or the young at heart), in which we’ll learn about Neo4j and have some fun at the same time. How? By building our own Neo4j-powered mobile game.

LET’S BEGIN

Have you ever wondered how apps like Google Maps or Waze provide turn by turn directions and offer the fastest route, as well as respond to changing traffic conditions in realtime?

Today I will show you how to use Neo4j for traffic routing, and it will only take a few minutes.

As you will soon see, we could pick any city that we like as a case study, however for the sake of this article let us imagine a sprawling nation-state that is part Paris, part Metro Manila and part Coney Island. Are you with me?

Such a city could be represented in topographical form like this:

Saxeburg, c. 1986

Towards the task at hand let us also imagine Dr Cerulean, the charismatic founding forefather of our thriving metropolis. Charisma aside, he is unfortunately a calamitously lazy man and one prone to numerous vices at that. Most especially wine, women and song.

We are going somewhere with this, but I would ask that you please stretch your imagination just a little more, to accommodate the following notion: On the night before he was due to present an inaugural city charter, our dear Doctor was in Phoenix sampling the Cactus Juice, which is very good down that way. And unfortunately also lethal on this occasion.

THE LAST DAY OF DOCTOR CERULEANN’S LIFE

OK, so here we are on the last day of our city founding father’s last day of life. We will get to the traffic routing in a moment, but I think we better address this matter at least briefly, as it would be disrespectful to brush over, wouldn’t it?

Doctor Cerulean commenced his last day, after waking from an hour or two of sleep. He discovered himself in a compromising position, but was otherwise feeling quite fantastic. Violently alive, you could say. The city charter, however was nowhere in site, the task of preparing one having been neglected for months prior.

You might think this sounds like the start of a day where things aren’t going to go necessarily all that well, and you’d be right.

However, at this point, I can elaborate on some of the soon-to-be departed Doctor’s redeeming qualities. For one, he is deliciously playful. Two, he’s remarkably resourceful and quite inventive to boot.

You see, the night prior, there was a fantastic party taking place in the science department of Phoenix’ very party-oriented fledgling university campus. Thus, the Doctor found himself, that morning, regaining some semblance of consciousness drooling onto a Periodic Table of Elements.

Having awoken at ten, and due to present the city charter at eleven, our Doctor performed a momentous feat. He gathered up the table of elements, crossed out the carbon; nitrogen; phosphorus; oxygen; sulphur; selenium various noble gasses and so forth until there was nothing left but what? Exactly: metal. On top of this, he scrawled, in black marker pen: “The People Will Rock!”.

And so, this is the document he presented in lieu of an actual city charter, in front of the assembled town hall, and those were in fact the last words he uttered. They were spoken with enthusiasm and with arm held aloft, fingers formed into a pair of horns.

He then promptly collapsed and died, on stage, making quite a show of it.

The doctors (actual qualified ones) wrote “general congestion in all systems”, which was a polite way of saying “excess of Cactus Juice”, back in those days.

DON’T CRY

Finally, here ready to commence our traffic routing exercise! Woo hoo! However, hmmmm . . . now I’m a little worried about you.

Maybe this story of Doctor Cerulean, has moved you. Rocked your emotional core, so to speak. Perhaps even to the point of overcoming your powers of cognition. The thing is, you are going to need those.

Therefore I would say to you this: Do not shed a tear! The good Doctor’s statue stands aloft in Intramuros to this day. He is looking very dapper, albeit simultaneously a little worse for wear. His arm is raised, just as it was in those last moments, in an ever enduring veneration of metal and hard-living.

Meanwhile Saxeburg is thriving, it really is. And I tell you what, the people certainly did rock! Every neighbourhood adopted an elemental metal, enshrined it with a stage and auditorium with standing area for thousands. There are full light-show capabilities (on days that the town’s electricity supply is functioning), you name it.

MOONGIRL AND THE BULLHORNS

Now, the show is on the road. Ladies and gentlemen, I would like to welcome you to present-day Saxeburg, and introduce you to Moo-oooonngirl and the Bullhorns! (Moongirl, please take a bow).

Moongirl is the nubile lead singer of Saxeburg’s premier Rock and Roll show and the Bullhorns are the tightest backing band in the business. A dashing bunch of brutes too.

Moongirl and her band put on a show every night of the year, and they love what they do. There is only one problem.

The traffic in Saxeburg is bloody terrible!

LET’S BEGIN, THIS TIME FOR REAL

Moongirl has been spending the day at the beach, with her boys. Meanwhile she is head-lining at the Grand Théâtre de Rabat in NYC tonight. Let’s see if we can get her to the gig on time.

I’m assuming you have an instance of Neo4j running on your machine. If you don’t go google that and we’ll regroup here.

DATA INGESTION

Open your browser at localhost:7474 and run this statement.

Now run:

match (n) return n;

This yields a graph that will look something like this:

The first thing that you might notice is that it looks nothing like our topographical map. So what gives?

GRAPH THEORY

Well, you probably know that graph databases are based on a branch of mathematics, in the field of combinatorics called graph theory; that in fact graph theory itself emerged from an exercise in path-finding:

Euler’s solution of the Königsberg bridge problem is considered to be the first theorem of graph theory and the first true proof in the theory of networks. Additionally Euler recognised that the key information was the number of bridges and the list of their endpoints rather than their exact positions.

So there’s that.

MORE GRAPH THEORY

But it is quite a rabbit hole, actually.

While combinatorial problems have been considered since antiquity and graph theory emerged some three hundred years ago, network structures remain an area of research interest to this day.

Meanwhile the practical ramifications are endless. Some examples of applied graph theory are:

Recommendation engines
Root cause analysis
Fraud Detection

Something that makes Neo4j so compelling is that it puts graph algorithms for real-time transactional data at your fingertips.

In fact later in this series we will be applying graph theory to solve a crime. Or maybe (shocking thought) to get away with one. Which will it be?

Of course this is a suspenseful blog series so you’ll have to wait. In the meantime our sassy urbanite is starting to get tetchy about being late for her gig, so we’d better press on!

BIDIRECTIONAL RELATIONSHIPS

Something else that you might notice is that the HAS_ROUTE relationships are directional - we can see this on the visualisation, because, well, they have arrows on one end.

However, we have actually modelled Saxeburg as an undirected graph. But, all relationships in Neo4j are directed.

So what is happening here? Well, the CYPHER query language allows us to ignore direction when it is not relevant. You can see an example of that on the merge statements to create those HAS_ROUTE relationships, and we’ll employ it again in a moment.

EXPLORING ROUTES

Let’s run the following CYPHER:

MATCH (n:Metro)-[r:HAS_ROUTE]-(m:Metro)
RETURN n.name, r.travelTime, m.name LIMIT 5;

This yields the following results:

We can see that each Metro has a route to various other metros, and that the average travel time has been recorded.

MOST EXPEDIENT ROUTE

Using the information at hand, we can now easily find the most expedient route from Cavite Island to NYC:

MATCH paths = (a:Metro {name: 'Cavite Island'})-[:HAS_ROUTE*1..6]-(b:Metro {name: 'NYC'})
WITH paths, relationships(paths) AS rels
UNWIND rels AS rel
WITH paths, collect(rel.travelTime) AS streets, sum(rel.travelTime) AS travelTime
RETURN extract (n IN nodes(paths) | n.name) AS metros, streets, travelTime ORDER BY travelTime;

This query tells us the following:

Moongirl will get to her gig on time - she can reach NYC in 26 minutes.
She can wave at Doctor Cerulean’s statue on the way - the fastest route is via Intramuros and China Town.

ROAD CLOSURES

Let’s expand our model to handle road closures.

MATCH (:Metro)-[r:HAS_ROUTE]-(:Metro)
SET r.status = 'ACTIVE';

The citizens of Saxeburg decide to throw their television sets out of their windows. It causes road closures between China Town and Ermita, and also between Intramuros and China Town.

MATCH (:Metro {name:'China Town'})-[r1:HAS_ROUTE]-(m:Metro {name: 'Ermita'})
WITH r1
MATCH (:Metro {name:'Intramuros'})-[r2:HAS_ROUTE]-(m:Metro {name: 'China Town'})
SET r1.status = 'CLOSED'
SET r2.status = 'CLOSED';

Now we can extend our initial query as follows:

MATCH paths = (a:Metro {name: 'Cavite Island'})-[:HAS_ROUTE*1..6]-(b:Metro {name: 'NYC'})
WITH paths, relationships(paths) AS rels where all(rel IN rels WHERE rel.status = 'ACTIVE')
UNWIND rels AS rel
WITH paths, collect(rel.travelTime) AS streets, sum(rel.travelTime) AS travelTime
RETURN extract (n IN nodes(paths) | n.name) AS metros, streets, travelTime ORDER BY travelTime;

We can see that:

Travel time increases 29.6 minutes
The best route is now via Intramuros, St Germain and China Town.

CONCLUSION

Today we learned how to use Neo4j to perform traffic routing.

There is a lot more that we could do, however I would like you to think about it, and see where it leads you. How would you extend the model? Maybe handling delays? Turn by turn directions? What about performance concerns with much larger datasets?

Have a try for yourself and tweet your discoveries to @doctor_cerulean hashtag #doctor-cerulean-liberates-your-data.

We also learned today that:

Neo4j is accessible. We can analyse network structures and solve real-world problems, without necessarily needing to know a lot about graph theory or combinatorics.
Network structures have tremendous plasticity. We can enhance our model to encompass evolving requirements. And because Neo4j is transactional we can be assured of data consistency for large-scale, fluid networks. This is a powerful combination. In fact it makes Neo4j compelling for AI applications. We will explore that, with Moongirl, in a future post.

Please stay tuned for the next instalment. I hope that you enjoyed this one! If you did, why not tell your friends about the fun that can be had when #doctor-cerulean-liberates-your-data.

Thanks a lot!