Visualizing shortest paths with neomap ≥ 0.4.0 and the Neo4j Graph Data Science plugin

Estelle Scifo
Feb 27, 2020 · 5 min read
Image for post
Image for post

A new version of neomap was released on 27th February (version 0.4.0). It brings a few new features:

  • Support for Neo4j-spatial simple point layers
  • Save/Open existing project
  • Draw polylines
  • Better handling of large datasets

See the ChangeLog for more details.

In the meantime, the Neo4j Graph Algorithm library is being replaced by the Graph Data Science (GDS) plugin. In this post, we are going to see how neomap can be used together with this new library to visualize shortest paths through some London streets.

The data

In this example, we are going to use a subset of the London streets graph extracted from OpenStreetMap (OSM).

In order to do this extraction, we can use the awesome osmnx python package. With only three line of codes, we can get a graphml file compatible with Neo4j:

import osmnx as ox
G = ox.graph_from_point((51.509934, -0.087333), distance=1500, network_type=’all’)
ox.save_graphml(G, “london.graphml”)

This code snippet creates the street network centered around the point with latitude and longitude (51.509934, -0.087333), within a radius of 1500 meters. It also saves the generated graph in london.graphml.

The generated graph looks like the following figure, where nodes are displayed in blue and edges in grey:

Image for post
Image for post
London street network — Image generated by osmnx

We can then import this graph into Neo4j using the APOC plugin:

CALL apoc.import.graphml(“london.graphml”, {})

Since the created nodes have no label, we can assign a label to them (not mandatory, but improves query performance if you happen to have other types of nodes/many nodes in your Neo4j graph):

MATCH (n) SET n:Node

Our graph schema is quite simple: only one node Label (Node), related to each other through the RELATED relationship:

Image for post
Image for post
Neo4j graph schema

And we are ready to go.

Finding shortest path

In order to use the GDS shortest path algorithms, we first need to create a projected graph the algorithm will run on. Here is how to create the projected graph we want to use:

CALL gds.graph.create.cypher(
“projected_graph”,
“MATCH (n:Node) RETURN id(n) AS id”,
“MATCH (n)-[r:RELATED]->(m) RETURN id(n) AS source, id(m) AS target, toFloat(r.length) AS length”
)

From this projected graph, we can then find the shortest path between two nodes with:

MATCH (startNode:Node {osmid: “7203717542”})
MATCH (endNode:Node {osmid: “7203717545”})
CALL gds.alpha.shortestPath.stream(
projected_graph”,
{
startNode: startNode,
endNode: endNode,
relationshipWeightProperty: “length”
}
)
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).osmid AS osmid, cost

The result is displayed below, both with a table listing the node’s osmid and cost(length) of the path between them (only 45 meters!), and with the graph visualization.

Image for post
Image for post
Image for post
Image for post
Nodes in the shortest path

Let’s now see how neomap can help in visualizing this path in a more understandable way, since we have geolocated nodes.

Shortest path visualization

We are going to create two layers:

  • A marker layer indicating each node in the graph
  • A polyline layer able to display the shortest path between two chosen nodes, based on a Cypher query

London Street Network

In order to visualize the London Street Network, we can use a simple layer configuration. In this setup, we just need to configure:

  • The node label(s) to be displayed. Here we only have one label called Node
  • The node property containing the latitude (y in our case)
  • The node property containing the longitude (x in our case)
  • The node property to be used for the popup. We will choose the osmid property to be able to easily identify and find the node locations

Finally, we can choose the color to be used for the markers. Here I choose grey for convenience. The final configuration is shown on the image below:

Image for post
Image for post
Simple marker layer configuration

You can hit the “Update map” button to see where our nodes are. Let’s now create another layer to display the result of a shortest path algorithm.

Shortest Path

To visualize shortest path, we will use an advanced layer configuration, selecting the nodes allowed to be displayed, using a Cypher query. This query needs to return two attributes: the latitude and longitude of the nodes. Starting from the shortest path query above, we just need to change our return statement so that it returns the nodes latitude (y attribute) and longitude (x attribute):

MATCH (startNode:Node {osmid: "7203717542"})
MATCH (endNode:Node {osmid: "7203717545"})
CALL gds.alpha.shortestPath.stream(
"projected_graph",
{
startNode: startNode,
endNode: endNode,
relationshipWeightProperty: "length"
}
)
YIELD nodeId, cost
WITH gds.util.asNode(nodeId) AS node
RETURN node.x AS longitude, node.y AS latitude

Inside the neomap layer configuration, we will also choose the “Polyline” map rendering method, in order to draw a line and not markers for this path:

Image for post
Image for post
Shortest Path advanced layer configuration

Updating the map displays this result nicely:

Image for post
Image for post

Finding path between other pairs of nodes

You can now also use the London Street Network layer to find the node’s osmid (by clicking on them) and modify the shortest path query. For instance, let’s find the shortest path between St Paul’s Cathedral and Cannon Street Station:

Image for post
Image for post

NB: since our nodes do have latitude and longitude (y and x), we can also use the A* algorithm (gds.alpha.shortestPath.astar).

Have fun with Neo4j, its new GDS plugin and neomap!

Neo4j Developer Blog

Developer Content around Graph Databases, Neo4j, Cypher…

Estelle Scifo

Written by

PhD, Data Scientist, Python developer — Graphie award 2019 @Neo4j — author @PacktPub — https://www.linkedin.com/in/estellescifo/

Neo4j Developer Blog

Developer Content around Graph Databases, Neo4j, Cypher, Data Science, Graph Analytics, GraphQL and more.

Estelle Scifo

Written by

PhD, Data Scientist, Python developer — Graphie award 2019 @Neo4j — author @PacktPub — https://www.linkedin.com/in/estellescifo/

Neo4j Developer Blog

Developer Content around Graph Databases, Neo4j, Cypher, Data Science, Graph Analytics, GraphQL and more.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store