In a (possibly directed) graph, is there a simple way to find all nodes reachable for a given node?

I've recently started working with MATLAB graphs. In two recent problems, I have graphs which are not known to be connected every node to every other node. Is there a way to determine in one or a known number of steps, the set of nodes which can (or cannot would work) be reached from a specified node? I've encountered this question both with undirected (small, and I powered through) and now undirected nodes.

Just in case I'm in asking an XY question, my current directed graph is entirely unidirectional; there are no closed loops. I could trivially assign a value to each node, and know that every edge leads to a node with a strictly larger value than the node it leads from. To be even more specific if it helps, though I definitely don't know the proper math language: the graph represents a double elimination playoff bracket, and I want to put together the possible routes for each seed on a plot to guide teams through the process, pruning out things that don't matter to that team. Fortunately in this case, the graph is deterministic; no re-seeding occurs due to match outcomes, making such a plot useful.

My previous issue, which was small so I powered through, had an undirected graph, and I really just wanted to know whether or not the graph was continuous; that is, whether every node pair was connected by some path.

[GeeTwo]

I solved the problem and posted the solution where I trust it will make lives a bit easier. :

I didn't use MATLAB for the presentation, but I gave due credit.

https://www.chiefdelphi.com/t/a-map-for-double-eliminations/498239

Answer 1

[John D'Errico]

First, create a graph.

M = eye(100) + triu(rand(100) < 0.035);
spy(M)

You will agree this matrix satisfies the requirements, in the sense that node 1 can possibly talk to only nodes below node 1, and down the line. If it bothers you that the matrix representing the connections is purely upper triangular, I could randomize the matrix, but that does nothing except rename the nodes. Node 1 could have any name or number you want to assign to it.

G = digraph(M)

G = 
  digraph with properties:

    Edges: [272x2 table]
    Nodes: [100x0 table]

plot(G)

Now, the question was asked, if everything can communicate in this graph. Here, clearly, just a plot of the graph shows that will fail, because some nodes are obviously disconnected from the rest.

I think conncomp could possibly help here, but for it to do what I want, I need to have a symmetric graph matrix.

Gs = graph(M + M');
CC = conncomp(Gs);
unique(CC)

ans = 1×3

1 2 3

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

And this tells me there were multiple distinct groups which did not talk to each other. I suppose I could have done this too:

SP1 = shortestpathtree(G,1)

SP1 = 
  digraph with properties:

    Edges: [7x2 table]
    Nodes: [100x0 table]

plot(SP1)

So at the top of the tree is node 1. And we see that some nodes can be reached from node 1, but there were many nodes which were unreachable, shown off to the side on the top row.

[GeeTwo]

I was not familiar with conncomp(), thanks for that, but it won't help with my current problem, because it would show nothing using a directed graph and everything if undirected either the way you did it or more easily with conncomp(g,'Type','weak').

However, It could quickly solve by former problem! is_conn = @(g)all(conncomp(g)==1)

************

The shortestpathtree() seems more promising...YES! For my little problem where I won't deal with exceptions in code, the following function to extract the subgraph of g including only node start and those reachable from start does exactly what I need:

subg_from = @(g,start)subgraph(g,unique(shortestpathtree(g,start).Edges.EndNodes))

Thanks, John D'Errico!

Answer 2

[Christine Tobler]

The quickest way to find all nodes reachable from a given node is using the nearest function with Inf as the distance:

g = digraph([1 1 1 2 2], [2 5 6 3 4]);
plot(g)

●

node = 1;
distance = Inf;
nearest(g, node, distance)

ans = 5×1

2 5 6 3 4

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

This returns the nodes sorted by the distance from the original node.

Also, the allpaths method returns all paths between two nodes.

[GeeTwo]

Thanks! I solved my problem last night, but I solved it again this morning using your suggestion: subgraph(nearest(g,start,Inf)). The difference is that the start node was not returned. The plot of the resulting subgraph was closer to how I presented my answer, though it was not as clear from the plot where to start.

[John D'Errico]

Hi @Christine Tobler,

Please answer more questions. Whenever you do, I ALAYS learn something useful!