Sign up ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a large directed graph containing small loops. I would like to extract all paths to all end nodes (no VertexOutComponent) with a given path length $n$. I have written a function which works, but I would like to know if anybody knows a more "elegant" and sufficient way to perform this task.

Please see my minimum working example and the function I am using. In this case, vertices 3 and 4 are end nodes.




You will get:

route[g, 1, 6] =

All routes are 6 steps long and end in vertices 3 or 4. Is there a build-in function or any other code I can use to get this output efficiently? My real world data are graphs containing approx. 80 vertices, 5 to 10 loops with 5 to 10 vertices and 5 to 10 end nodes.

You can try:

SeedRandom[1];g=RandomGraph[{80, 120}, DirectedEdges->True];

which gives a list of 110807 routes in 16 seconds (on my PC).


share|improve this question
After some reading I found that the MatrixPower of the 'AdjacencyMatrix` will give the total number of paths to the end nodes, so in this case: MatrixPower[AdjacencyMatrix[g], 5]={{16, 16, 8, 8}, {16, 16, 8, 8}, {0, 0, 0, 0}, {0, 0, 0, 0}}; there are 8 paths to end node 3 and 8 paths to end note 4, each 6 steps long. Now I just need to get all these paths... – akm Jun 27 '13 at 11:25
I found this lecture which is pointing in the right direction, but it only lists the shortest paths of length n. – akm Jun 27 '13 at 12:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.