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

Question

hossam eldakroury 2019-4-1

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453733-detect-isolated-nodes-from-tree-graph-mathematically-through-incidence-matrix-or-adjacency-matrix-or

评论： hossam eldakroury 2019-4-1

采纳的回答： Stephan

在 MATLAB Online 中打开

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Stephan 2019-4-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453733-detect-isolated-nodes-from-tree-graph-mathematically-through-incidence-matrix-or-adjacency-matrix-or#answer_368482

编辑：Stephan 2019-4-1

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

3 个评论
显示 1更早的评论隐藏 1更早的评论

Stephan 2019-4-1

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 2019-4-1

okay, thanks.

请先登录，再进行评论。

Answer 2

Steven Lord 2019-4-1

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453733-detect-isolated-nodes-from-tree-graph-mathematically-through-incidence-matrix-or-adjacency-matrix-or#answer_368552

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.