http://www.mathworks.com/matlabcentral/newsreader/view_thread/306423
MATLAB Central Newsreader  Gathering indexes of elements connectable only by rows or columns
Feed for thread: Gathering indexes of elements connectable only by rows or columns
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Mon, 18 Apr 2011 09:03:05 +0000
Gathering indexes of elements connectable only by rows or columns
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306423#831667
Hassan
I have a m x n matrix of zeros and ones. I want to be able to group all the "1"s that can be connected to other "1"s, but only by going vertically or horizontally in a matrix, never diagonally. Here's an example:<br>
<br>
A= 0 0 0 0 0 1 0 0 <br>
0 1 1 0 0 1 0 0<br>
0 0 0 0 0 0 0 0<br>
1 0 0 0 1 0 0 0<br>
0 1 0 0 0 0 0 1<br>
0 0 0 0 1 0 0 0<br>
<br>
In this matrix, A(1,6),A(2,6),A(2,3),A(2,2),A(5,2), and A(5,8) would be one group<br>
then<br>
A(4,1),A(4,5), and A(6,5) would be another group, <br>
etc...<br>
<br>
What's the easier way to do that? I thought about approaching this by doing loops, but things get very hairy. Are there any built in Matlab functions for this?<br>
<br>
Thanks in advance,<br>
H

Mon, 18 Apr 2011 20:24:04 +0000
Re: Gathering indexes of elements connectable only by rows or columns
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306423#831804
Roger Stafford
"Hassan" wrote in message <ioguo9$gut$1@fred.mathworks.com>...<br>
> I have a m x n matrix of zeros and ones. I want to be able to group all the "1"s that can be connected to other "1"s, but only by going vertically or horizontally in a matrix, never diagonally. Here's an example:<br>
> <br>
> A= 0 0 0 0 0 1 0 0 <br>
> 0 1 1 0 0 1 0 0<br>
> 0 0 0 0 0 0 0 0<br>
> 1 0 0 0 1 0 0 0<br>
> 0 1 0 0 0 0 0 1<br>
> 0 0 0 0 1 0 0 0<br>
> <br>
> In this matrix, A(1,6),A(2,6),A(2,3),A(2,2),A(5,2), and A(5,8) would be one group<br>
> then<br>
> A(4,1),A(4,5), and A(6,5) would be another group, <br>
> etc...<br>
> <br>
> What's the easier way to do that? I thought about approaching this by doing loops, but things get very hairy. Are there any built in Matlab functions for this?<br>
> <br>
> Thanks in advance,<br>
> H<br>
         <br>
Your "connected" condition constitutes an equivalence relation between all the 1 elements of A, and the groups you seek are equivalence classes. See the site:<br>
<br>
<a href="http://en.wikipedia.org/wiki/Connected_component_">http://en.wikipedia.org/wiki/Connected_component_</a>(graph_theory)<br>
<br>
I am not aware of any Matlab functions that perform this specific task, so you will have to write your own.<br>
<br>
I would recommend first setting up a larger square matrix, B, in which each row and column correspond to a single 1 element in A. The elements in B should be 1 if the two corresponding 1 elements in A are in the same row or column and therefore immediately connected, and 0 otherwise. The following should accomplish that:<br>
<br>
[r,c] = find(A);<br>
m = length(r);<br>
[p,q] = ndgrid(1:m,1:m);<br>
B = reshape(r(p)==r(q)c(p)==c(q),m,m);<br>
<br>
The r,c pairs indicate which row and column pairs in A had 1's, and their order in r,c matches the order of rows and columns in B.<br>
<br>
In B this is then a straightforward problem in graph theory in finding the connected components in B where a 1 indicates a path between nodes. I am sure somewhere there are algorithms that have been worked out for this problem. Do a search on Google using the words "graph", "connected", "equivalence class", "component", etc.<br>
<br>
Roger Stafford