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

graphgraph theoryplotting

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.

Best Answer

Gc = G;
[eid, nid] = outedges(Gc,1);
Gc = rmedge(Gc, eid(nid ~= 2));
downstream_nodes = setdiff(unique(minspantree(Gc,'Root',1).Edges.EndNodes), 1);

Related Solutions

MATLAB: How to find all edges indexes if node indexes are given

So you're looking for all edges where both end nodes are part of the set 4, 5, 6? This will compute them:

>> [s, t] = findedge(g);
>> nodes = [4 5 6];
>> find(ismember(s, nodes) & ismember(t, nodes))
ans =
     5
     6

MATLAB: Determine separated node in graph

I'm not sure what is the final goal and/or application of this process. But let me try to do this task (since this "puzzle" will be a good excerise for me!)

% Create Graph object with fixed node name
s = [1 2 2 4 5 4 8 7 7 8 13];
t = [3 3 11 5 6 6 7 10 12 12 9];
G = graph(s,t,[],compose('%d',1:13));
% Separate G to subgraphs
group = conncomp(G,'OutputForm','cell');
subGraph = cellfun(@(x) subgraph(G,x),group,'UniformOutput',false);
% Initialize the output cell array (= result)
C_out = cell(1,numel(subGraph));
for kk1 = 1:numel(subGraph)
  % kk1-th subgraph
  G = subGraph{kk1};
  nodes = G.Nodes.Name';
  c = cell(1,numel(nodes));
  % Find non-neighbouring nodes for each node and create the output cell
  % arrray for each subgraph
  for kk2 = 1:numel(nodes)
    nextNodes = neighbors(G,nodes{kk2})';
    nonNextNodes = setdiff(nodes,[nodes(kk2),nextNodes]);
    if isempty(nonNextNodes)
      c{kk2} = str2double(nodes(kk2));
    else
      [~,pt] = sort(str2double(nonNextNodes));
      c{kk2} = str2double(nonNextNodes(pt));
    end
  end
  
  % Store the result for each subgraph
  C_out{kk1} = c;
end

Best Answer

Related Solutions

MATLAB: How to find all edges indexes if node indexes are given

MATLAB: Determine separated node in graph

Related Question