MATLAB Answers

How to find all the downstream nodes from a node in a graph?

8 views (last 30 days)
Hello All,
Hope you are staying safe and doing well.
I am trying to solve a problem where I would need to figure out all the nodes going downstream from a specified node in a MatLab graph.
For example:
I have this sample code which gives me the following figure
G = graph([1,2,3,4,2,6,7,1,9],[2,3,4,5,6,7,8,9,10]);
plot(G)
Now, I need to know the number/IDs/indexes of nodes going out of node 1 towads 2 and beyond. Like, it should give me that Node 2,3,4,5,6,7,and 8 are connected to a tree branch groing out of 1. Please let me know if there is a way to figure that out.
I have tried the command OUTEDGES and successors. But they only give nodes directly connected to 1.
I would appreciate your help and ideas in this problem. Thank you.

  0 Comments

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 8 Jun 2020
Gc = G;
[eid, nid] = outedges(Gc,1);
Gc = rmedge(Gc, eid(nid ~= 2));
downstream_nodes = setdiff(unique(minspantree(Gc,'Root',1).Edges.EndNodes), 1);

More Answers (2)

Christine Tobler
Christine Tobler on 8 Jun 2020
You can call
nearest(G, 1, Inf)
which will find all nodes reachable from node 1 in an infinite radius. This will contain only the reachable nodes.

  1 Comment

Walter Roberson
Walter Roberson on 8 Jun 2020
... Though you still need to remove the (1,9) edge first; or more generally all edges from 1 that are not connected to 2
(since the user only wants to know what is "going out of node 1 towads 2 and beyond")

Sign in to comment.


Steven Lord
Steven Lord on 8 Jun 2020
You want to find all nodes reachable from 1? Those nodes have a finite distance from 1. I'm removing node 1 itself from the list (which is what D > 0 is for.)
G = graph([1,2,3,4,2,6,7,1,9],[2,3,4,5,6,7,8,9,10]);
D = distances(G, 1);
reachable = find(isfinite(D) & D > 0)
In your original graph all nodes (other than 1) are reachable from 1. Let's operate on a slightly different graph, one where there is no edge between say 7 and 8.
G2 = rmedge(G, 7, 8);
D2 = distances(G2, 1);
reachable2 = find(isfinite(D2) & D2 > 0)
In this case, 8 isn't reachable from 1.
Alternately you could ask for the connected components of G or G2 and return all nodes that are in the component containing 1.
C = conncomp(G2);
find(C == C(1)) % This will include 1

  0 Comments

Sign in to comment.


Translated by