A* returns bad path.

[Legolash2o]

I'm running both the apoc Dijkstra and apoc A algorithm on openstreetmap UK data. Dijkstra seems to be working correctly but A is bring back a weird result. It does the same when using the Neo4j web interface as well.

I only use: highway=motorway,trunk,primary,secondary,motorway_link,trunk_link,primary_link,secondary_link

Dijkstra vs A https://imgur.com/nKkOeYD Zoomed in https://imgur.com/DX6sJbd Red is Dijkstra and blue is A

The area in the red box looks like it's going the longer way round as there is route between the two roundabouts. It's the same near the area (Grays)

Possibly Related Another but possibly related issue too is that if I add sea route from start to finish with a length of 100000, it returns that as the result enough though via road it's about 700 miles.

match(s:Node {UID: 60224115}), (e: Node { UID: 4582764124}) 
CALL apoc.algo.dijkstra(s, e, 'Highway>', 'Length') YIELD path, weight 
RETURN path, weight LIMIT 1

match(s:Node {UID: 60224115}), (e: Node { UID: 4582764124}) 
CALL apoc.algo.aStar(s, e,'Highway>' ,'Length','Latitude','Longitude') YIELD path, weight 
RETURN path, weight LIMIT 1

[sarmbruster]

have you tried to exchange latitude and longitude in the astar call? I wonder how the path looks like when you try this.

[Legolash2o]

Thanks for the reply. It still looks wrong when switching.

https://imgur.com/dYMqYaW

[Legolash2o]

It seems to be going the wrong way when it comes to a oneways. The data in my graph matches OSM directions on oneways. I have a hunch that when it finds the node, it needs to reverse back incorrectly.

https://imgur.com/ElnaogV https://imgur.com/of0lY9H

I forgot to mention that I'm only using highway=motorway,trunk,primary,secondary,motorway_link,trunk_link,primary_link,secondary_link

[sarmbruster]

Is there a way for you to share your database? I can also provide a private channel for this. Would be much easier to debug with the same data at hand.

[Legolash2o]

I can share with you with CSVs I outputted and the commands I used?

[sarmbruster]

CSVs I outputted Output? Or did you mean the csv you've used to build the graph via load csv ? If so this would help.

[Legolash2o]

Yes, it's the CSVs I used to build the graph. I don't have control of the firewall settings on this server to give you access that way and the database itself my to be big too upload as it contains Europe.

[Legolash2o]

Hopefully this contains enough for you to rebuild the database. It only contains Great Britain as that's where the algorithm seems to be malfunctioning.

https://universityofhull.box.com/s/dz4bwqvk4y7c0v3ca168nut64bol1qwu

[sarmbruster]

That should be good enough. Gimme some time for getting more insight.

[Legolash2o]

It might be worth stopping for a while as I think I found a bug in the code that turns my OSM into CSV. I didn't include that roundabout is oneway and only looked for oneway tags.

[sarmbruster]

Ok, so I'm on hold until you get back.

[Legolash2o]

Just finished testing. I was wrong about the going up the wrong ways but it still returning a very different result than Dijkstra https://imgur.com/Vf0BhK1

It is also making weird decisions. Below is an example where it would be quicker to go the route I drawn, it does this sort of thing alot. https://imgur.com/yV4Xvs1

Another example is that if I add edges between the start and end i.e. via the sea and that route is longer, it will still give me that as a route because there's less nodes between them. sea for example would be 700 miles whereas by road is 600 miles. It's almost as if it stops search as soon as it finds the end node even though it may not be the quickest. Not sure if that's how A* works.

CSV files https://universityofhull.box.com/s/91elldmoh2qmcwyqulld157ret1v2ivj

[sarmbruster]

since apoc just delegates to a astar function inside neo4j I guess it needs to be fixed in Neo4j and not in apoc. Need to investigate more.

[conker84]

This can be done in GDS now