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

[martineutinger]

OrientDB Version, operating system, or hardware.

• v2.2.14

Operating System

• Linux
• MacOSX
• 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(Auto discovery of databases if they are placed under $ORIENT_HOME/databases [moved] #23:19965, Auto discovery of databases if they are placed under $ORIENT_HOME/databases [moved] #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]

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

[luigidellaquila]

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

Thanks!

Luigi

[saeedtabrizi]

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

[luigidellaquila]

Great, thank you very much @saeedtabrizi !

Looking forward to the pr!

Thanks

Luigi

[saeedtabrizi]

@luigidellaquila the bugs fixed now .

[martineutinger]

Thank you @saeedtabrizi.

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

[saeedtabrizi]

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.

I'm glad if i hear from @lvca , @luigidellaquila and i create an issue for proposal path-finding .

[lvca]

+100!

[luigidellaquila]

Hi @martineutinger

I just pushed a fix for this. Thank you very much @saeedtabrizi for the contribution!

Luigi

[saeedtabrizi]

@luigidellaquila Thanks to solve the root of problem .

[santo-it]

Noted in the Release Notes