Very fast algorithm for all paths between two nodes

Question

I am very new to python coding and I am looking for an algorithm that would quickly find all of the paths between a start node and end node for a very large graph - say a graph that has approx 1000 nodes and 10,000 edges. The number of paths that actually exist from the start node to the end node is small - ten or fewer. To help contextualize the question a bit more, consider a social network - If I had 1000 friends and I wanted to know how many ways my best friend from high school connect to my roommate from college, I don't care about the fact that my best friend from high school is connected to all 200 of my high school friends because those paths never lead to my roommate. What I want to do with this python code is quickly subset the paths that exist between my two friends and essentially get rid of all of the "noise" that exists around these two nodes.

I have tried to implement a number of examples of code, all of which work well on small, simple graphs. However, when I try to incorporate them into my large graph analysis, they all take too long to be useful.

Do you all have any suggestions of methods to investigate (i.e., something already created in networkx or even info on using a stack vs. recursion, etc... ), code examples to implement, or even other routes outside of python to pursue? Keep in mind, I am a python newbie.

Answer 1

Maybe you want all of the simple (no repeated nodes) paths between two nodes? NetworkX has a function for that which is based on depth-first search. See http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

The example from there shows that the number of simple paths can be large:

>>> import networkx as nx
>>> G = nx.complete_graph(4)
>>> for path in nx.all_simple_paths(G, source=0, target=3):
...     print(path)
...
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 1, 3]
[0, 2, 3]
[0, 3]