Message Boards Message Boards

GROUPS:

Get all possible simple paths between two nodes in a large network?

Posted 1 year ago
1701 Views
|
1 Reply
|
1 Total Likes
|

I have written down a code that finds all possible simple paths (not repeating the same vertex and not duplicating the same path) between two nodes in a undirected graph in terms of vertices not nodes.

The code works very well for small networks. However, it doesn't function for large networks and keeps running forever.

Attached my code.

Attachments:

Hello Nehal!

I read your code, and I concluded that it's the problem is about complexity, let me explain to you why is that happening...

First, is that your graph is undirected, so there are more possible paths than an equal directed graph. The problem is that when you call FindPath[] with Infinity in an undirected graph, it takes too much for it to process all the possible paths with no limits to the length.

I've created a visualization for the time it takes for processing the paths between node zero and five, with the maximum length from 5 to 28.

As you can see, there's an exponential pattern in the maximum length of the path, and the time it takes for processing. And since you are using Infinity, it will find ALL possible paths from one node to another, without considering a maximum length.

One solution is to reduce the maximum length to some proportional minimum value.

Looking forward to reading your reply!

Pedro Cabral.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract