hi There first time poster I am using the function get_all_simple_paths and I notice a significant speed issue with graph and nodes > 600.
I simplify my graph before usage. I’m using python 3.7 and installed using conda.
Is there a way to get speed improvements? or somehow use the C version with python. BTW is the python or cython code for igraph multi-threaded?
As stated in the documentation,
Note that potentially there are exponentially many paths between two vertices of a graph, especially if your graph is lattice-like.
In other words, it is entirely expected that as the size of the graph increases, you will hit a performance wall. A faster implementation is not likely to help much for such problems. “Brute-force” approaches to speedup, such as faster computers or parallelization definitely would not help. It would only make make slightly larger graphs feasible.
I am not familiar with the specific implementation used in igraph, and how much better one can get. Perhaps better implementations are possible. My point is that since the number of results is exponentially large, no algorithm will be better than exponential—all of them will hit a performance wall at some graph size.
The Python interface of igraph exposes the function implemented in the C core. You are already using it.
Thank you for the reply I see and that does make quiet a bit of sense. I’m not an expert in graphs do you or does anyone (broadcasting request for any passer bys) know of a way to reduce my graph to make it more simpler.
In the documentation it says it may run out of memory when calculating get_all_simple_paths.
A decent idea might be to use tempfile to push the paths to disk then load back up at the end before returning them. It’ll help to minimize peak memory usage.
just curious if I wished to make the function multi-threaded can someone provide any insight on that before I look into it
Hi Ravi,
Caching to disk, multicore etc. are all feasible but not interesting for most users, so we can’t easily spend our time on them.
By any means, if you need it and want to code a parallelized version, feel free to get started and ask questions along the way.
Cheers,
Fabio