Detect isolated nodes from tree graph mathematically through incidence matrix or adjacency matrix or any other mathematical method?

Hi guys,

i have a tree graph as viewed in the picture

the data of nodes and branches as following (note: nodes numbers are not in uniform order)

node=[1
      2
      3
      6
      9
      5
      7
      8
      9
      15
      11
      12
      13];
%branch_number  from_node  to_node
branch=[1             1         2
        2             2         3
        3             2         4
        4             3         6
        5             4         5
        6             4         7
        7             6         8
        8             8         9
        9             7         10
        10            10        12
        11            10        11
        12            12        13];

supposed i choosed to removed specific branches [B7, B9, B12] (the ones with circles around) and want to know which nodes are isloated from the graph (main node)

i made the following loop to remove the desired branches

B=[7 9 12]; %branches removed
N=length(B);
% loop for removing branches from branch data
c=0;
for i=1:N
branch(B(i)-c,:)=[];
c=c+1;
end
branch;

so now after branches are removed and there become new branch data, i want the output is to be detecting the nodes isloated from the system (main nodes)

such as in this case will be nodes number (N8, N9, N15, N11, N12, N13) nodes in yellow color

and the the update the node array by removing the isolated nodes from it and become as following

isolated_node=[8 9 15 11 12 13] 
node= [1
       2
       3
       6
       9
       5
       7];

i made a loop for incidence matrix but i dont know if it helps and can be used or not, and it's as following

br=length(branch);
no=length(node);
%incidence matrix
C=zeros(br,no);
for i=1:br
    a=branch(i,2);
    b=branch(i,3);
    for j=1:no
         c=node(j,1);
        if a==c
            C(i,j)=-1;
        end
        if b==c
            C(i,j)=1;
        end
    end
end
C;

please help.

Answer 1

[Stephan]

Hi,

Matlab has his own graph functions. Learn how to define a graph object in Matlab, will help you saving a lot of time for coding:

https://de.mathworks.com/help/matlab/graph-and-network-algorithms.html

For your case i suggest:

https://de.mathworks.com/help/matlab/ref/graph.conncomp.html

Best regards

Stephan

[hossam eldakroury]

well, i have already previously viewed those links while searching for the answer. but i didn't want to get deep in graph theory since its not my scope plus i'm new to matlab and i found the graph thing and functions pretty advanced to me.

I just wanted a simple "mathematical" method and not "graphical" to detect the isolated nodes through any characteristics could be found in incidence or adjacency matrix to detect such a thing, maybe be through a for loop or something i dunno.

But i already tried earlier the links you have sent, but they couldnt help me with the output i desire.

[Stephan]

Im sure that you will spend at east as much time by trying on your own as you wil need to use implemented functions. I recommend to work through the examples.

[hossam eldakroury]

okay, thanks.

Answer 2

[Steven Lord]

Use your vectors of edge endpoints to build a graph. Use rmedge to remove edges from it. Compute the distances from the root node to all others. If that distance is Inf, it means you can't get to the corresponding node from the root node.

[hossam eldakroury]

i am new to matlab so can you please show me with how to write this code on matlab ?