Lazy traversal

[dunyakirkali]

Does it make sense to allow pathfinding in a lazy way? Where the nodes and the edges can be added whilst traversing.

Or is this a silly idea?

[zachallaun]

Wondering if there was ever some additional thought put into this. The idea certainly makes sense and is applicable to a number of pathfinding problems where the graph is only being used as an intermediate/normalized representation to enable pathfinding.

[dunyakirkali]

TBH with you, I personally haven't put much thought into the how. It was just something that I missed with libgraph so I put it here as a reminder to myself (for if I ever have time to work on it) or for anyone else (who might be looking for a good first issue)

[zachallaun]

Very understandable! This was a feature I was personally looking for just now and found this issue while looking to see whether anyone had brought it up.

I might be able to contribute, but I'd need a bit more direction on a desired API. I'm likely going to create a simple version based on the current a_star implementation and will post here if I come up with anything that might be generally applicable.

[zachallaun]

So, as mentioned, I had a problem that I wanted to apply lazy pathfinding to and I finally got around to it this morning. You can find a stripped down version of pathfinding.ex here -- for my purposes, I only needed djikstra/a-star.

The difference in speed between using this implementation and eagerly constructing the graph is many orders of magnitude for my particular use-case (3000+ to 1ms for certain test cases), but I believe that's actually because of an additional optimization/fix I included after profiling the eager implementation currently in Graph.Pathfinding. In particular, for vertices containing relatively large values (e.g. nested data structures), a huge amount of time is spent calculating the vertex id using :erlang.phash2/1.

I'd like to do some more targeted profiling/benchmarking separate from my particular use-case, but the link above may be a helpful jumping off point if a lazy pathfinding implementation is desired in libgraph.

[zachallaun]

For the purposes of potentially adding something like this to libgraph, two decisions I made in my implementation that would need buy-in:

1. lazy_dijkstra and lazy_a_star return {graph, path} or nil (instead of path or nil). This allows reusing or querying the lazily-constructed graph after pathfinding has completed. It might make more sense to return {:ok, graph, path} or {:error, graph}, since much of the graph may still be computed even when no path can be found.
2. Lazy pathfinding functions take a next_fun which serves both to generate the next state of the graph and determine when pathfinding should stop. The function takes the current graph and vertex under consideration and returns either {:cont, graph} to continue searching or :halt to indicate the correct vertex has been found. An alternative would be to accept two functions, one to compute the next graph and one to check whether the target has been reached.