Geek Answers Handbook

Very fast algorithm for all paths between two nodes

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

I tried to implement a series of code examples, all of which work well on small simple graphs. However, when I try to include them in my large graph analysis, they are all too long to be useful.

Do you have any suggestions on research methods (i.e. something already created in networkx or even information on using the stack against recursion, etc.), code examples for implementation or even other routes outside of python to pursue ? Keep in mind, I'm new to python.

+8
python graph nodes
source share
2 answers

Perhaps you need all the simple (non-repeating nodes) paths between two nodes? NetworkX has a feature for that which is based on a depth search. See http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html

An example from here 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]
+3
source share

Personally, I would recommend using a graph database for this. Neo4j or Rexter spring.

When accessing them with Python, several libraries are available:

Although it would be impossible to write a fast / scalable version of Python, now I do not know how much I know.

+1
source share

More articles:


All Articles