graphs and networks - How to find all vertices reachable from a start vertex following directed edges?
How to find all vertices reachable from a given start vertex following directed edges, in a cyclic directed graph given as
Graph[{v1, v2, ...},
{v1 -> v11, v1 -> v12, ..., v2 -> v21, v2 -> v21, ..., vn -> vn1, vn -> vn2, ...}]
where all the ending vertices of edges vij are in the list of vertices {v1, v2, ...}. ?
Answer
One can use VertexOutComponent[] to find all the vertices connected to a given vertex in a directed graph:
In[107]:= edges={1->3,1->4,2->4,2->5,3->5,6->7,7->8,8->9,9->10,6->10,1->6,2->7,3->8,4->9,5->10};
In[114]:= vertices=Sort@DeleteDuplicates[Flatten[List@@@edges]];
In[115]:= g=Graph[vertices,edges];
In[116]:= {#,VertexOutComponent[g,{#}]}&/@vertices//Grid
Out[116]= 1 {1,3,4,5,6,7,8,9,10}
2 {2,4,5,7,8,9,10}
3 {3,5,8,9,10}
4 {4,9,10}
5 {5,10}
6 {6,7,8,9,10}
7 {7,8,9,10}
8 {8,9,10}
9 {9,10}
10 {10}
It should work for any directed graph whether it's acyclic or not. The analogue of VertexOutComponent[] for undirected graphs is ConnectedComponents[].
Comments
Post a Comment