ASCIIMX | Log

NEO4J A* SEARCH

06 MARCH 2018

+
+

Back in 2018, we used Neo4J graph database to track the +movement of marine vessels. We were interested in the shortest path a ship +could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling.

+ +

A graph is a finite set of vertices, and a subset of vertex pairs (edges). +Edges can have weights. In the case of vessel tracking, the route points form +the vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel’s arrival time.

+ +

Given a graph, an algorithm like Dijkstra’s search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J shipped with +at the time. One drawback of Dijkstra’s algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. The time complexity of this exhaustive search prevented our +database from scaling beyond 4,000 route points.

+ +

The following enhancement to Dijkstra’s search, also known as the A* search, +employs a heuristic to steer the search in the direction of the destination +more quickly. In the case of our network of vessels, which are on the earth’s +surface, spherical distance is a good candidate for a heuristic:

+ +

package org.neo4j.graphalgo.impl;
+
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
+import org.neo4j.graphalgo.api.Graph;
+import org.neo4j.graphalgo.core.utils.ProgressLogger;
+import org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue;
+import org.neo4j.graphalgo.core.utils.queue.SharedIntPriorityQueue;
+import org.neo4j.graphalgo.core.utils.traverse.SimpleBitSet;
+import org.neo4j.graphdb.Direction;
+import org.neo4j.graphdb.Node;
+import org.neo4j.kernel.internal.GraphDatabaseAPI;
+
+import com.carrotsearch.hppc.IntArrayDeque;
+import com.carrotsearch.hppc.IntDoubleMap;
+import com.carrotsearch.hppc.IntDoubleScatterMap;
+import com.carrotsearch.hppc.IntIntMap;
+import com.carrotsearch.hppc.IntIntScatterMap;
+
+public class ShortestPathAStar extends Algorithm<ShortestPathAStar> {
+    
+    private final GraphDatabaseAPI dbService;
+    private static final int PATH_END = -1;
+    
+    private Graph graph;
+    private final int nodeCount;
+    private IntDoubleMap gCosts;
+    private IntDoubleMap fCosts;
+    private double totalCost;
+    private IntPriorityQueue openNodes;
+    private IntIntMap path;
+    private IntArrayDeque shortestPath;
+    private SimpleBitSet closedNodes;
+    private final ProgressLogger progressLogger;
+    
+    public static final double NO_PATH_FOUND = -1.0;
+    
+    public ShortestPathAStar(
+        final Graph graph,
+        final GraphDatabaseAPI dbService) {
+
+        this.graph = graph;
+        this.dbService = dbService;
+
+        nodeCount = Math.toIntExact(graph.nodeCount());
+        gCosts = new IntDoubleScatterMap(nodeCount);
+        fCosts = new IntDoubleScatterMap(nodeCount);
+        openNodes = SharedIntPriorityQueue.min(
+            nodeCount,
+            fCosts,
+            Double.MAX_VALUE);
+        path = new IntIntScatterMap(nodeCount);
+        closedNodes = new SimpleBitSet(nodeCount);
+        shortestPath = new IntArrayDeque();
+        progressLogger = getProgressLogger();
+    }
+    
+    public ShortestPathAStar compute(
+        final long startNode,
+        final long goalNode,
+        final String propertyKeyLat,
+        final String propertyKeyLon,
+        final Direction direction) {
+
+        reset();
+
+        final int startNodeInternal = 
+            graph.toMappedNodeId(startNode);
+        final double startNodeLat =
+            getNodeCoordinate(startNodeInternal, propertyKeyLat);
+        final double startNodeLon = 
+            getNodeCoordinate(startNodeInternal, propertyKeyLon);
+
+        final int goalNodeInternal =
+            graph.toMappedNodeId(goalNode);
+        final double goalNodeLat = 
+            getNodeCoordinate(goalNodeInternal, propertyKeyLat);
+        final double goalNodeLon = 
+            getNodeCoordinate(goalNodeInternal, propertyKeyLon);
+
+        final double initialHeuristic = 
+            computeHeuristic(startNodeLat,
+                startNodeLon,
+                goalNodeLat,
+                goalNodeLon);
+
+        gCosts.put(startNodeInternal, 0.0);
+        fCosts.put(startNodeInternal, initialHeuristic);
+        openNodes.add(startNodeInternal, 0.0);
+
+        run(goalNodeInternal,
+            propertyKeyLat,
+            propertyKeyLon,
+            direction);
+
+        if (path.containsKey(goalNodeInternal)) {
+            totalCost = gCosts.get(goalNodeInternal);
+            int node = goalNodeInternal;
+            while (node != PATH_END) {
+                shortestPath.addFirst(node);
+                node = path.getOrDefault(node, PATH_END);
+            }
+        }
+        return this;
+    }
+    
+    private void run(
+        final int goalNodeId,
+        final String propertyKeyLat,
+        final String propertyKeyLon,
+        final Direction direction) {
+
+        final double goalLat = 
+            getNodeCoordinate(goalNodeId, propertyKeyLat);
+        final double goalLon =
+            getNodeCoordinate(goalNodeId, propertyKeyLon);
+
+        while (!openNodes.isEmpty() && running()) {
+            int currentNodeId = openNodes.pop();
+            if (currentNodeId == goalNodeId) {
+                return;
+            }
+
+            closedNodes.put(currentNodeId);
+
+            double currentNodeCost = 
+                this.gCosts.getOrDefault(
+                    currentNodeId, 
+                    Double.MAX_VALUE);
+
+            graph.forEachRelationship(
+                currentNodeId,
+                direction,
+                (source, target, relationshipId, weight) -> {
+                    double neighbourLat = 
+                        getNodeCoordinate(target, propertyKeyLat);
+                    double neighbourLon = 
+                        getNodeCoordinate(target, propertyKeyLon);
+                    double heuristic = 
+                        computeHeuristic(
+                            neighbourLat, 
+                            neighbourLon, 
+                            goalLat,
+                            goalLon);
+
+                    updateCosts(
+                        source,
+                        target,
+                        weight + currentNodeCost,
+                        heuristic);
+
+                    if (!closedNodes.contains(target)) {
+                        openNodes.add(target, 0);
+                    }
+                    return true;
+                });
+
+            progressLogger.logProgress(
+                (double) currentNodeId / (nodeCount - 1));
+        }
+    }
+    
+    private double computeHeuristic(
+        final double lat1,
+        final double lon1,
+        final double lat2,
+        final double lon2) {
+
+        final int earthRadius = 6371;
+        final double kmToNM = 0.539957;
+        final double latDistance = Math.toRadians(lat2 - lat1);
+        final double lonDistance = Math.toRadians(lon2 - lon1);
+        final double a = Math.sin(latDistance / 2)
+            * Math.sin(latDistance / 2)
+            + Math.cos(Math.toRadians(lat1))
+            * Math.cos(Math.toRadians(lat2))
+            * Math.sin(lonDistance / 2)
+            * Math.sin(lonDistance / 2);
+        final double c = 2
+            * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
+        final double distance = earthRadius * c * kmToNM;
+        return distance;
+    }
+    
+    private double getNodeCoordinate(
+        final int nodeId,
+        final String coordinateType) {
+
+        final long neo4jId = graph.toOriginalNodeId(nodeId);
+        final Node node = dbService.getNodeById(neo4jId);
+        return (double) node.getProperty(coordinateType);
+    }
+    
+    private void updateCosts(
+        final int source, 
+        final int target, 
+        final double newCost,
+        final double heuristic) {
+
+        final double oldCost = 
+            gCosts.getOrDefault(target, Double.MAX_VALUE);
+
+        if (newCost < oldCost) {
+            gCosts.put(target, newCost);
+            fCosts.put(target, newCost + heuristic);
+            path.put(target, source);
+        }
+    }
+    
+    private void reset() {
+        closedNodes.clear();
+        openNodes.clear();
+        gCosts.clear();
+        fCosts.clear();
+        path.clear();
+        shortestPath.clear();
+        totalCost = NO_PATH_FOUND;
+    }
+    
+    public Stream<Result> resultStream() {
+        return StreamSupport.stream(
+            shortestPath.spliterator(), false)
+                .map(cursor -> new Result(
+                    graph.toOriginalNodeId(cursor.value),
+                    gCosts.get(cursor.value)));
+    }
+
+    public IntArrayDeque getFinalPath() {
+        return shortestPath;
+    }
+    
+    public double getTotalCost() {
+        return totalCost;
+    }
+
+    public int getPathLength() {
+        return shortestPath.size();
+    }
+    
+    @Override
+    public ShortestPathAStar me() {
+        return this;
+    }
+
+    @Override
+    public ShortestPathAStar release() {
+        graph = null;
+        gCosts = null;
+        fCosts = null;
+        openNodes = null;
+        path = null;
+        shortestPath = null;
+        closedNodes = null;
+        return this;
+    }
+    
+    public static class Result {
+
+        /**
+         * the neo4j node id
+         */
+        public final Long nodeId;
+
+        /**
+         * cost to reach the node from startNode
+         */
+        public final Double cost;
+
+        public Result(Long nodeId, Double cost) {
+            this.nodeId = nodeId;
+            this.cost = cost;
+        }
+    }
+}
+

+ +

The heuristic function is domain-specific. If chosen wisely, it can +significantly speed up the search. In our case, we achieved a 300x speedup, +enabling us to expand our search from 4,000 to 13,000 route points. The v3.4.0 of the +Neo4J graph algorithms shipped with our A* search algorithm.

+ +

by W. D. Sadeep Madurange

RECREATING THE MATRIX RAIN WITH ANSI ESCAPE SEQUENCES

21 DECEMBER 2025

Unicode support

Phosphor decay

The algorithm

NEO4J A* SEARCH

06 MARCH 2018