MATLAB Answers

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

3 views (last 30 days)
Anatole Jimenez
Anatole Jimenez on 18 Dec 2019
Commented: Guillaume on 19 Dec 2019
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 Comments

Sign in to comment.

Accepted Answer

Guillaume
Guillaume on 18 Dec 2019
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 Comments

Show 5 older comments
Anatole Jimenez
Anatole Jimenez on 18 Dec 2019
This is exactly what I am looking for. Thank you Guillaume for your help.
Anatole Jimenez
Anatole Jimenez on 19 Dec 2019
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
Guillaume on 19 Dec 2019
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

Sign in to comment.

More Answers (0)

Sign in to answer this question.