# Get path to end nodes in directed (partially cyclic) graph

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.

g=Graph[{1,2,3,4},
{DirectedEdge[1,2],DirectedEdge[1,1],DirectedEdge[2,1],DirectedEdge[2,2],DirectedEdge[2,3],DirectedEdge[2,4]},

route[g_,sp_,n_]:=Block[{ep,m,bag},
ep=Cases[{#,VertexOutDegree[g,#]}&/@VertexList[g],{_,0}][[All,1]];
m=1;bag={{sp}};
While[m<n,
bag=DeleteCases[bag,_?(MemberQ[ep,Last[#]]&&SameQ@@Take[#,-2]&)];
m++;
];
Cases[bag,_?(MemberQ[ep,Last[#]]&)]
];


You will get:

route[g, 1, 6] =
{{1,1,1,1,2,3},{1,1,1,1,2,4},{1,1,1,2,2,3},{1,1,1,2,2,4},
{1,1,2,2,2,3},{1,1,2,2,2,4},{1,1,2,1,2,3},{1,1,2,1,2,4},
{1,2,2,2,2,3},{1,2,2,2,2,4},{1,2,2,1,2,3},{1,2,2,1,2,4},
{1,2,1,1,2,3},{1,2,1,1,2,4},{1,2,1,2,2,3},{1,2,1,2,2,4}}


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];
route[g,2,17]


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

Thanks!

-
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 web.info.uvt.ro/~mmarin/lectures/GTC/c-13.pdf which is pointing in the right direction, but it only lists the shortest paths of length n. –  akm Jun 27 '13 at 12:18