summaryrefslogtreecommitdiffstats
path: root/_site/log/neo4j-a-star-search
diff options
context:
space:
mode:
authorSadeep Madurange <sadeep@asciimx.com>2025-12-28 08:08:52 +0800
committerSadeep Madurange <sadeep@asciimx.com>2025-12-28 10:40:36 +0800
commit0777fca6c67f6e1e96fd12db870b33dd7956899a (patch)
tree76764e8ecc3b45daabc9fcc6960a127ab2ecdfe2 /_site/log/neo4j-a-star-search
parent386a4985dd0d6664489392139b6d742bbf034364 (diff)
downloadwww-0777fca6c67f6e1e96fd12db870b33dd7956899a.tar.gz
Neo4J.
Diffstat (limited to '_site/log/neo4j-a-star-search')
-rw-r--r--_site/log/neo4j-a-star-search/index.html333
1 files changed, 36 insertions, 297 deletions
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 @@
<html>
<head>
<meta charset="utf-8">
- <title>Neo4J A* search</title>
+ <title>Neo4j shortest path optimization</title>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
- <title>Neo4J A* search</title>
+ <title>Neo4j shortest path optimization</title>
<link rel="stylesheet" href="/assets/css/main.css">
<link rel="stylesheet" href="/assets/css/skeleton.css">
</head>
@@ -41,316 +41,55 @@
<main>
<div class="container">
<div class="container-2">
- <h2 class="center" id="title">NEO4J A* SEARCH</h2>
+ <h2 class="center" id="title">NEO4J SHORTEST PATH OPTIMIZATION</h2>
<h6 class="center">06 MARCH 2018</h5>
<br>
- <div class="twocol justify"><p>Back in 2018, we used <a href="https://neo4j.com/" class="external" target="_blank" rel="noopener noreferrer">Neo4J</a> 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.</p>
+ <div class="twocol justify"><p>Replaced Dijkstra’s for vessel route tracking in Neo4J.</p>
-<p>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.</p>
+<p>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.</p>
-<p>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.</p>
+<p>Implemented A* search using haversine function as heuristic:</p>
-<p>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:</p>
+<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>private double computeHeuristic(
+ final double lat1, final double lon1,
+ final double lat2, final double lon2) {
+ final int earthRadius = 6371;
+ final double kmToNM = 0.539957;
-<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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&lt;ShortestPathAStar&gt; {
-
- 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() &amp;&amp; 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) -&gt; {
- 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 &lt; 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&lt;Result&gt; resultStream() {
- return StreamSupport.stream(
- shortestPath.spliterator(), false)
- .map(cursor -&gt; 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;
+}
+</code></pre></div></div>
- /**
- * cost to reach the node from startNode
- */
- public final Double cost;
+<p>Core search loop updates costs when better path found:</p>
- public Result(Long nodeId, Double cost) {
- this.nodeId = nodeId;
- this.cost = cost;
- }
+<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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 &lt; oldCost) {
+ gCosts.put(target, newCost);
+ fCosts.put(target, newCost + heuristic);
+ path.put(target, source);
}
}
</code></pre></div></div>
-<p>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 <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" class="external" target="_blank" rel="noopener noreferrer">v3.4.0</a> of the
-Neo4J graph algorithms shipped with our A* search algorithm.</p>
-
+<p>Outcome: 300x speedup. Scaled to 13,000 route points. Upstreamed changes. <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" class="external" target="_blank" rel="noopener noreferrer">Neo4J v3.4.0</a>.
+<a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/blob/bd9732d9a690319552e134708692acb5a0d6b37c/algo/src/main/java/org/neo4j/graphalgo/impl/ShortestPathAStar.java">Full source</a></p>
</div>
<p class="post-author right">by W. D. Sadeep Madurange</p>
</div>