all_pairs_all_simple_paths hanging for 100-node graphs

[miamico]

Information

• rustworkx version:
• rustworkx==0.17.1
• Python version: 3.10.16
• Rust version: rustc 1.78.0
• Operating system: MacOS

What is the current behavior?

Running all_pairs_all_simple_paths hangs indefinitely, using huge amount of processing.

What is the expected behavior?

It should complete in a few seconds

Steps to reproduce the problem

from rustworkx import all_pairs_all_simple_paths, directed_gnp_random_graph

graph_100 = directed_gnp_random_graph(100, 0.6, seed=None)

simple_path_pairs = all_pairs_all_simple_paths(graph_100)

[jakelishman]

It's dependent on the structure of the graph, but just very loosely and empirically, the total size of the output alone is going as like $\propto 5.7^{\text{node count}}$ for the graphs you're after. At 100 nodes you're looking at an output size like $10^{74}$ entries.

[miamico]

I have encountered the issue in the context of finding a 100q chain on a heron device. It had been working in the past but it's now hanging indefinitely. The heavy hex topology should be more tractable compared to the random graph above