Breadth-first search on numpy array for consecutive adjacent zeroes

Question

I have a numpy array that looks like the following:

arr = np.array([[-1, -1, -1,  0, -1]
               [ -1, -1, -1,  0, -1]
               [ -1,  0, -1, -1,  0]
               [ -1,  0, -1, -1, -1]
               [ -1, -1, -1, -1,  0]])

I want each consecutive region marked with a 0 (including diagonals) to be changed to a different value, such that my array would end up looking like this:

arr = np.array([[ -1, -1, -1,  1, -1]
                [ -1, -1, -1,  1, -1]
                [ -1,  2, -1, -1,  1]
                [ -1,  2, -1, -1, -1]
                [ -1, -1, -1, -1,  3]])

One way of doing this could be through a breadth-first search. Is there any convenient way to do this, or is there an easier method available?

Answer 1

Assuming this is a "real world" problem and not an algorithmic exercise, I would suggest to just use scipy.ndimage.label. The usual convention for these image segmentation and region labelling tasks is to use 0 to label the background. Considering this, you end up with the following code for your example:

import numpy as np
from scipy.ndimage import label

arr = np.array([[-1, -1, -1,  0, -1],
               [ -1, -1, -1,  0, -1],
               [ -1,  0, -1, -1,  0],
               [ -1,  0, -1, -1, -1],
               [ -1, -1, -1, -1,  0]])

labels, _ = label(arr + 1, structure=np.ones((3, 3)))

result = labels + arr
print(result)

Which gives:

[[-1 -1 -1  1 -1]
 [-1 -1 -1  1 -1]
 [-1  2 -1 -1  1]
 [-1  2 -1 -1 -1]
 [-1 -1 -1 -1  3]]

The performance should be orders of magnitude better than any Python loop based solution, as the loop is lowered down to C.

I hope this helps!