2 dimensional array algorithm question

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

  1. Zarathustra

    Zarathustra Guest

    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
    #1
    1. Advertising

  2. Zarathustra

    Paul Mesken Guest

    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.

    Here's a link :

    http://splorg.org:8080/people/tobin/projects/hoshenkopelman/hoshenkopelman.html
    Paul Mesken, Jun 12, 2005
    #2
    1. Advertising

  3. Zarathustra

    Zarathustra Guest

    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.
    >
    > Here's a link :
    >
    > 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
    #3
  4. Zarathustra

    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
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alf P. Steinbach
    Replies:
    0
    Views:
    417
    Alf P. Steinbach
    Aug 18, 2003
  2. John Harrison
    Replies:
    4
    Views:
    6,906
    Default User
    Aug 19, 2003
  3. Icosahedron
    Replies:
    8
    Views:
    635
    Vivek
    Aug 21, 2003
  4. Venkat
    Replies:
    4
    Views:
    952
    Venkat
    Dec 5, 2003
  5. spidey12345
    Replies:
    6
    Views:
    890
    Thomas Fritsch
    Feb 8, 2007
Loading...

Share This Page