knutwalker
commented
2 years ago Hi @dmbianco
thanks for the request. It's a good idea and we have added the feature to our backlog, at least for the Dijkstra-based ones, that you also mentioned. I can give no ETA on when we are starting the work on that, though.
If you like - since you already did some changes on the code - you can also contribute you code under the contribution guidelines, and we can help you clean it up.
Path finding algorithms can be very slow if graph contains millions of nodes and relationships. Consider Yens algorithm, it is computationally expensive since it should "explore all paths" from source to target; however, in most business contexts, too long or too costly paths are not interesting and are nonetheless discarded ex-post.
I suggest to add two new parameters to path finding algorithms (at least Dijkstra source-target, Dijkstra single source, Yens): max cost and max path length. In this way, one could be able to filter out irrelevant paths during computation. Implementing this parameters could reduce dramatically computation time taking advantage of business constraints.
I have patched GDS library adding these parameters to SourceNodeConfig (for simplicity, it is not the best implementation) and hours have become minutes in our path finding applications in a graph with 10 million nodes and 100 million relationships. This two parameters are very simple to add and could transform a global and too expensive research into a local and fast one. The complete patch requires to change HugeLongPriorityQueue so that it can store path lengths and Dijkstra so that nodes are not added to queue if they are "too far" from source.
Finally, I think this new features will allow your customers to run path finding algorithms even on big graphs where "local" connections are fundamental and this will allow them to exploit business constraints reducing compute time.