MATLAB: How to get the root node of a given node from a directed graph

digraphdirected graphgraphMATLABnode

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

Best Answer

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

Related Solutions

MATLAB: Delete and add new edges in a graph

A graph object is undirected. A digraph object is directed.

Construct your network graph using digraph instead of graph on the fourth line of your code.

By the way, the addedge function has two capabilities you might find useful.

The s (source) and t (target) inputs can be vectors to add multiple edges at once.
If the source and/or target inputs reference nodes that don't yet exist, addedge adds them.

So you could do this with something like:

% Make a digraph and plot it for later reference
G = digraph(triu(ones(3)));
figure;
plot(G)
% How many nodes does G have?
N = numnodes(G);
% Add 2 new nodes
newnodes = [N+1 N+2];
% Add the edges between 1 and N+1, N+1 and N+2, and N+2 and 2
%

% I'm doing this in a copy of G, rather than G itself so you can go back
% and compare G and G2. But you can modify G itself if you want.
%
% Because of the way I created G, it's a weighted digraph, so I need
% to give the new edges weights. I chose to weight them all pi.
% Scalar expansion lets me specify a scalar weight to be used for each new edge.
G2 = addedge(G, [1 newnodes], [newnodes 2], pi);
% Eliminate the edge from 1 to 2
G2 = rmedge(G2, 1, 2);
% Plot the new digraph
figure;
plot(G2)

MATLAB: How to find the Members of the largest component of a graph

Use

oF = F_prime.Nodes.Name(bin==m);

instead of the find command to return node names instead of node numbers.

Best Answer

Related Solutions

MATLAB: Delete and add new edges in a graph

MATLAB: How to find the Members of the largest component of a graph

Related Question