[Solved]: Finding all paths with lengths in a fixed interval in sparse graphs

Problem Detail: 

What is the most efficient way to find all paths of length M to N in a large sparse graph?

Some general information:

• Graph has 30,000 to 50,000 nodes
• Average number of edges per node ~ 10
• M=4, N=7
• Graph has cycles

Asked By : Andrew S.

Answered By : zvisofer

Assuming a directed graph.

Paths of length $1$ are simply the edges.

paths of length $i+1$:

Unite on all nodes $v \in V$ {concatenate all paths of length $i$ that end with $v$ with all paths of length $1$ that start with $v$}.

repeat for $i=1$ to $7$.

Note that this method avoids redundancies, so you don't need to check for them.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21381