0

I have a 1D numpy array of bools representing an NxN matrix (for example, a 10x10 matrix has values 0 through 9,then 10 through 19, etc.) My goal is to find the number of 'true' elements that are adjacent --above, below, left, right, or diagonal.

My plan to solve this is to iterate through the array (for x in my_array) and when a 'true' element is encountered, enter a search pattern for the surrounding elements. If one of the surrounding elements is also true, it then searches its surrounding elements. However, I am not certain if this is the optimized search, and implementing it recursively is proving difficult.

Any recommendations on algorithms or methods to search a 1D numpy array for adjacent elements?

EDIT:

Because the depth first searches I have seen use dictionaries to set the paths between elements, I tried creating a function to define this (below).

I simplified it to only consider left, right, above and below (no diagonals yet), but edge cases are not working.

With this, I'd hope to use a Depth First Search function, recursively calling itself when a 'true' element is found. 

def getgraph(lst):
    #print('here2')
    for x in lst:
        if x is 0:
            graph[x] = set([x+1, x+n])
            x = x+1
        while (x > 0) and (x < (n-1)): #first row, excluding edges
            graph[x] = set([(x-1),(x+1),(x+n)])
            x= x+1

        while x >= (n-1) and x < ((n-1)*n): #second to second last row, with edge cases
            v = x%n
            width = n-1
            print('XN: %f' %v)
            if (x % n) == 0:
                graph[x] = set([x+1, x+n])
                x = x+1
            if (v) is width:
                graph[x] = set([(x-1),(x+n)])
                x = x+1
            else:
                graph[x] = set([(x-1), (x+1), (x+n), (x-n)])
                x= x+1

        while x >= (n-1)*n and x <= ((n*n)-1):
            value = ((n*n)-1)
            if x is value: # works with manually inputting last element number
                graph[x] = set([(x-1),(x-n)])
                x = x+1
            else:
                graph[x] = set([(x-1),(x+1),(x-n)])
                x= x+1

    print(graph)
    return graph
NdW
  • 1
  • 3
  • What have you done? Please add at least a snippet code. – Dr.jacky Mar 08 '16 at 05:05
  • Welcome to Stack Overflow! Your question is difficult to answer as it doesn't contain your code. You'll need to post your code so that people can look at it and point out where the problem is. It's preferred that you create a [Minimal, Complete, and Verifiable example](http://stackoverflow.com/help/mcve). Also see [How do I ask a good question?](http://stackoverflow.com/help/how-to-ask). Good luck! – Martin Tournoij Mar 08 '16 at 05:08
  • Sounds like the Game of Life. You could look for someone else's implementation of it in Python for starters, e.g. http://codereview.stackexchange.com/questions/40886/conways-game-of-life-in-python. But its typically better to try by oneself first, then see what others did. – roadrunner66 Mar 08 '16 at 05:15

1 Answers1

0

The problem you describe is called "connected component labeling" in image processing - you just have a 1D array instead of a matrix (which, incidentally, was the usual case in the old days of image processing).

If you convert to a 2D array, you can apply scipy.ndimage.measurements.label (docs) (e.g. as explained in this answer)

If you still want to implement it yourself, a 2-pass algorithm is known as a standard solution. Lots of additional insights in this other answer.

Community
  • 1
  • 1
JARS
  • 1,109
  • 7
  • 10