# 2 dimensional array algorithm question

Discussion in 'C Programming' started by Zarathustra, Jun 12, 2005.

1. ### ZarathustraGuest

I'm sure there must be a simple algorithm for giving the number of
"ones" that are connected, for example in an array like this:
int a[5][5] = {0};
a[0][0] = a[0][1] = a[1][1] = a[2][1] = a[0][4] = a[3][4]= a[4][4] =
a[4][0] = 1;
with all the rest still equal to zero.

1 0 0 1 1
0 0 0 0 0
0 0 0 0 0
1 1 1 0 0
1 0 0 0 1

such that the output in this case, can give 1 group of size 4, 1 group
of size 2, and 2 groups of size 1.

It looks simple, but everything I've tried so far hasn't caught all
possible shapes of groups of "1"s.

Any ideas would be greatly appreciated.

Zarathustra, Jun 12, 2005

2. ### Paul MeskenGuest

On 12 Jun 2005 11:16:16 -0700, "Zarathustra"
<> wrote:

>I'm sure there must be a simple algorithm for giving the number of
>"ones" that are connected, for example in an array like this:
>int a[5][5] = {0};
>a[0][0] = a[0][1] = a[1][1] = a[2][1] = a[0][4] = a[3][4]= a[4][4] =
>a[4][0] = 1;
>with all the rest still equal to zero.
>
>1 0 0 1 1
>0 0 0 0 0
>0 0 0 0 0
>1 1 1 0 0
>1 0 0 0 1
>
>such that the output in this case, can give 1 group of size 4, 1 group
>of size 2, and 2 groups of size 1.
>
>It looks simple, but everything I've tried so far hasn't caught all
>possible shapes of groups of "1"s.
>
>Any ideas would be greatly appreciated.

Jburgy mentioned in thread "Clustering in C" the Hoshen-Kopelman
algorithm. It's very simple. Just use it and then count the number of
cells for each cluster.

http://splorg.org:8080/people/tobin/projects/hoshenkopelman/hoshenkopelman.html

Paul Mesken, Jun 12, 2005

3. ### ZarathustraGuest

Paul Mesken wrote:
> On 12 Jun 2005 11:16:16 -0700, "Zarathustra"
> <> wrote:
>
> >I'm sure there must be a simple algorithm for giving the number of
> >"ones" that are connected, for example in an array like this:
> >int a[5][5] = {0};
> >a[0][0] = a[0][1] = a[1][1] = a[2][1] = a[0][4] = a[3][4]= a[4][4] =
> >a[4][0] = 1;
> >with all the rest still equal to zero.
> >
> >1 0 0 1 1
> >0 0 0 0 0
> >0 0 0 0 0
> >1 1 1 0 0
> >1 0 0 0 1
> >
> >such that the output in this case, can give 1 group of size 4, 1 group
> >of size 2, and 2 groups of size 1.
> >
> >It looks simple, but everything I've tried so far hasn't caught all
> >possible shapes of groups of "1"s.
> >
> >Any ideas would be greatly appreciated.

>
> Jburgy mentioned in thread "Clustering in C" the Hoshen-Kopelman
> algorithm. It's very simple. Just use it and then count the number of
> cells for each cluster.
>
>
> http://splorg.org:8080/people/tobin/projects/hoshenkopelman/hoshenkopelman.html

Thanks very much. That was exactly what I was looking for.

Zarathustra, Jun 14, 2005
4. ### Guest

It suffices to use depth-first search or breadth-first
search to label all of the clusters. Union-find is
probably overkill here since your graph is fixed.

, Jun 18, 2005