Home > graphs and networks > How to find all vertices reachable from a start vertex following directed edges?

# How to find all vertices reachable from a start vertex following directed edges?

April 27Hits:1

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, ...}. ?

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]:= [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */[Flatten[List@@@edges]];
In[115]:= g=Graph[vertices,edges];
In[116]:= {#,VertexOutComponent[g,{#}]}&[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> *///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[].

Perhaps something like this?

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};

GraphPlot[edges, DirectedEdges -> True, VertexLabeling -> True]



connected[edges_][v_] :=
Module[{f},
f[x_] := (f[x] = {}; f[x] = # ⋃ Flatten[f /@ #]& @ ReplaceList[x, edges]);
f[v]
]

connected[edges][2]


{4, 5, 7, 8, 9, 10}



On large graphs it will be advantageous to convert the edges to a Dispatch table.

Calculation and return of all connections as an Association:

allConnected[edges_] :=
Module[{a = <||>, f},
f[x_] := (a[x] = {}; a[x] = # ⋃ Flatten[f /@ #] & @ ReplaceList[x, edges]);
f ~Scan~ Union @ Keys[edges];
KeySort @ a
]

allConnected[edges]


<|1 -> {3, 4, 5, 6, 7, 8, 9, 10}, 2 -> {4, 5, 7, 8, 9, 10}, 3 -> {5, 8, 9, 10},
4 -> {9, 10}, 5 -> {10}, 6 -> {7, 8, 9, 10}, 7 -> {8, 9, 10}, 8 -> {9, 10},
9 -> {10}, 10 -> {}|>


allConnected[edges] ~Lookup~ {6, 4}


{{7, 8, 9, 10}, {9, 10}}



Adapting this answer for finding the transitive closure of a symmetric binary relation (and dropping the symmetry property):

 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};

pairs = edges /. Rule -> List;
m = [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */;
(*the adjacency matrix of atomic elements in pairs:*)
SparseArray[pairs~Append~{i_, i_} -> 1, {m, m}];
(* find the transitive closure:*)
[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */@MatrixPower[N@%, m];
(* find labels of reachable vertices  *)
Join @@ Position[#, 1] & /@ %
(*==> {{1, 3, 4, 5, 6, 7, 8, 9, 10}, {2, 4, 5, 7, 8, 9, 10},
{3, 5, 8, 9, 10}, {4, 9, 10}, {5, 10}, {6, 7, 8, 9, 10},
{7, 8, 9, 10}, {8, 9, 10}, {9, 10}, {10}}  *)
(* organize: *)
Grid[{First@#, Rest@#} & /@ %, Alignment -> Left]



Note: As is, this works for cases where the vertex list is a range of contigous integers. For a general graph g where vertex list is an arbitrary set, one can work with the set of vertex indices VertexIndex[g,#]&[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */[g].

Yet another way using GraphDistanceMatrix:

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};



If

mygraph = [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */;
vertex = [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */;
graphdist = [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */;



then

{vertex, Pick[##, Except[_List | Infinity | 0]] & @@@
Thread[{vertex, graphdist}, List, {2}]} // Transpose // Sort // Column



returns

{1,{3,4,5,6,7,8,9,10}}
{2,{4,5,7,8,9,10}}
{3,{5,8,9,10}}
{4,{9,10}}
{5,{10}}
{6,{7,8,9,10}}
{7,{8,9,10}}
{8,{9,10}}
{9,{10}}
{10,{}}



## Related Articles

• ### How to find all vertices reachable from a start vertex following directed edges?April 27

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

• ### Is there a function or tool that will add vertices to polylines where endpoints are snapped to edges? (ArcMap)November 16

My friend and I are creating a walking network, and we have been having issues getting the routing to work. We just realized that the reason why our routes are messed up is because we snapped our routes to edges as well as endpoints. The routing work

• ### Merging Vertices of a Graph and adding up the edges weightsOctober 3

I have a Weighted Graph of g which looks like this. vertex = {a, b, c, d, e} SeedRandom[1] g = Graph[#[[1]] -> #[[2]] & /@ Permutations[vertex, {2}], VertexLabels -> Placed["Name", Center], VertexSize -> 0.3, EdgeWeight -> Random

• ### Enable mouse scrollbar and fix vertical scrollbar in Codemirror 3.23 when direction is changed to rtlFebruary 11

I want to change my text direction based on language. Everything worked fine when it is LTR but as soon as it is switched to RTL then there are two vertical scrollbars in codemirror's textarea. When I remove the overflow-y: scroll then my mouse scrol

• ### Efficiently or Elegantly construct linear graph list from vertex pairsFebruary 20

I am processing MRP data, with BOM relations as pairs of part number strings. I want to construct lists that represent the linear graphs defined by these pairs. Here is some code to generate random sample data, with real-world distribution of lengths

• ### Identifying the trianglesFebruary 20

Counting the amount of triangles in a picture is a task commonly used in brain tests. You are given a picture that contains shapes consisting of triangles. You then must find all possible triangles in the picture. Task You are given a list of lines i

• ### 3Ds Max is exporting model with more normals than verticesMarch 22

I made a simple teapot with the "Create Standard Primitives" option and exported it as a collada file, ended up with this: < float_array id="Teapot001-POSITION-array" count="1590"> < float_array id="Teapot001-No

• ### Finding all shortest paths between two verticesApril 11

The built-in FindShortestPath and GraphDistance functions find the shortest path between two particular vertices in a graph. I can't think of a simple way to finding all shortest paths between two vertices. Any ideas? My graph has weighted edges and

• ### How to draw a directed graph with arrows showing vertically from bottom to topMay 7

If I have a directed graph, how can I draw it with arrows pointing vertically from bottom to top, like showing a class inheritance pattern in OOP(object oriented programming)? --------------Solutions------------- You'll need to use LayeredGraphPlot.

• ### Ordering vertices in GraphPlotSeptember 18

I'm new here, so forgive me if this question is not well-posed/duplicates an earlier question - although I've searched for similar questions without success. I'm trying to present a plot of connections between elements (correlations between student p

• ### Create bullet physics rigid body along the vertices of a blender modelJuly 2

I am working on my first 3D game, for iphone, and I am using Blender to create models, Cocos3D game engine and Bullet for physics simulation. I am trying to learn the use of physics engine. What I have done I have created a small model in blender whi

• ### Geometry Shader input vertices orderFebruary 9

MSDN specifies (link) that when using triangleadj type of input to the GS, it should provide me with 6 vertices in specific order: 1st vertex of the triangle processed, vertex of an adjacent triangle, 2nd vertex of the triangle processed, another ver

• ### Can I change the options of an individual vertex in \Vertices?February 18

Consider the following code that produces vertices on a line. \documentclass[12pt,a4paper]{article} \usepackage{tkz-graph} \begin{document} \begin{figure} \begin{tikzpicture} \GraphInit[vstyle=Classic] \tikzset{VertexStyle/.append style = {minimum si

• ### How can I find the "end" vertices on an open-ended mesh?June 16

I was looking at a video of a system that extrudes meshes along a curve, connecting them end to end but adjusting the vertices for a smooth connection. It does this with a mesh that as far as I know is guaranteed to have open ends that are later capp

• ### How to plot a graph from its adjacency matrix and coordinates of vertices?September 20

A similar question is here. If we give all the data of the vertices's coordinates and the graph's adjacency matrix, how to plot it with tikz, pstrick or other tool in tex? here are the data of adjacency matrix and coordinates Coordinates:{{0.809,0.58

• ### Using GraphData to generate all directed graphs with n verticesFebruary 7

Using Combinatorica, it was possible to generate unlabeled (non-isomorphic) directed graphs of $|V|=n$. Here the example is for $n=4$: Needs["Combinatorica`"] ShowGraph /@ ListGraphs[4,Directed]; Using GraphData, I know how to generate undirecte

• ### How to find all possible paths with as many edges between two same vertices?October 9

Suppose I have an undirected graph G = Graph[{1 <-> 2, 2 <-> 3, 2 <-> 3, 3 <-> 4}] I used FindPath[G,1,4,Infinity,All] and obtained the result {{1, 2, 3, 4}} But the expected result is {{1, 2, 3, 4}, {1, 2, 3, 4}} Is there any way

• ### Graph Interface: Storing Vertices in an Array vs HashTableNovember 17

I have just started learning graph algorithms and am trying to arrive at an ideal interface. I understand that this code will not be used anywhere else (I will certainly use Boost::Graph) but I just want to make sure that what I am writing is not com

• ### Maximal sum of unique vertices' weights in a grapJanuary 26

I'm given a directed graph with weights assigned to vertices, not edges. My goal is to find the maximal weight of a path in this graph. A path's weight is a sum of weights of all unique vertices it contains. A vertex may be visited multiple times on

• ### Prevent div from expanding vertically, give it scrollbarJanuary 31

Refer to the following fiddle: https://jsfiddle.net/537w3qsn/ Here's what I want: The header and footer should remain visible on the page at all times. The body (green div in the middle) should get a vertical scrollbar if it would otherwise cause con