I am trying to debug a situation where apoc.algo.astar on Neo4j 5.13 returns an unexpected result.
The tests that I have run to ensure that my data is correct, are the following:
-
x and y perhaps switched? I don't think so, because x and y of my 1.6M nodes are inside correct ranges:
-
COST property missing . The query below tells me that this is not the case.
-
existence of a path.. yes checked in the query below
I am running the following query to
- get the start and end of a set of road segments.
- get the path from the junction at the beginning of the first segment (A), to the junction at the end of the last segment (B) (this proves that there actually is a path)
- run a A* to get the path from (A) to (B) using durationSeconds as the COST property.
- create geoJSON from the two paths and display them on a map.
- calculate total duration and total length of the two paths, telling me that the astar path is definitely not the shortest.
The params and query that I'm using is the following :
"$params.WVK_IDs": "387318013,387317023,392322014"
// provide WVK_IDs, not necessarily in the correct order, but together they form a continous road.
WITH split($WVK_IDs,',') AS WVK_IDs
MATCH ()-[r:MULTILINESTRING]->()
WHERE toString(r.WVK_ID) IN WVK_IDs
WITH WVK_IDs,COLLECT(r.JTE_ID_END) AS endJs, COLLECT(r.JTE_ID_BEG) AS begJs
// get the start junction and end junction of the combined road
WITH WVK_IDs,apoc.coll.subtract(begJs,endJs)[0] AS start,apoc.coll.subtract(endJs,begJs)[0] AS end
MATCH (startJ:Junction:NWB {JTE_ID: start}),(endJ:Junction:NWB {JTE_ID: end})
// prove that there is a NEXT > path from the start Junction to the end Junction
WITH WVK_IDs,startJ, endJ
MATCH pathWVK= (startJ)-[r:NEXT WHERE ( toString(r.WVK_ID) IN WVK_IDs AND r.durationSeconds IS NOT NULL ) ] ->+(endJ)
// now calculate the shortest path using A*, using durationSeconds for the COST
WITH pathWVK,startJ, endJ
CALL apoc.algo.aStar(startJ,endJ,'NEXT>','durationSeconds','y','x') YIELD path,weight
// create geoJSON for display on map
WITH pathWVK, path AS pathAStar
WITH pathWVK,pathAStar,
[node IN nodes(pathWVK) | [node.x,node.y,0]] AS coordinatesWVK,
[node IN nodes(pathAStar) | [node.x,node.y,0]] AS coordinatesAStar
WITH pathWVK,pathAStar,
{
type:'FeatureCollection',
features: [
{
type: 'Feature',
geometry: {
type: 'LineString',
coordinates: coordinatesWVK
}
},
{
type: 'Feature',
geometry: {
type: 'LineString',
coordinates: coordinatesAStar
}
}
]
} AS geoJSON
// return with total durations and lengths
RETURN geoJSON,
REDUCE(sum = 0.0 ,rel IN relationships(pathWVK) | sum +rel.durationSeconds) AS Duration_WVK,
REDUCE(sum = 0.0 ,rel IN relationships(pathAStar) | sum +rel.durationSeconds) AS Duration_AStar,
REDUCE(sum = 0.0 ,rel IN relationships(pathWVK) | sum +rel.length) AS length_WVK,
REDUCE(sum = 0.0 ,rel IN relationships(pathAStar) | sum +rel.length) AS length_AStar,
size([ node IN nodes(pathWVK) WHERE ( node.x IS NULL OR node.y IS NULL)]) AS xORy_Missing_WVK
and the results are as follows (it's pretty obvious which is the correct path)
I'm almost sure that I'm missing something, so any suggestion of checks that I can run to find a solution are most welcome.