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.

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

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

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.

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


Card image cap
Graph(ileon): Powerful tooling to plan procurement and production in food processing

In food processing and packaging, it is essential that stock levels of fresh ingredients are sufficient, food processing machines are operational and the staff to operate them are available.  This is the field in which one of our customers, The Power Central, has been operating since 2020. Besides its own food packaging activities, The Power … Continued

Card image cap
Graphileon Cloud has arrived!

Today we launch Graphileon Cloud (beta), allowing users to run a free Graphileon Personal Edition in a fully managed environment on AWS. It offers the same functionality as the Personal Edition for desktop and comes with two pre-installed Memgraph graph stores. Just go to  https://graphileon.app, create an account and spin up an environment in under … Continued

Card image cap
Graphileon basics: Run queries from your dashboard

With Graphileon you can run your own queries from the Query box on the left. Every query you run is stored in the Recent queries list so you can rerun it or reload and modify it. However, if you find yourself running the same query regularly then you might want to extend your dashboard with … 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.