Orientdb: [PROPOSAL] Add some useful path finding algorithm as sql functions like the ( Block A* , Hybrid A* , CH , CRP ) to OrietntDB

[saeedtabrizi]

As we discussed in https://github.com/orientechnologies/orientdb/issues/7103#issuecomment-275836380 , we know path-finding algorithms is so useful to Robotic , Intelligence Traffic Management, Routing for the smart vehicle systems and some similar applications.

OrientDB currently (v2.2.15) supports the Shortest Path , Dijkstra , A* (a star) algorithms . but we can add some other useful path finding to orientdb now .
OrientDB is a multimodel database that supports graph functionalities . so we must have access to wide range of algorithms to working with the graphs .
I recommend to implementing Block A , Hybrid A , CH , CRP path finding functions too .
The following Chart gives a compare some popular path finding algorithms :

Implementation and tasks for :

• [ ] Block A*
• [ ] Hybrid A*
• [ ] CH
• [ ] CRP

Welcome to comments .

[lvca]

It would be awesome!

[lvca]

@saeedtabrizi have you had the chance to work on this?

[saeedtabrizi]

@lvca sure . i have wrote some lines of code to implement it . but i should complete it asap. I will push it in the next week .

[lvca]

Awesome, thanks!

[saeedtabrizi]

Hi @lvca i have some question for implementing CH that be one of fastest routing algorithms :
As we know for decrease the cost of routing in huge routing request handling problems like the Bing maps or google maps or OSM services , CH algorithm makes _precomputed_ cost shortcuts between the vertex and finally execute a Dijkstra over the shortcuts and main graph data.
So according to Wiki of CH algorithm for implementing CH we have the following phase :

• A) Preprocessing :
  
  
  
  • Compute traveling cost between nodes and build shortcuts .
  
  
  • Put shortcuts to a local cache for next re usability . (Be or not to be , this is my question)
  
  
• B) Querying :
  
  
  
  • Execute a Dijkstra over the shortcuts to find the cheapest cost .
  
  

So please tell your idea for implementing a local cache for computed shortcuts .
I can make a named Index or Class to store the shortcuts or using the OrientDB internal caching mechanism or make an custom caching mechanism for it.
Which would better and faster for my scenario ? please help me .
I prefer to make a named Class for ease of use and implementing .
The first syntac for CH function is :

ch(<sourceVertex>, <destinationVertex>, <weightEdgeFieldName>, [<options>]) 
 // options  : {direction:"OUT",edgeTypeNames:[] , shortcutClassName:"MyMapShortCuts", updateShortcuts:true,rebuildShortcuts:true,resultsLimit:3} 

Thanks
Saeed Tabrizi

[lvca]

I like the idea of using a class for caching, so it would be persistent and the user can choose the class name. Also, the signature seems good. So +1 for me.

[saeedtabrizi]

If there is not any more comment about it , i just starting to finalize implementation .

[lvca]

+1

[saeedtabrizi]

Hi @lvca , I start this issue implementation to compatible for ODBv3 .
Just i try to make a compatible version very soon (maybe in the next week) .