Pathfinding in Graphileon using GeoJSON and the aStar algorithm


For a network of roads, a graph database is a natural fit. Roads have waypoints with coordinates, which are connected by road segments that can have properties like distance, type of surface and maximum speed. In this blog, we focus on the amazing things you can do with just the distance property. Combined with the capabilities of Graphileon, which allows you to model various kinds of interactions and visualizations of the graph, a small application can be built in a couple of hours.

NOTE: The functionality described below requires Neo4j 4.* and Graphileon 3.3.0 (our next release) which comes with an enhanced MapView with more events and GeoJSON handling capabilities.

NOTE: The Graphileon configuration described in this blog is available in Graphileon’s App library under the name ‘Pathfinding’

A simple model

The model we will use is very simple, and has :Waypoint nodes connected by [:NEXT] relationships.

So our graph will look as follows:

The GeoJSON we use comes from BBBike, which provides a great service to extract data from OpenStreetMap and convert it into JSON.


Neo4j‘s apoc library provides the functionality to load data from the JSON array.

CALL apoc.load.jsonArray('file:///amman.json','$.features') YIELD value
WITH value AS feature
WHERE feature.geometry.type = 'LineString'
AND NOT = 'footway'
CREATE (:Feature {geoJson:apoc.convert.toJson(feature)})

After importing the GeoJSON from a file and creating :Feature nodes, we convert the coordinate pairs inside the LineString geometries to :Waypoint nodes and connect them, with [:NEXT] relationships. For two-way segments, we create two [:NEXT] relationships, one in each direction.

Before creating the :Waypoint nodes, we create a constraint, to speed up  MERGE and automatically link the :Waypoint nodes across features. We also create an index on the [:NEXT] relationships in order to speed up the retrieval of blocked road segments.

CREATE CONSTRAINT ON ( waypoint:Waypoint ) ASSERT waypoint.location IS UNIQUE;
CREATE INDEX NEXT_blocked IF NOT EXISTS FOR ()-[r:NEXT]-() ON (r.blocked);
MATCH (f:Feature)
     apoc.convert.fromJsonMap(f.geoJson) AS feature
     COALESCE(,'no') AS oneway, 
     apoc.coll.pairsMin(feature.geometry.coordinates) AS pairs

UNWIND pairs AS pair

MERGE (from:Waypoint {location:point({latitude:pair[0][1],longitude:pair[0][0]})})
MERGE (to:Waypoint {location:point({latitude:pair[1][1],longitude:pair[1][0]})})
MERGE (from)-[:NEXT]->(to)
MERGE (f)-[:WAYPOINT]->(from)
MERGE (f)-[:WAYPOINT]->(to)
FOREACH (i IN CASE WHEN oneway = 'yes' THEN [] ELSE [1] END |
   MERGE (to)-[:NEXT]->(from)

Since we will be using the apoc.algo.aStar procedure later, which requires property names, we will also add the x and y coordinates as separate properties. In addition, we use point.distance() to calculate the distance between waypoints and store it in a property on the [:NEXT] relationship.

MATCH (wp:Waypoint)
SET wp.x = wp.location.x,
    wp.y = wp.location.y

MATCH (a)-[r:NEXT]->(b)
SET r.distance = point.distance(a.location,b.location)

Loading and visualizing GeoJSON

With the data in place, we can visualise the GeoJSON in a MapViewfunction. The MapView is connected to a Dashboard and it has a batch trigger to the query that retrieves the GeoJSON features.

We only retrieve the GeoJSON features that are in the bounding box of the MapView. Each road segment is imported as a separate feature, which will allow us to create a featureClick event on each individual road segment.

WITH point({longitude:$west,latitude:$south}) AS sw,
point({longitude:$east,latitude:$north}) AS ne

MATCH (n)-[r:NEXT]->(m)
WHERE point.withinBBox(n.location,sw,ne)

          id: id(r),
          type: "Feature", 
          style: {
            strokeColor: "black"
          geometry: {
            type: "LineString",
         properties: {}
) AS features

The result is a GeoJSON overlay over the map in the MapView. You can see that there are some differences between the roads in the Google Map and the GeoJson, but we ignore that in the context of this blog.

GeoJSON loaded in a MapView

Finding a route between points, and re-routing when a road is blocked

To find a route, we first have to add the functionality to add the start and end points to the map. For this, we use our mapClick event.

In the mapClick trigger we use javascript functions to set the right symbol for the start and end points. We also build in a matching condition to ensure that no more than two markers can be added.

To find the route, we use the aStar algorithm procedure that is available in the apoc library. The logic, displayed below, illustrates that we use an intermediary IO function that allows for clearing existing routes before visualizing the new route.

// convert the start and end coordinates to point objects
WITH point($start) AS start,
point($end) AS end

// get the closest :Waypoint nodes for start and end
MATCH (wp:Waypoint) 
WITH start,end,wp,
     distance(wp.location,start) AS d

WITH end,
     wp AS from

MATCH (wp:Waypoint) 
WITH end,from,wp,
     distance(wp.location,end) AS d 

WITH from,
     wp AS to

// use aStar algoritm to get the path with lowest weight
CALL apoc.algo.aStar(from,to,'NEXT>','weight','y','x') YIELD path,weight

// convert the path to segments
WITH from,to,weight,
     length(path) AS hops,
     REDUCE(arr=[],rel IN CASE WHEN weight > 100000 THEN [] ELSE relationships(path) END |
            arr +
              id: id(rel),
              distance: rel.distance,
              coordinates: [
     ) AS segments

// convert each segment into a geoJson feature, return as collection
WITH from,to,weight,hops,segments
     RETURN toInteger(weight) AS weight,hops,
            id(from) AS fromId,
            id(to) AS toId,
            [ segment IN segments |
                type: "Feature",
                geometry: {
                  type: "LineString",
                  coordinates: segment.coordinates
                style: {
                properties: {
                  distance: segment.distance,
                  blocked: false
             ] AS features

After adding two markers to the map, and activating the Find route batch trigger, the picture on the left shows up, representing the path with the shortest distance from start to end.

Re-routing when blocking a route segment

When clicking on a road segment, a featureClick event is triggered. This event fires a query (see below) that sets the distance of the corresponding [:NEXT] relationship to 100000, so that the aStar algorithm will avoid the segment. The blocked segment shows up in red. See the picture on the right.

MATCH ()-[r:NEXT]->()
WHERE id(r)=$id
SET r.blocked = NOT COALESCE(r.blocked,false),
    r.weight = CASE WHEN r.weight = r.distance THEN 100000 ELSE r.distance END

In addition to setting the weight to 100000, the application flow deletes the current route,  re-loads the blocked segments, and re-activates the route finding. See the diagram below.

Amman’s arteries

Until now, we have used the aStar algorithm to find a single route. When you apply it to a number of routes and count the number of times each road segment is crossed, it gives you a measure of betweenness. The map visualization below shows the results for the city of Amman, based on routes between the NW, NE, SW, SE, N, W, E and S in the bounding box. The query is given below as well.

Amman's arteries

WITH point({longitude:$west,latitude:$south}) AS sw,
     point({longitude:$east,latitude:$north}) AS ne,
     point({longitude:$west,latitude:$north}) AS nw,
     point({longitude:$east,latitude:$south}) AS se,
     point({longitude:$west,latitude:($south+$north)/2}) AS w,
     point({longitude:$east,latitude:($south+$north)/2}) AS e,
     point({longitude:($west+$east)/2,latitude:$north}) AS n,
     point({longitude:($west+$east)/2,latitude:$south}) AS s

WITH [sw,ne,nw,se,n,w,s,e] AS corners
UNWIND corners AS corner

// get the closest :Waypoint nodes for all corners
MATCH (wp:Waypoint) 
WITH corner,
     apoc.agg.minItems(wp,point.distance(wp.location,corner),1).items[0] AS cornerWp

// create sets of from,to nodes
WITH COLLECT(cornerWp) AS cornerWps
UNWIND cornerWps AS from
UNWIND cornerWps AS to
WITH from,to WHERE from <> to

// use aStar algoritm to get the path with lowest weight
CALL apoc.algo.aStar(from,to,'NEXT>','weight','y','x') YIELD path,weight

UNWIND relationships(path) AS segment
WITH apoc.coll.frequencies(COLLECT(segment)) AS segmentFrequencies
UNWIND segmentFrequencies AS segment

          id: id(segment.item),
          type: "Feature", 
          style: {
            strokeColor: "red",
            strokeWeight: segment.count
          geometry: {
            type: "LineString",
          properties: {}
) AS features

The Graphileon logic: The app is a graph too!

The functionality described above consists of a Dashboard, a MapView and an IO function, and 5 Query functions. They are linked through TRIGGER relationships.

The Graphileon logic with a Dashboard, MapView, Query and IO functions

Card image cap
Graphileon partners with thatDot to support Quine streaming graph for real-time analytics

Graphileon partners with thatDot to develop connectors for Quine (, an open-source streaming graph solution for event-driven applications.

Card image cap
Release of Graphileon 3.6.0

The release of Graphileon 3.6.0 brings numerous enhancements and features to this graph database management software. Here are the key highlights: New Components and Features: This version introduces new and improved components (Functions) and incorporates user-requested features, enhancing the functionality of the software. Enhanced Visualization: Users can now customize the visualization of nodes in the … Continued

Card image cap
The Graphileon App Library

Graphileon includes an App Library since version 3.1. The App Library contains demos to inspire you and to get you started building your own graphy applications. We included demo configurations ranging from a simple “Hello World” popup to examples that show you how to work with Google Maps, Google Charts, API calls, node templating or … Continued

Get started with Graphileon Personal Edition in the cloud or on your desktop.

The easiest way to get to know Graphileon is to spin up the Personal Edition in the Graphileon Cloud. It comes with two graph stores installed and access to the App Library with examples and apps. You can also download and install Graphileon Personal Edition to run it on your desktop. Either way, you will be able to build graphy applications an browse your graph stores in a way you never did before.