ROCK ’N’ ROLL TRAFFIC ROUTING, WITH NEO4J, PART 2
Originally posted on November 28, 2018 by Jasper Blues in Saxeburg Series.
This post is the second 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.
Originally at Liberation Data, the series will be continued on Neo4j’s own developer relations space — thanks so much to Ljubica Lazarevic and my friends at Neo4j for editing & hosting.
THE STORY CONTINUES
I did plan on each of the Saxeburg Series having an accompanying short story, with Moongirl, and some new folks, who you will meet soon. Just like we had in the first installment.
Because, let’s face it, what could be more awesome than exploring graph algorithms, aided by a menagerie of colorful albeit possibly criminally minded side-kicks? Especially if we place our beloved fictional friends into a city that is so dysfunctional, chaotic and downright dangerous that their very survival (wait, he survived!?) depends on the formulas we employ on their behalf.
However, I’ve been working on a new open-source framework for you. Therefore I didn’t have the time to prepare a new chapter this week. Tell you what though: You take the leading role for this installment, and I’ll have a new chapter for you soon, okay?
LET’S BEGIN
In the last post we learned how to perform traffic routing with Neo4j.
We discovered that Neo4j is accessible. With nothing more than a graph model, Cypher and a little creative thinking we were able to solve a real-world problem.
We also observed that Neo4j provides us with a directed property graph model. This gave us a lot of flexibility. Having solved the question “What is the most expedient route between two points in a city?” we immediately asked a new one. (By the way, don’t you find that this is exactly what happens in the real world? Business requirements evolve). With a few tweaks to our model, we were able to re-route traffic in the event of a road closure.
Today we’ll optimize our solution with the help of Neo4j Graph Data Science Library. This library, as the name suggests, provides a range of Graph Data Science algorithms. It’s maintained and officially supported by Neo4j, with participation from the community.
We’ll be accessing the libraries using a feature of Neo4j called stored procedures. Stored procedures give us a way to call, from Cypher, routines that run on the graph. There’s a plethora of interesting open-source routines. It is also fun and easy to write your own. I will show you how to do that in a future post.
Just one of those libraries above would in fact, be enough to perform optimization today. However we’ll be making good use of both in subsequent posts. They’re both pretty interesting too, so let’s read on.
GETTING SET UP
You’ve got a number of options for getting Neo4j set up for this post. You can:
- Use Neo4j Sandbox Graph Data Science use case. It already has GDS installed, just remove the existing data set before you continue. This is the no download, no install route.
- Download and install Neo4j Desktop and use the Plugin helper to install GDS.
- Get set up on Neo4j using the server directly. If going down this route, you will need to manually install the GDS plugin. Make sure you’ve downloaded the right versions for the database you have installed. You will also need to grant access to the plugins in the neo4j.conf file.
You can test out what procedures you’ve got available to you with the following command:
call dbms.procedures()
WELCOME BACK TO SAXEBURG
Its good to have you back!
You awaken after a fitful night’s sleep in some nondescript hotel in Pigalle. The driver wanted to take you to Red Light, but you you insisted on the more civilized North-east quarter.
Nonetheless, it seems every neighbourhood in Saxeburg hoists their red lights come nightfall. In fact, one shone, like a tainted moonbeam, from across the street through your hotel-room window. Bereft of curtains, as it was. Barely after your eyes had closed it crept like tendrils through shuttered lids and sparked the technicolors of your mind. Lurid dreams followed. Such fantasies leave you nary rested, thus, the morning sun came as a shock, seemingly moments later. Truth be told, you wouldn’t have minded staying in your dream a little longer, and yet now daylight beckons.
COFFEE
Coffee fixes everything. And the coffee is good, surprisingly good!
Outside, eleven floors below, the world’s most unlikely urban eco-system hums, grinds and teems with life. The sidewalks are full. People spill onto the road. Traffic overflows onto the crumbling, tree-lined pavement. No space is wasted. Hawkers have set up what seems to be the world’s most popular street-food stall on a traffic-island. The smoke from their grills wafts and mixes with that belched by a packed ten peso passenger jeep. Said jeep hurtles past, then slams on the brakes, with a squeal.
Meanwhile, at the demolition site next door, stray dogs are playing a game of chase, leaping and tumbling among piles of concrete debris. Atop one: a life-sized, smiling statue of Buddha in pock-marked golden plastic. Suddenly, two dogs and Buddha collide, then all three are tumbling down the rubble-side. Buddha’s face is alight, as though laughing, but the dogs don’t seem to notice. They too are absorbed in the present moment, in their game.
STOP PEERING OUT THE WINDOW
Hey! Come on, finish your coffee. We’ve got work to do!
Showered, and dressed for the day, you’re greeted out of your hotel-room door by dim, flickering lights, in a windowless elevator well. The floor is scuffed. An ancient lounge that sits on the opposite side of the elevator doors is flanked by two pot plants. Although plastic, they display drooping, thirsty leaves that seem to be pushing the limits of survival.
You wonder at the special kind of neglect it must take to kill a plastic pot plant! Probably the kind that is comfortable to scrawl “Out of Service” using what appears to be red lipstick on a piece scrap paper. Undoubtedly, the type that would then stick it to the elevator door with spent chewing gum.
At least the air-con is still working. It is attacking the fecund heat, keeping it at bay with an acrid smelling air that is two parts squalid, and one part you-don’t-want-to-know.
You reach the lobby after an eleven floor stair descent. Behind the counter, a beautiful human with remarkably androgynous features and a dashing red uniform greets you with a heartfelt “Good Morning!”. That sing-song intonation. Damn, you love the Saxeburgian accent.
You feel a little awkward though, when you ask “How do you prefer to be addressed?”.
There is no sign of offense taken in the answer. “I prefer she”, she laughs warmly, and hands you a brochure (Moongirl and the Bullhorns Tour Dates) along with a map of Saxeburg.
You’re not wearing your mixed-reality goggles, and so “Actual paper!”, you think to yourself, “How quaint!”
ORIENTEERING
Let’s reorient ourselves and take a little squiz at our map:
Sheesh, it seems this map is from 1986! But we’ve got all the information we need: What I’m seeing is that:
- There are neighbourhoods. We are in Pigalle.
- There are routes between each of them, neighbourhoods, that is.
- Each route has an associated travel time or cost.
What we are dealing with here is a weighted graph.
WHAT IS A WEIGHTED GRAPH?
As we learned previously, graph structures have been considered since antiquity, with path-finding being a classical application thereof.
Not long after Euler came up with the first known graph, folks started to develop variants applicable to different avenues of exploration. For example, previously we saw that a graph can be directed or undirected.
A weighted graph, then, is a graph in which each edge is given a numerical value. These numbers are usually taken to be positive. The value that is attached to an edge is what gives the edge its weight. The weight can represent cost, distance, throughput or some other property.
PROPERTY GRAPH MODEL VS WEIGHTED GRAPH
Once again, we see that Neo4j’s property graph model is pretty versatile. Previously we explored how we can model graphs in which the relationships are bidirectional or undirected, even though, under the hood, all Neo4j relationship are directed. Do you remember?
Neo4j can happily serve as a weighted graph model too. There are various algorithms that deal with weighted graphs, probably the most famous of which is Djikstra’s. That’s what we’ll use for routing today.
DJIKSTRA’S ALGORITHM
Dijkstra came up with his algorithm in 1956, although it wasn’t published until three years later. At the time, he was trying to come up with something to show off the new ARMAC mainframes. Bear in mind that this was the dawn of the electronic computing age. One of the challenges was to find a problem and solution that people not familiar with computing would be able to understand. Thus he designed a solution for finding the most expedient route between two points in a road network.
Perhaps it is a little ironic, then. Although he wanted the algorithm to be accessible for the layperson, budding computer scientists find it one of the more intimidating algorithms to grasp.
Here’s what the man himself had to say.
IN HIS OWN WORDS
“What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city? It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice.”
– Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001
MY TAKE ON THAT
- There were only a handful of working programmers in the 1950s, however at least one of them was as enthusiastic about coffee as some of our modern comrades.
- Djikstra was a rock star developer. Nothing pleases a rock-star-dev more than his or her own mad skillz.
LET’S BEGIN, THIS TIME FOR REAL
We’re using the same graph as last time. Open your browser (either click ‘Open Browser’ on Neo4j Sandbox, ‘Open’ on Neo4j Desktop, or put localhost:7474 into your favorite browser )and run this statement.
To recap where we left off:
- We expressed our requirements (find the fastest route) in Cypher. It was a handful of lines of code.
- We found candidate routes between two required destinations, trusting that Neo4j’s Cypher would choose the most appropriate path finding algorithm for us.
- Using aggregation functions and ordering, we reduced that down to the best route.
This got the job done. When the requirements evolved we were able to update our Cypher to match too. Pretty handy.
MOST EXPEDIENT ROUTE
There are graph models and corresponding algorithms for specific classes of problems. One of which is Djikstra’s Algorithm, as discussed. It is an optimal solution, for finding the most expedient route on a weighted graph. The algorithm has a time complexity of O(|E| + |V| log|V|)
where V
is the number of nodes and E
is the number of edges (relationships).
Let’s get down to applying Djikstra’s algorithm with the Graph Data Science Library. By the way, if you would like to read about how the algorithm works, there are some excellent tutorials on that topic. We’ll see you back here when you’re done.
The brochure that Charm, from hotel reception, gave you this morning says that Moongirl and the Bullhorns are headlining at the Ruins tonight — an unplugged tribute to Doctor Cerulean. The concert starts at sunset. It is 5pm now. Let’s see if we can get you there on time:
MATCH (a:Metro {name: 'Pigalle'})
MATCH (b:Metro {name: 'The Ruins'})
CALL gds.alpha.shortestPath.stream({
nodeProjection: 'Metro',
relationshipProjection: {
HAS_ROUTE: {
type: 'HAS_ROUTE',
properties: 'travelTime',
orientation: 'UNDIRECTED'
}
},
startNode: a,
endNode: b,
relationshipWeightProperty: 'travelTime'
})
YIELD nodeId, cost
WITH gds.util.asNode(nodeId) AS nodes, cost
RETURN nodes, cost AS journeyTime
THE RESULTS:
Notice how our query returned two columns. The first is a path, containing nodes and relationships, so we have a visualization available:
We can travel to The Ruins via China Town, Intramuros, Uptown and Brooklyn.
We returned weight
, as journeyTime
. Switching to the table tab and looking at our final stop, The Ruins, we can see that journeyTime
is 29.5
minutes.
MOST EXPEDIENT ROUTE IF THERE ARE CLOSURES
Let’s solve the road closure problem. Previously, we entered all the Nodes we had to run Djikstra’s algorithm. This doesn’t account for road closures. We have to project a specific graph to be able to address these closures.
It turns out, we’ve already done a graph projection when we ran the last query, except that we projected the whole graph. What we can do is project a specific part of the graph we want to run the algorithm on, and to do that we’re going to use Cypher to help us.
First let’s ensure that each HAS_ROUTE
relationship has a status property, and reset that status to ACTIVE
.
MATCH ()-[r:HAS_ROUTE]-() SET r.status = 'ACTIVE'
Now, we’ll close the route between Pigalle and China Town:
MATCH (n:Metro {name: 'Pigalle'})-[r:HAS_ROUTE]-(m:Metro {name:'China Town'})
SET r.status = 'CLOSED'
Finally we can use Cypher in our GDS algorithm to account for open roads when using shortest path:
MATCH (a:Metro {name: 'Pigalle'})
MATCH (b:Metro {name: 'The Ruins'})
CALL gds.alpha.shortestPath.stream({
nodeQuery: 'MATCH (n:Metro) RETURN id(n) as id',
relationshipQuery:'MATCH (n:Metro)-[r:HAS_ROUTE]-(m:Metro) WHERE r.status <> "CLOSED" RETURN id(n) AS source, id(m) AS target, r.travelTime AS travelTime',
startNode: a,
endNode: b,
relationshipWeightProperty: 'travelTime'
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).name, cost
THE RESULTS:
A road closure between Pigalle and China Town would increase the journey time to 35 minutes.
CONCLUSION
Today we explored weighted graphs and Djikstra’s Algorithm with Neo4j. We discovered that Neo4j puts the power of graph algorithms at our fingertips. We also learned that we can project the property graph model to other graph models.
Please stay tuned for the next installment. 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!