Simple paths in path search functions

[sanyabt]

Hi @LucaCappelletti94, I've been using the centrality measures and shortest paths in ensmallen and it works great! I wanted to ask if there is any interest or plan to add simple paths to the available path functions (with cutoffs and weight options)? Such as the networkx functions all_simple_edge_paths and shortest_simple_paths.

[zommiommy]

Hi!

For the all simple paths we need to figure out first what's the best way to return an iterator from rust to python, as, for any non trivial graph, the paths won't fit in memory.

About the all simple shortest paths I'm a bit confused as I think that all shortest paths will always be single if there are no negative weight loops.

What do you think about this? Also, may I ask which is the use case for these methods?

Thanks ☺️

[sanyabt]

Hi! Sorry for the delay. You are correct that all shortest paths is single if there are no negative weight loops. The only other case I can think of is when there are multiple shortest simple paths (due to edges with same weight). My use case is for the PheKnowLator (https://github.com/callahantiff/PheKnowLator) and NP-KG (https://github.com/sanyabt/np-kg) graphs to find simple paths between disease, drug and gene nodes (as shortest paths in these graphs are not always useful to find mechanistic information and result in mostly direct edges).