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!

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:

Youtake 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:

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:

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

everyneighbourhood 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. 1986Sheesh, it seems this map is from 1986! But we’ve got all the information we need: What I’m seeing is that:

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

## 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:

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 Bullhornsare 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:## 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 Algorithmslibrary 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`

.Now, we'll close the route between Pigalle and China Town:

Finally we can run the “Neo4j Graph Algorithms” version of Djikstra’s algorithm:

## 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!