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

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:

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:

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.

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:

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:

Shortest Path advanced layer configuration

Updating the map displays this result nicely:

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:

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!