Pathfinding in Graphileon using GeoJSON and the aStar algorithm

Introduction

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 feature.properties.highway IS NULL
AND NOT feature.properties.highway = '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)
WITH f,
     apoc.convert.fromJsonMap(f.geoJson) AS feature
WITH f,
     COALESCE(feature.properties.oneway,'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)
      OR 
      point.withinBBox(m.location,sw,ne)

RETURN COLLECT(
         { 
          id: id(r),
          type: "Feature", 
          style: {
            strokeColor: "black"
          },
          geometry: {
            type: "LineString",
            coordinates:[
                      [n.x,n.y],
                      [m.x,m.y]
            ]
         },
         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.

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
ORDER BY d LIMIT 1

WITH end,
     wp AS from

MATCH (wp:Waypoint) 
WITH end,from,wp,
     distance(wp.location,end) AS d 
ORDER BY d LIMIT 1

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: [
                [startNode(rel).x,startNode(rel).y],
                [endNode(rel).x,endNode(rel).y]
              ]
            }
     ) 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",
                id: segment.id,
                geometry: {
                  type: "LineString",
                  coordinates: segment.coordinates
                },
                style: {
                  strokeColor:'green'
                },
                properties: {
                  id: segment.id,
                  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.

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.

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

RETURN COLLECT(
         { 
          id: id(segment.item),
          type: "Feature", 
          style: {
            strokeColor: "red",
            strokeWeight: segment.count
          },
          geometry: {
            type: "LineString",
            coordinates:[
              [startNode(segment.item).x,startNode(segment.item).y],
              [endNode(segment.item).x,endNode(segment.item).y]
            ]
          },
          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.