From 0777fca6c67f6e1e96fd12db870b33dd7956899a Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Sun, 28 Dec 2025 08:08:52 +0800 Subject: Neo4J. --- _site/feed.xml | 2 +- _site/index.html | 2 +- _site/log/fpm-door-lock-rf/index.html | 2 +- _site/log/index.html | 2 +- _site/log/neo4j-a-star-search/index.html | 333 ++++--------------------------- _site/posts.xml | 2 +- 6 files changed, 41 insertions(+), 302 deletions(-) (limited to '_site') diff --git a/_site/feed.xml b/_site/feed.xml index 9569ab2..fd63680 100644 --- a/_site/feed.xml +++ b/_site/feed.xml @@ -1 +1 @@ -Jekyll2025-12-28T07:41:39+08:00/feed.xmlASCIIMX | LogW. D. Sadeep MadurangeMatrix Rain: 2025 refactor2025-12-21T00:00:00+08:002025-12-21T00:00:00+08:00/log/matrix-digital-rainW. D. Sadeep MadurangeFingerprint door lock (LP)2025-08-18T00:00:00+08:002025-08-18T00:00:00+08:00/log/fpm-door-lock-lpW. D. Sadeep MadurangeHigh-side MOSFET switching2025-06-22T00:00:00+08:002025-06-22T00:00:00+08:00/log/mosfet-switchesW. D. Sadeep MadurangeATmega328P at 3.3V and 5V2025-06-10T00:00:00+08:002025-06-10T00:00:00+08:00/log/arduino-unoW. D. Sadeep MadurangeFingerprint door lock (RF)2025-06-05T00:00:00+08:002025-06-05T00:00:00+08:00/log/fpm-door-lock-rfW. D. Sadeep MadurangeBumblebee: browser automation2025-04-02T00:00:00+08:002025-04-02T00:00:00+08:00/log/bumblebeeW. D. Sadeep MadurangeATSAM3X8E bare-metal programming2024-09-16T00:00:00+08:002024-09-16T00:00:00+08:00/log/arduino-dueW. D. Sadeep MadurangeEtlas: e-paper dashboard2024-09-05T00:00:00+08:002024-09-05T00:00:00+08:00/log/etlasW. D. Sadeep MadurangeESP32 e-reader prototype2023-10-24T00:00:00+08:002023-10-24T00:00:00+08:00/log/e-readerW. D. Sadeep MadurangeNeo4J A* search2018-03-06T00:00:00+08:002018-03-06T00:00:00+08:00/log/neo4j-a-star-searchW. D. Sadeep Madurange \ No newline at end of file +Jekyll2025-12-28T10:40:10+08:00/feed.xmlASCIIMX | LogW. D. Sadeep MadurangeMatrix Rain: 2025 refactor2025-12-21T00:00:00+08:002025-12-21T00:00:00+08:00/log/matrix-digital-rainW. D. Sadeep MadurangeFingerprint door lock (LP)2025-08-18T00:00:00+08:002025-08-18T00:00:00+08:00/log/fpm-door-lock-lpW. D. Sadeep MadurangeHigh-side MOSFET switching2025-06-22T00:00:00+08:002025-06-22T00:00:00+08:00/log/mosfet-switchesW. D. Sadeep MadurangeATmega328P at 3.3V and 5V2025-06-10T00:00:00+08:002025-06-10T00:00:00+08:00/log/arduino-unoW. D. Sadeep MadurangeFingerprint door lock (RF)2025-06-05T00:00:00+08:002025-06-05T00:00:00+08:00/log/fpm-door-lock-rfW. D. Sadeep MadurangeBumblebee: browser automation2025-04-02T00:00:00+08:002025-04-02T00:00:00+08:00/log/bumblebeeW. D. Sadeep MadurangeATSAM3X8E bare-metal programming2024-09-16T00:00:00+08:002024-09-16T00:00:00+08:00/log/arduino-dueW. D. Sadeep MadurangeEtlas: e-paper dashboard2024-09-05T00:00:00+08:002024-09-05T00:00:00+08:00/log/etlasW. D. Sadeep MadurangeESP32 e-reader prototype2023-10-24T00:00:00+08:002023-10-24T00:00:00+08:00/log/e-readerW. D. Sadeep MadurangeNeo4j shortest path optimization2018-03-06T00:00:00+08:002018-03-06T00:00:00+08:00/log/neo4j-a-star-searchW. D. Sadeep Madurange \ No newline at end of file diff --git a/_site/index.html b/_site/index.html index 24e96cf..f7b6c70 100644 --- a/_site/index.html +++ b/_site/index.html @@ -173,7 +173,7 @@ - Neo4J A* search + Neo4j shortest path optimization diff --git a/_site/log/fpm-door-lock-rf/index.html b/_site/log/fpm-door-lock-rf/index.html index 96dc356..0c5037b 100644 --- a/_site/log/fpm-door-lock-rf/index.html +++ b/_site/log/fpm-door-lock-rf/index.html @@ -51,7 +51,7 @@ lines of the transceivers to UART RXD/TXD of an ATmega328P. Unreliable–constant packet loss.

2025-01: Switched to RFM69 modules. A complete ball-ache. Followed the -datasheet to the letter, audited code more than 30 times, cross-checked with +datasheet to the letter, audited code more than 10 times, cross-checked with RadioHead and RFM69 OSS drivers. No luck. ATmega328P runs at 5V, RFM69 3.3V. I suspect the problem is with the logic-level converter (LLC). Not enough swing.

diff --git a/_site/log/index.html b/_site/log/index.html index 59582a7..de9c470 100644 --- a/_site/log/index.html +++ b/_site/log/index.html @@ -163,7 +163,7 @@ - Neo4J A* search + Neo4j shortest path optimization diff --git a/_site/log/neo4j-a-star-search/index.html b/_site/log/neo4j-a-star-search/index.html index 9473dc6..a00dd6c 100644 --- a/_site/log/neo4j-a-star-search/index.html +++ b/_site/log/neo4j-a-star-search/index.html @@ -2,12 +2,12 @@ - Neo4J A* search + Neo4j shortest path optimization - Neo4J A* search + Neo4j shortest path optimization @@ -41,316 +41,55 @@
-

NEO4J A* SEARCH

+

NEO4J SHORTEST PATH OPTIMIZATION

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.

+

Replaced Dijkstra’s for vessel route tracking in Neo4J.

-

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.

+

Tracking 13,000 marine vessel route points. Needed shortest paths between ports +for arrival prediction. Neo4j’s Dijkstra’s algorithm slows after 4,000 route +points.

-

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.

+

Implemented A* search using haversine function as heuristic:

-

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:

+
private double computeHeuristic(
+    final double lat1, final double lon1,
+    final double lat2, final double lon2) {
+    final int earthRadius = 6371;
+    final double kmToNM = 0.539957;
 
-
package org.neo4j.graphalgo.impl;
+    final double latDistance = Math.toRadians(lat2 - lat1);
+    final double lonDistance = Math.toRadians(lon2 - lon1);
 
-import java.util.stream.Stream;
-import java.util.stream.StreamSupport;
+    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);
 
-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;
+    final double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
 
-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;
+    return earthRadius * c * kmToNM;
+}
+

 
-        /**
-         * cost to reach the node from startNode
-         */
-        public final Double cost;
+
Core search loop updates costs when better path found:

 
-        public Result(Long nodeId, Double cost) {
-            this.nodeId = nodeId;
-            this.cost = cost;
-        }
+
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);
     }
 }
 

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

-
+
Outcome: 300x speedup. Scaled to 13,000 route points. Upstreamed changes. Neo4J v3.4.0.
+Full source

by W. D. Sadeep Madurange

diff --git a/_site/posts.xml b/_site/posts.xml index e2404d1..35f625c 100644 --- a/_site/posts.xml +++ b/_site/posts.xml @@ -1 +1 @@ -Jekyll2025-12-28T07:41:39+08:00/posts.xmlASCIIMXW. D. Sadeep Madurange \ No newline at end of file +Jekyll2025-12-28T10:40:10+08:00/posts.xmlASCIIMXW. D. Sadeep Madurange \ No newline at end of file -- cgit v1.2.3