search

AnacletoLAB / ensmallen

🍇 Ensmallen is the Rust/Python high-performance graph processing submodule of the GRAPE library.
MIT License
39 stars 12 forks source link

Simple paths in path search functions #195

Closed sanyabt closed 4 months ago

sanyabt commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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).