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

19 次查看（过去 30 天）
Mohammad Asif Iqbal Khan
评论： Christine Tobler 2022-4-1
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.

请先登录，再回答此问题。

采纳的回答

Walter Roberson
Walter Roberson 2020-6-8
Gc = G;
[eid, nid] = outedges(Gc,1);
Gc = rmedge(Gc, eid(nid ~= 2));
downstream_nodes = setdiff(unique(minspantree(Gc,'Root',1).Edges.EndNodes), 1);
  3 个评论
显示 1更早的评论
AKHILESH BARNWAL
AKHILESH BARNWAL 2022-3-22
This code generate node IDs downstraem nodes beyond Node 1.
If I have to find node IDs downstraem nodes beyond Node 2 or 6 what should changes we make?
Walter Roberson
Walter Roberson 2022-3-23
编辑：Walter Roberson 2022-3-23
Ran in:
G = graph([1,2,3,4,2,6,7,1,9],[2,3,4,5,6,7,8,9,10]);
plot(G)
Gc = G;
[eid, nid] = outedges(Gc,2)
eid = 3×1
1 3 4
nid = 3×1
1 3 6
downstream_nodes = setdiff(nid, 1) %remove the backlink to 1
downstream_nodes = 2×1
3 6

请先登录，再进行评论。

更多回答（3 个）

Christine Tobler
Christine Tobler 2020-6-8
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 个评论
Walter Roberson
Walter Roberson 2020-6-8
... 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")

请先登录，再进行评论。

Christine Tobler
Christine Tobler 2022-3-23
Ran in:
Looking at this again due to the recent comment added, it might be simpler to use a directed graph instead of an undirected one: This way, the concept of "downstream" is represented by "following the arrows".
G = digraph([1,2,3,4,2,6,7,1,9],[2,3,4,5,6,7,8,9,10]);
plot(G)
nearest(G, 1, Inf)
ans = 9×1
2 9 3 6 10 4 7 5 8
nearest(G, 2, Inf)
ans = 6×1
3 6 4 7 5 8
nearest(G, 6, Inf)
ans = 2×1
7 8
  3 个评论
显示 1更早的评论
Christine Tobler
Christine Tobler 2022-4-1
Ran in:
Assuming we agree "downstream" means "in the direction of the edges of this digraph", the nodes are already returned by the nearest function above. As Walter mentioned, I'm also assuming that you have no cycles in this directed graph, like is the case for your example.
For edges / branches, it's not as straightforward, the easiest is probably to just get all edges connected to one of the downstream nodes:
G = digraph([1,2,3,4,2,6,7,1,9],[2,3,4,5,6,7,8,9,10]);
plot(G, 'EdgeLabel', 1:numedges(G))
node = 2;
downstreamNodes = nearest(G, node, Inf)
downstreamNodes = 6×1
3 6 4 7 5 8
downstreamEdges = outedges(G, node);
for ii=1:length(downstreamNodes)
downstreamEdges = [downstreamEdges; outedges(G, downstreamNodes(ii))];
end
downstreamEdges
downstreamEdges = 6×1
3 4 5 7 6 8

请先登录，再进行评论。

Steven Lord
Steven Lord 2020-6-8
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

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by