diff options
Diffstat (limited to '_site')
| -rw-r--r-- | _site/feed.xml | 2 | ||||
| -rw-r--r-- | _site/index.html | 2 | ||||
| -rw-r--r-- | _site/log/fpm-door-lock-rf/index.html | 2 | ||||
| -rw-r--r-- | _site/log/index.html | 2 | ||||
| -rw-r--r-- | _site/log/neo4j-a-star-search/index.html | 333 | ||||
| -rw-r--r-- | _site/posts.xml | 2 |
6 files changed, 41 insertions, 302 deletions
diff --git a/_site/feed.xml b/_site/feed.xml index 9569ab2..fd63680 100644 --- a/_site/feed.xml +++ b/_site/feed.xml @@ -1 +1 @@ -<?xml version="1.0" encoding="utf-8"?><feed xmlns="http://www.w3.org/2005/Atom" ><generator uri="https://jekyllrb.com/" version="4.4.1">Jekyll</generator><link href="/feed.xml" rel="self" type="application/atom+xml" /><link href="/" rel="alternate" type="text/html" /><updated>2025-12-28T07:41:39+08:00</updated><id>/feed.xml</id><title type="html">ASCIIMX | Log</title><author><name>W. D. Sadeep Madurange</name></author><entry><title type="html">Matrix Rain: 2025 refactor</title><link href="/log/matrix-digital-rain/" rel="alternate" type="text/html" title="Matrix Rain: 2025 refactor" /><published>2025-12-21T00:00:00+08:00</published><updated>2025-12-21T00:00:00+08:00</updated><id>/log/matrix-digital-rain</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[The 2022 version worked but had some loose ends. Unicode support was inflexible–couldn’t mix ASCII with Katakana; Phosphor decay was stored in a separate array when it should’ve been packed with RGB; Code was harder to read than it needed to be.]]></summary></entry><entry><title type="html">Fingerprint door lock (LP)</title><link href="/log/fpm-door-lock-lp/" rel="alternate" type="text/html" title="Fingerprint door lock (LP)" /><published>2025-08-18T00:00:00+08:00</published><updated>2025-08-18T00:00:00+08:00</updated><id>/log/fpm-door-lock-lp</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Second iteration of the RF door lock. Old version worked but drew too much quiescent current. Sensor and servo pulled 13.8mA and 4.6mA idle. Linear regulators were a disaster. Battery didn’t last 24 hours.]]></summary></entry><entry><title type="html">High-side MOSFET switching</title><link href="/log/mosfet-switches/" rel="alternate" type="text/html" title="High-side MOSFET switching" /><published>2025-06-22T00:00:00+08:00</published><updated>2025-06-22T00:00:00+08:00</updated><id>/log/mosfet-switches</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Needed low-power switching for the fingerprint door lock. Servo and FPM draw high quiescent current–had to cut power electronically during sleep. MOSFETs can do this.]]></summary></entry><entry><title type="html">ATmega328P at 3.3V and 5V</title><link href="/log/arduino-uno/" rel="alternate" type="text/html" title="ATmega328P at 3.3V and 5V" /><published>2025-06-10T00:00:00+08:00</published><updated>2025-06-10T00:00:00+08:00</updated><id>/log/arduino-uno</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Quick reference for wiring ATmega328P ICs at 5V and 3.3V. 5V uses 16MHz crystal, 3.3V uses 8MHz.]]></summary></entry><entry><title type="html">Fingerprint door lock (RF)</title><link href="/log/fpm-door-lock-rf/" rel="alternate" type="text/html" title="Fingerprint door lock (RF)" /><published>2025-06-05T00:00:00+08:00</published><updated>2025-06-05T00:00:00+08:00</updated><id>/log/fpm-door-lock-rf</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Wanted to unlock door with fingerprint, wirelessly to avoid drilling.]]></summary></entry><entry><title type="html">Bumblebee: browser automation</title><link href="/log/bumblebee/" rel="alternate" type="text/html" title="Bumblebee: browser automation" /><published>2025-04-02T00:00:00+08:00</published><updated>2025-04-02T00:00:00+08:00</updated><id>/log/bumblebee</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Built with Andy Zhang for an employer. Tool to automate web scraping script generation.]]></summary></entry><entry><title type="html">ATSAM3X8E bare-metal programming</title><link href="/log/arduino-due/" rel="alternate" type="text/html" title="ATSAM3X8E bare-metal programming" /><published>2024-09-16T00:00:00+08:00</published><updated>2024-09-16T00:00:00+08:00</updated><id>/log/arduino-due</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Notes on programming ATSAM3X8E chips (Arduino Due) without bootloader. Tested on OpenBSD.]]></summary></entry><entry><title type="html">Etlas: e-paper dashboard</title><link href="/log/etlas/" rel="alternate" type="text/html" title="Etlas: e-paper dashboard" /><published>2024-09-05T00:00:00+08:00</published><updated>2024-09-05T00:00:00+08:00</updated><id>/log/etlas</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Repurposed e-reader prototype into something for regular use. News, stocks, weather dashboard. ESP32 NodeMCU D1 + 7.5” Waveshare e-paper + DHT22 sensor.]]></summary></entry><entry><title type="html">ESP32 e-reader prototype</title><link href="/log/e-reader/" rel="alternate" type="text/html" title="ESP32 e-reader prototype" /><published>2023-10-24T00:00:00+08:00</published><updated>2023-10-24T00:00:00+08:00</updated><id>/log/e-reader</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[First project with e-paper displays and ESP32.]]></summary></entry><entry><title type="html">Neo4J A* search</title><link href="/log/neo4j-a-star-search/" rel="alternate" type="text/html" title="Neo4J A* search" /><published>2018-03-06T00:00:00+08:00</published><updated>2018-03-06T00:00:00+08:00</updated><id>/log/neo4j-a-star-search</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[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.]]></summary></entry></feed>
\ No newline at end of file +<?xml version="1.0" encoding="utf-8"?><feed xmlns="http://www.w3.org/2005/Atom" ><generator uri="https://jekyllrb.com/" version="4.4.1">Jekyll</generator><link href="/feed.xml" rel="self" type="application/atom+xml" /><link href="/" rel="alternate" type="text/html" /><updated>2025-12-28T10:40:10+08:00</updated><id>/feed.xml</id><title type="html">ASCIIMX | Log</title><author><name>W. D. Sadeep Madurange</name></author><entry><title type="html">Matrix Rain: 2025 refactor</title><link href="/log/matrix-digital-rain/" rel="alternate" type="text/html" title="Matrix Rain: 2025 refactor" /><published>2025-12-21T00:00:00+08:00</published><updated>2025-12-21T00:00:00+08:00</updated><id>/log/matrix-digital-rain</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[The 2022 version worked but had some loose ends. Unicode support was inflexible–couldn’t mix ASCII with Katakana; Phosphor decay was stored in a separate array when it should’ve been packed with RGB; Code was harder to read than it needed to be.]]></summary></entry><entry><title type="html">Fingerprint door lock (LP)</title><link href="/log/fpm-door-lock-lp/" rel="alternate" type="text/html" title="Fingerprint door lock (LP)" /><published>2025-08-18T00:00:00+08:00</published><updated>2025-08-18T00:00:00+08:00</updated><id>/log/fpm-door-lock-lp</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Second iteration of the RF door lock. Old version worked but drew too much quiescent current. Sensor and servo pulled 13.8mA and 4.6mA idle. Linear regulators were a disaster. Battery didn’t last 24 hours.]]></summary></entry><entry><title type="html">High-side MOSFET switching</title><link href="/log/mosfet-switches/" rel="alternate" type="text/html" title="High-side MOSFET switching" /><published>2025-06-22T00:00:00+08:00</published><updated>2025-06-22T00:00:00+08:00</updated><id>/log/mosfet-switches</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Needed low-power switching for the fingerprint door lock. Servo and FPM draw high quiescent current–had to cut power electronically during sleep. MOSFETs can do this.]]></summary></entry><entry><title type="html">ATmega328P at 3.3V and 5V</title><link href="/log/arduino-uno/" rel="alternate" type="text/html" title="ATmega328P at 3.3V and 5V" /><published>2025-06-10T00:00:00+08:00</published><updated>2025-06-10T00:00:00+08:00</updated><id>/log/arduino-uno</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Quick reference for wiring ATmega328P ICs at 5V and 3.3V. 5V uses 16MHz crystal, 3.3V uses 8MHz.]]></summary></entry><entry><title type="html">Fingerprint door lock (RF)</title><link href="/log/fpm-door-lock-rf/" rel="alternate" type="text/html" title="Fingerprint door lock (RF)" /><published>2025-06-05T00:00:00+08:00</published><updated>2025-06-05T00:00:00+08:00</updated><id>/log/fpm-door-lock-rf</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Wanted to unlock door with fingerprint, wirelessly to avoid drilling.]]></summary></entry><entry><title type="html">Bumblebee: browser automation</title><link href="/log/bumblebee/" rel="alternate" type="text/html" title="Bumblebee: browser automation" /><published>2025-04-02T00:00:00+08:00</published><updated>2025-04-02T00:00:00+08:00</updated><id>/log/bumblebee</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Built with Andy Zhang for an employer. Tool to automate web scraping script generation.]]></summary></entry><entry><title type="html">ATSAM3X8E bare-metal programming</title><link href="/log/arduino-due/" rel="alternate" type="text/html" title="ATSAM3X8E bare-metal programming" /><published>2024-09-16T00:00:00+08:00</published><updated>2024-09-16T00:00:00+08:00</updated><id>/log/arduino-due</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Notes on programming ATSAM3X8E chips (Arduino Due) without bootloader. Tested on OpenBSD.]]></summary></entry><entry><title type="html">Etlas: e-paper dashboard</title><link href="/log/etlas/" rel="alternate" type="text/html" title="Etlas: e-paper dashboard" /><published>2024-09-05T00:00:00+08:00</published><updated>2024-09-05T00:00:00+08:00</updated><id>/log/etlas</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Repurposed e-reader prototype into something for regular use. News, stocks, weather dashboard. ESP32 NodeMCU D1 + 7.5” Waveshare e-paper + DHT22 sensor.]]></summary></entry><entry><title type="html">ESP32 e-reader prototype</title><link href="/log/e-reader/" rel="alternate" type="text/html" title="ESP32 e-reader prototype" /><published>2023-10-24T00:00:00+08:00</published><updated>2023-10-24T00:00:00+08:00</updated><id>/log/e-reader</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[First project with e-paper displays and ESP32.]]></summary></entry><entry><title type="html">Neo4j shortest path optimization</title><link href="/log/neo4j-a-star-search/" rel="alternate" type="text/html" title="Neo4j shortest path optimization" /><published>2018-03-06T00:00:00+08:00</published><updated>2018-03-06T00:00:00+08:00</updated><id>/log/neo4j-a-star-search</id><author><name>W. D. Sadeep Madurange</name></author><summary type="html"><![CDATA[Replaced Dijkstra’s for vessel route tracking in Neo4J.]]></summary></entry></feed>
\ 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 @@ <tr> <td class="posts-td posts-td-link"> - <a href="/log/neo4j-a-star-search/" class="link-decor-none">Neo4J A* search</a> + <a href="/log/neo4j-a-star-search/" class="link-decor-none">Neo4j shortest path optimization</a> </td> <td class="posts-td posts-td-time"> <span class="post-meta"> 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.</p> <p>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.</p> 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 @@ <tr> <td class="posts-td posts-td-link"> - <a href="/log/neo4j-a-star-search/" class="link-decor-none">Neo4J A* search</a> + <a href="/log/neo4j-a-star-search/" class="link-decor-none">Neo4j shortest path optimization</a> </td> <td class="posts-td posts-td-time"> <span class="post-meta"> 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<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; +} +</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 < 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> diff --git a/_site/posts.xml b/_site/posts.xml index e2404d1..35f625c 100644 --- a/_site/posts.xml +++ b/_site/posts.xml @@ -1 +1 @@ -<?xml version="1.0" encoding="utf-8"?><feed xmlns="http://www.w3.org/2005/Atom" ><generator uri="https://jekyllrb.com/" version="4.4.1">Jekyll</generator><link href="/posts.xml" rel="self" type="application/atom+xml" /><link href="/" rel="alternate" type="text/html" /><updated>2025-12-28T07:41:39+08:00</updated><id>/posts.xml</id><title type="html">ASCIIMX</title><author><name>W. D. Sadeep Madurange</name></author></feed>
\ No newline at end of file +<?xml version="1.0" encoding="utf-8"?><feed xmlns="http://www.w3.org/2005/Atom" ><generator uri="https://jekyllrb.com/" version="4.4.1">Jekyll</generator><link href="/posts.xml" rel="self" type="application/atom+xml" /><link href="/" rel="alternate" type="text/html" /><updated>2025-12-28T10:40:10+08:00</updated><id>/posts.xml</id><title type="html">ASCIIMX</title><author><name>W. D. Sadeep Madurange</name></author></feed>
\ No newline at end of file |