Take the 2-minute tour ×
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.

graph

g=Graph[{1,2,3,4},
{DirectedEdge[1,2],DirectedEdge[1,1],DirectedEdge[2,1],DirectedEdge[2,2],DirectedEdge[2,3],DirectedEdge[2,4]},
{GraphLayout->"SpringEmbedding",ImagePadding->20,VertexLabels->{"Name"},VertexLabelStyle->{Directive[RGBColor[1,0,0],Bold,20]}}];

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=Flatten[Thread[Append[#[[1]],#[[2]]]]&/@(Thread[List[bag,(VertexOutComponent[g,Last[#],1]&/@bag)]]),1];
    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!

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 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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.