How to get connected component from adjacency matrix

Question

lingfeng zhou 2016-8-13

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/299488-how-to-get-connected-component-from-adjacency-matrix

评论： ali ganjbakhsh 2020-12-9

采纳的回答： Guillaume

The adjacency matrix is already known.

what I want to do is showed in the picture below.

I don't care about the order of the vertex.

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

请先登录，再进行评论。

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

Answer 1

Guillaume 2016-8-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/299488-how-to-get-connected-component-from-adjacency-matrix#answer_231683

在 MATLAB Online 中打开

A lot of graph functions have been added in R2015b. In particular, you have conncomp which gives you exactly what you want:

adjacencyMatrix =[0 1 1 0 1 0 1 0 1 0
    1 0 1 0 1 0 1 0 1 0
    1 1 0 0 1 0 1 0 1 0
    0 0 0 0 0 0 0 1 0 0
    1 1 1 0 0 0 1 0 1 0
    0 0 0 0 0 0 0 0 0 1
    1 1 1 0 1 0 0 0 1 0
    0 0 0 1 0 0 0 0 0 1
    1 1 1 0 1 0 1 0 0 0
    0 0 0 0 0 1 0 1 0 0]
G = graph(adjacencyMatrix);
plot(G);  %view the graph
bins = conncomp(G);
binnodes = accumarray(bins', 1:numel(bins), [], @(v) {sort(v')});
fprintf('number of Regions = %d\n\n', numel(binnodes));
for binidx = 1:numel(binnodes)
    fprintf('All these nodes are connected:%s\n', sprintf(' %d', binnodes{binidx}));
end
fprintf('\n');

2 个评论
显示无隐藏无

lingfeng zhou 2016-8-14

It's great and that's exactly what I want. I have never contact with this function before.Thank you so much.

ali ganjbakhsh 2020-12-9

so tnx

请先登录，再进行评论。

Answer 2

Image Analyst 2016-8-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/299488-how-to-get-connected-component-from-adjacency-matrix#answer_231640

编辑：Image Analyst 2016-8-13

在 MATLAB Online 中打开

Use bwlabel() and regionprops:

[labeledMatrix, numberOfRegions] = bwlabel(A);
props = regionprops(labeledMatrix, 'PixelList');

labeledMatrix gives an ID number to each connected region. props has all the information on all the elements in each connected region. You can get indexes (rows and columns), values, areas, etc. depending on what you ask regionprops() for.

7 个评论
显示 5更早的评论隐藏 5更早的评论

Image Analyst 2016-8-13

在 MATLAB Online 中打开

Yeah, I got it. I'm not sure you understand so I'll do the full blown demo with both of your cases so that you can see it tells you all the nodes that are connected:

% Example 1
adjacencyMatrix = false(6);
adjacencyMatrix(2, 3:4) = true;
adjacencyMatrix(3:4, 2) = true;
adjacencyMatrix(5, 6) = true;
adjacencyMatrix(6, 5) = true
[labeledMatrix, numberOfRegions] = bwlabel(adjacencyMatrix)
props = regionprops(labeledMatrix, 'PixelList');
for regions = 1 : numberOfRegions
  fprintf('All these nodes are connected: ');
  fprintf('%d ', unique(props(regions).PixelList));
  fprintf('\n');
end
% Example 2
adjacencyMatrix = false(6);
adjacencyMatrix(1, 3) = true;
adjacencyMatrix(2, 3:4) = true;
adjacencyMatrix(3, [1,2,4]) = true;
adjacencyMatrix(4, 2:3) = true;
adjacencyMatrix(5, 6) = true;
adjacencyMatrix(6, 5) = true
[labeledMatrix, numberOfRegions] = bwlabel(adjacencyMatrix)
props = regionprops(labeledMatrix, 'PixelList');
for regions = 1 : numberOfRegions
  fprintf('All these nodes are connected: ');
  fprintf('%d ', unique(props(regions).PixelList));
  fprintf('\n');
end

In the command window you'll see this for example 1:

adjacencyMatrix =
     0     0     0     0     0     0
     0     0     1     1     0     0
     0     1     0     0     0     0
     0     1     0     0     0     0
     0     0     0     0     0     1
     0     0     0     0     1     0
labeledMatrix =
     0     0     0     0     0     0
     0     0     1     1     0     0
     0     1     0     0     0     0
     0     1     0     0     0     0
     0     0     0     0     0     2
     0     0     0     0     2     0
numberOfRegions =
     2
All these nodes are connected: 2 3 4 
All these nodes are connected: 5 6

and this for example 2:

adjacencyMatrix =
     0     0     1     0     0     0
     0     0     1     1     0     0
     1     1     0     1     0     0
     0     1     1     0     0     0
     0     0     0     0     0     1
     0     0     0     0     1     0
labeledMatrix =
     0     0     1     0     0     0
     0     0     1     1     0     0
     1     1     0     1     0     0
     0     1     1     0     0     0
     0     0     0     0     0     2
     0     0     0     0     2     0
numberOfRegions =
     2
All these nodes are connected: 1 2 3 4 
All these nodes are connected: 5 6

Isn't that what you want to know? Which nodes are all part of the same group? I thought it was. Correct me if I'm wrong.

By the way, bwlabel does not ignore single isolated nodes, but you can remove those in advance if you want with the bwmorph()'s "Clean" option.

lingfeng zhou 2016-8-14

在 MATLAB Online 中打开

Well, thanks for your patience. I know the meaning of your method now, but there seems to be a little different with what I want to know.

For example, the answer I want is:

numberOfRegions =

     3
    All these nodes are connected: 1
    All these nodes are connected: 2 3 4
    All these nodes are connected: 5 6

Here,I want to give a more complex example,

% example 01
adjacencyMatrix =[0 1 0 0 0 0 0 0 0 0
    1 0 1 0 0 0 0 0 0 0
    0 1 0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    0 0 0 0 0 1 1 1 1 1
    0 0 0 0 1 0 1 1 1 1
    0 0 0 0 1 1 0 1 1 1
    0 0 0 0 1 1 1 0 1 1
    0 0 0 0 1 1 1 1 0 1
    0 0 0 0 1 1 1 1 1 0]
[labeledMatrix, numberOfRegions] = bwlabel(adjacencyMatrix)
props = regionprops(labeledMatrix, 'PixelList');
for regions = 1 : numberOfRegions
  fprintf('All these nodes are connected: ');
  fprintf('%d ', unique(props(regions).PixelList));
  fprintf('\n');
end

matlab answer is:

adjacencyMatrix =
       0     1     0     0     0     0     0     0     0     0
       1     0     1     0     0     0     0     0     0     0
       0     1     0     1     0     0     0     0     0     0
       0     0     1     0     0     0     0     0     0     0
       0     0     0     0     0     1     1     1     1     1
       0     0     0     0     1     0     1     1     1     1
       0     0     0     0     1     1     0     1     1     1
       0     0     0     0     1     1     1     0     1     1
       0     0     0     0     1     1     1     1     0     1
       0     0     0     0     1     1     1     1     1     0
labeledMatrix =
       0     1     0     0     0     0     0     0     0     0
       1     0     1     0     0     0     0     0     0     0
       0     1     0     1     0     0     0     0     0     0
       0     0     1     0     0     0     0     0     0     0
       0     0     0     0     0     2     2     2     2     2
       0     0     0     0     2     0     2     2     2     2
       0     0     0     0     2     2     0     2     2     2
       0     0     0     0     2     2     2     0     2     2
       0     0     0     0     2     2     2     2     0     2
       0     0     0     0     2     2     2     2     2     0
numberOfRegions =
       2
All these nodes are connected: 1 2 3 4 
All these nodes are connected: 5 6 7 8 9 10

Another example

% Example 2
  adjacencyMatrix =[0 1 1 0 1 0 1 0 1 0
      1 0 1 0 1 0 1 0 1 0
      1 1 0 0 1 0 1 0 1 0
      0 0 0 0 0 0 0 1 0 0
      1 1 1 0 0 0 1 0 1 0
      0 0 0 0 0 0 0 0 0 1
      1 1 1 0 1 0 0 0 1 0
      0 0 0 1 0 0 0 0 0 1
      1 1 1 0 1 0 1 0 0 0
      0 0 0 0 0 1 0 1 0 0]
    [labeledMatrix, numberOfRegions] = bwlabel(adjacencyMatrix)
    props = regionprops(labeledMatrix, 'PixelList');
    for regions = 1 : numberOfRegions
      fprintf('All these nodes are connected: ');
      fprintf('%d ', unique(props(regions).PixelList));
      fprintf('\n');
    end

matlab answer is:

adjacencyMatrix =
       0     1     1     0     1     0     1     0     1     0
       1     0     1     0     1     0     1     0     1     0
       1     1     0     0     1     0     1     0     1     0
       0     0     0     0     0     0     0     1     0     0
       1     1     1     0     0     0     1     0     1     0
       0     0     0     0     0     0     0     0     0     1
       1     1     1     0     1     0     0     0     1     0
       0     0     0     1     0     0     0     0     0     1
       1     1     1     0     1     0     1     0     0     0
       0     0     0     0     0     1     0     1     0     0
labeledMatrix =
       0     1     1     0     4     0     5     0     5     0
       1     0     1     0     4     0     5     0     5     0
       1     1     0     0     4     0     5     0     5     0
       0     0     0     0     0     0     0     5     0     0
       2     2     2     0     0     0     5     0     5     0
       0     0     0     0     0     0     0     0     0     5
       3     3     3     0     3     0     0     0     5     0
       0     0     0     3     0     0     0     0     0     5
       3     3     3     0     3     0     3     0     0     0
       0     0     0     0     0     3     0     3     0     0
numberOfRegions =
       5
All these nodes are connected: 1 2 3 
All these nodes are connected: 1 2 3 5 
All these nodes are connected: 1 2 3 4 5 6 7 8 9 10 
All these nodes are connected: 1 2 3 5 
All these nodes are connected: 1 2 3 4 5 6 7 8 9 10

From the above two examples we can find that the answer will change if we only change the node order.

lingfeng zhou 2016-8-14

Thank you anyway!

Image Analyst 2016-8-14

Unaccept my Answer and see if Guillaume's gives you the answer and if it does, accept his answer to give him credit.

请先登录，再进行评论。

How to get connected component from adjacency matrix

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

采纳的回答

2 个评论
显示无隐藏无

更多回答（1 个）

7 个评论
显示 5更早的评论隐藏 5更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

How to get connected component from adjacency matrix

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

采纳的回答

2 个评论 显示 无隐藏 无

更多回答（1 个）

7 个评论 显示 5更早的评论隐藏 5更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

WeChat

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

2 个评论
显示无隐藏无

7 个评论
显示 5更早的评论隐藏 5更早的评论