Thread Subject:

Gathering indexes of elements connectable only by rows or columns

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:

A= 0 0 0 0 0 1 0 0
     0 1 1 0 0 1 0 0
     0 0 0 0 0 0 0 0
     1 0 0 0 1 0 0 0
     0 1 0 0 0 0 0 1
     0 0 0 0 1 0 0 0

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
then
A(4,1),A(4,5), and A(6,5) would be another group,
etc...

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?

Thanks in advance,
H

"Hassan" wrote in message <ioguo9$gut$1@fred.mathworks.com>...
> 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:
>
> A= 0 0 0 0 0 1 0 0
> 0 1 1 0 0 1 0 0
> 0 0 0 0 0 0 0 0
> 1 0 0 0 1 0 0 0
> 0 1 0 0 0 0 0 1
> 0 0 0 0 1 0 0 0
>
> 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
> then
> A(4,1),A(4,5), and A(6,5) would be another group,
> etc...
>
> 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?
>
> Thanks in advance,
> H
- - - - - - - - - -
  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:

 http://en.wikipedia.org/wiki/Connected_component_(graph_theory)

  I am not aware of any Matlab functions that perform this specific task, so you will have to write your own.

  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:

 [r,c] = find(A);
 m = length(r);
 [p,q] = ndgrid(1:m,1:m);
 B = reshape(r(p)==r(q)|c(p)==c(q),m,m);

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.

  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.

Roger Stafford