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

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

Answer 1

[Guillaume]

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))

[Anatole Jimenez]

Thank you for your answer.

Indeed, my graphs are acyclics but have many roots.

Unfortunately, listing all the nodes is not my request. What I want is to associate each nodes with its root node. Something like : rootnode = getRootNode( myGraph, node )

Attached a figure of one of my graphs.

[Guillaume]

The graph object would be more useful than the figure.

Some of your nodes have more than one root, what should be returned then?

[Anatole Jimenez]

I computed the graph such that there is only one root per node. It is based on descending variance graph, (article).

I feel like matlab graphs are not adapted to image processing.

Attached you will find the graph.

[Guillaume]

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]

Sorry for the misunderstanding, by root node I meant the node 1. I agree that the direction of the edges can be misleading.

My graphs are supposed to link each nodes to its minimum neighbor, in order to group the nodes to a local minimum, here the node 1. I would like to have something like :

node1 = get_root_node( myGraph, node17 )

Thank you again for your time.

[Anatole Jimenez]

This is exactly what I am looking for. Thank you Guillaume for your help.

[Anatole Jimenez]

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]

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