A* SQL function returns paths of increasing length for consecutive, identical queries

martineutinger commented 7 years ago

OrientDB Version, operating system, or hardware.

v2.2.14

Operating System

[ ] Linux
[ ] MacOSX
[x] Windows
[ ] Other Unix
[ ] Other, name?

Expected behavior and actual behavior

When sending the same query (e.g. 'SELECT astar(#23:19965, #23:19187, 'length')') more than once, only the first result is correct. The consecutive results are longer and longer paths until it seems to either plateau or return no path at all.

So e.g. the shortest path contains 5 nodes. The first query would return the 5 nodes. The second would return 10. Then 17. And then it returns 21 for every query past that point.

Steps to reproduce the problem

Start the server, or connect to a local database.
Send a query like 'SELECT astar(#23:19965, #23:19187, 'length')' multiple times WITHOUT restarting the server in between each query.

Possible solutions

The problem seems to be, that in com.orientechnologies.orient.graph.sql.functions.OSQLFunctionAstar 'PriorityQueue open' and 'Set closedSet' are carried over from the last execution of the algorithm. It seems like ... ... either .clear() should be called for 'open' and 'closedSet' before each execution ... or a new instance of OSQLFunctionAstar should be created, every time the function is executed.

Misc

This is not the case with Dijkstra's algorithm, because a new instance of A* is created each time.

saeedtabrizi commented 7 years ago

Hi @martineutinger , @luigidellaquila
yes i detect some bugs in the astar function too (null checking and etc ) . i check it asap .

luigidellaquila commented 7 years ago

Thank you @saeedtabrizi, I'll check it as well

Thanks!

Luigi

saeedtabrizi commented 7 years ago

Hi @martineutinger , @luigidellaquila I fix some bugs (reported bug) and more test to astar function now . i will push it asap .

luigidellaquila commented 7 years ago

Great, thank you very much @saeedtabrizi !

Looking forward to the pr!

Thanks

Luigi

saeedtabrizi commented 7 years ago

@luigidellaquila the bugs fixed now .

martineutinger commented 7 years ago

Thank you @saeedtabrizi.

So does that mean the single-astar-instance-per-server is by design?

saeedtabrizi commented 7 years ago

Dear @martineutinger , Short answer is Yes in the current version . but i planned to add and implement some useful and more efficient path finding functions like the Block A , Hybrid A , CH , CRP for OrientDB asap . As we know path-finding algorithms is so useful to Robotic , Intelligence Traffic Management, Routing for the smart vehicle systems and some similar applications.

screenshot from 2017-01-28 12-47-17