How to get connected component from adjacency matrix
Mostrar comentarios más antiguos
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.
Respuesta aceptada
Guillaume
el 14 de Ag. de 2016
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');
Más respuestas (1)
Image Analyst
el 13 de Ag. de 2016
Editada: Image Analyst
el 13 de Ag. de 2016
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 comentarios
lingfeng zhou
el 13 de Ag. de 2016
Thanks for your answer!
But maybe I didn't introduce my question very clear.
What I have is "adjacency matrix", which means the relation between vertex and edge. And maybe bwlabel() is more suitable for a Binary Image problem rather than my problem.
Here is another example to introduce my question.
There are 6 vertex and 3 identity connected regions.
If I use bwlabel(), the vertex "1" maybe ignored.
Image Analyst
el 13 de Ag. de 2016
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
el 14 de Ag. de 2016
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
el 14 de Ag. de 2016
Image Analyst
el 14 de Ag. de 2016
You can't get that with regionprops. You'll have to look at graph/node/network functions. I'm not familiar with those.
lingfeng zhou
el 14 de Ag. de 2016
Image Analyst
el 14 de Ag. de 2016
Unaccept my Answer and see if Guillaume's gives you the answer and if it does, accept his answer to give him credit.
Categorías
Más información sobre Graph and Network Algorithms en Centro de ayuda y File Exchange.
Productos
el 13 de Ag. de 2016
el 9 de Dic. de 2020
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
