a magic all_simple_paths for a graph with 70,000 vertices and 400,000 edges

[Emerson Barea]

Hi there, I'm here again.

I'm struggling with a situation that I actually believe does not have a miracle to solve it, but come on...

I have an undirected graph with approximately 70,000 vertices and 400,000 edges and I need to know all possible paths between all vertices. I know all_simple_paths meets what I need, however, all_simple_paths uses only one core for processing, and so it will take a lot of years to achieve the expected result.

To further complicate the situation, after getting all possible paths, I need to validate those paths using a path key, since I use multigraph. So, I tried to use the command all_simple_edge_paths (networkx 2.5), which allows me to get the result that I need. but in an unfeasible computational time and cost.

Can anyone give me an idea of what I should do to be able to identify all the paths of a big graph at a viable computational cost?

Emerson

[Emerson Barea]

 Someone?

[Nicolas Cadieux]

Hi,

Difficult situation.  I also expect all simple paths will also demand lots of memory.  I had the same type of situation a resorted to using multiple one to one dijkstra. To make things faster, I break up the problem and used as many threads as you can handle.  We had over 500millions paths to calculate but I admit that the graph was smaller.  You will find the paper below.  Maybe it can be inspiration.

https://www.mdpi.com/2306-5729/5/1/8

https://gitlab.com/njacadieux/upstream_downstream_shortests_path_dijkstra

Nicolas Cadieux

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CAO1UhdVw6me4Nq17cpVeOgfLUWzpg-Uk7AcQWE_-TL-j4C%3DrWw%40mail.gmail.com.

[Emerson Barea]

Thank you Nicolas. Every information or suggestion is very welcome. I'll look closely at your code to see if I can get any central ideas that help me.

Thank you.

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/e46c678f-11dc-b3b6-fcba-dae017c65d19%40gmail.com.

[Zahra Sajjadi]

Hi

I have this question  too.

--

[Zahra Sajjadi]

I have this question too!

On Tue, Sep 29, 2020, 7:14 PM Emerson Barea <emerso...@gmail.com> wrote:

--