ROCK 'n' ROLL TRAFFIC ROUTING, WITH NEO4J, PART 2

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.

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 two libraries:

Neo4j APOC. APOC is a bonanza of useful procedures and functions. This library is developed, maintained and supported by a very active community. Progress is rapid, and sometimes subject to change.
Neo4j Graph Algorithms. Whereas APOC contains graph algorithms along with utilities and functions, this library, as the name suggests is just algorithms. Its 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.

INSTALLATION

The first task at hand will be to install the aforementioned routines. I’m not sure when you’ll be reading this, but today the current version of Neo4j is 3.5.0. Here’s a link for Neo4j-apoc-3.5.0-beta01 and version 3.5.0.1 of graph algorithms.

Be sure to download the version that matches your Neo4j version - this is important - then copy the jar files into your Neo4j install’s plugins directory.

Now we can test that the procedures were correctly installed:

call dbms.procedures()

After installation, you’ll see the algo.* and apoc.* procedures listed.

GRANTING ACCESS

We’ve still got one step. Before we can use the procedures, we need to grant execution privileges to run inside Neoj. Edit your neo4j.conf file, adding the following line:

dbms.security.procedures.unrestricted=algo.*,apoc.*

We granted access to all procedures in each library. If we wished, we could be more specific.

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 grill 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. Undoubtably 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 offence 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:

Saxeburg, c. 1986

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 last week, 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, they started to develop variants applicable to different avenues of exploration. For example, last week 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.

A weighted graph.

PROPERTY GRAPH MODEL VS WEIGHTED GRAPH

Once again, we see that Neo4j’s property graph model is pretty versatile. Last week 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 week. Open your browser at localhost:7474 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 planner 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, WITH APOC

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 APOC. 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 apoc.algo.dijkstra(a, b, 'HAS_ROUTE', 'travelTime')
YIELD path, weight
RETURN path, weight 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, we can see that journeyTime is 29.5 minutes.

MOST EXPEDIENT ROUTE, WITH GRAPH ALGORITHMS

Let’s solve the road closure problem. Djikstra’s algorithm doesn’t account for this directly. We have to project a graph for it to operate on. We can do that using a combination of features in Neo4j APOC. However the implementation provided by the Neo4j Graph Algorithms library has a projection feature built in to the method signature, so we can do it in one step.

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 run the “Neo4j Graph Algorithms” version of Djikstra’s algorithm:

MATCH (a:Metro {name: 'Pigalle'})
MATCH (b:Metro {name: 'The Ruins'})
CALL algo.shortestPath.stream(a, b, 'travelTime', { direction: 'BOTH', 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 weight', graph:'cypher'
})
YIELD nodeId, cost
RETURN algo.getNodeById(nodeId).name AS 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!