How can I get the root node of a given node from a directed graph ?

Question

Anatole Jimenez 2019-12-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/497271-how-can-i-get-the-root-node-of-a-given-node-from-a-directed-graph

评论： Guillaume 2019-12-19

采纳的回答： Guillaume

Hello,

I am using graph for image processing, 1 node = 1 pixel.

I computed the graph but I need to find for each node its root node.

Is there any function or a quite performant solution as the number of nodes is quite high ?

Thank you,

Anatole Jimenez

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Guillaume 2019-12-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/497271-how-can-i-get-the-root-node-of-a-given-node-from-a-directed-graph#answer_406957

在 MATLAB Online 中打开

the first element of the vector returned by toposort would be your root node. Of course, your graph must be acyclic and if your graph has several roots, this will only be one of them.

Perhaps easier would be to look in the edge table and find which nodes don't appear at all as target nodes. Assuming the Nodes table is empty:

rootnodes = setdiff(1:height(yourgraph.Nodes), yourgraph.Edges.EndNodes(:, 2))

8 个评论
显示 6更早的评论隐藏 6更早的评论

Guillaume 2019-12-18

编辑：Guillaume 2019-12-18

在 MATLAB Online 中打开

What are you calling a root node?

When I look at one of the subgraph of your graph:

bins = G.conncomp('OutputForm', 'cell', 'Type', 'weak');
plot(G.subgraph(bins{1}))

I get this:

Node 1 has nodes 20, 21, 22, 23, 3, 4, 5, 10,15 as roots.

edit: perhaps what you call a root is node 1 in the above graph, in which case either your graph is directed the wrong way or you're using the wrong terminology. I'm not sure what the correct term actually is, but it is something like a sink or a terminal

Anyway, it doesn't matter much if you're looking for roots instead of terminals. Simply replace outdegree by indegree for roots in the code below

bins = G.conncomp('Type', 'weak');  %since the graph is DAG all components are weakly connected
terminalidx = find(G.outdegree == 0);  %which nodes are terminal
assert(numel(unique(bins(terminalidx))) == numel(terminalidx), 'At least one subgraph has more than one terminal') %optional check
matchingterminal = terminalidx(bins);  %replicate terminal index in each bin

matchingterminal(n) gives you the index of the terminal node for node n.

Anatole Jimenez 2019-12-19

I just tried what you submit but It didn't work.

The bins from the G.conncomp('Type', 'weak') property are not sort with the terminalidx from find(G.outdegree == 0).

By example the node 6 has the node 1019 as terminal but the bins(6) is 2 and terminalidx(2) = 11.

I think bins number are not terminalidx index.

Guillaume 2019-12-19

在 MATLAB Online 中打开

Indeed, I made an assumption that the terminals would be in the same order as the bins, which is generally incorrect. Fixed code:

bins = G.conncomp('Type', 'weak');  %since the graph is DAG all connections are weak
terminalidx = find(G.outdegree == 0);  %which nodes are terminal
terminalbin = bins(terminalidx)
assert(isequal(unique(terminalbin), 1:numel(terminalbin)), 'At least one subgraph has more than one terminal') %optional check
[~, termorder] = sort(terminalbin);  %find ordering of terminals according to the bin they're in
terminalidx = terminalidx(termorder);    %and reorder them accordingly
matchingterminal = terminalidx(bins);  %replicate terminal index in each bin

Note that I would store all this information, together with the nodes X and Y location into the node table:

G.Nodes.Isterminal = G.outdegree == 0;
G.Nodes.MatchingTerminal = matchingterminal;
G.Nodes.Subgraph = bins;
G.Nodes.X = ???  %Nx1 column vector
G.Nodes.Y = ???  %Nx1 column vector

which makes for easy plotting

plot(G, 'XData', G.Nodes.X, 'YData', G.Nodes.Y, 'NodeCdata', G.Nodes.IsTerminal+1);  %to highlight the terminals

请先登录，再进行评论。

How can I get the root node of a given node from a directed graph ?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

8 个评论
显示 6更早的评论隐藏 6更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

Community Treasure Hunt

How can I get the root node of a given node from a directed graph ?

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

8 个评论 显示 6更早的评论隐藏 6更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

Community Treasure Hunt

WeChat

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

8 个评论
显示 6更早的评论隐藏 6更早的评论