Python Non Recursive Depth First Search

Question

I have written some code to identify the connected components in a binary image. I have used recursive depth first search. However, for some images, the Python Recursion Limit is not enough. Even though I increase the limit to the maximum supported limit on my computer, the program still fails for some images. How can I iteratively implement DFS? Or is there any other better solution?

My code:

count=1
height = 4
width = 5
g = np.zeros((height+2,width+2))
w = np.zeros((height+2,width+2))
dx = [-1,0,1,1,1,0,-1,-1]
dy = [1,1,1,0,-1,-1,-1,0]

def dfs(x,y,c):
    global w
    w[x][y]=c
    for i in range(8):
        nx = x+dx[i]
        ny = y+dy[i]
        if g[nx][ny] and not w[nx][ny]:
            dfs(nx,ny,c)

def find_connected_components(image):
    global count,g
    g[1:-1,1:-1]=image
    for i in range(1,height+1):
            for j in range(1,width+1):
                    if g[i][j] and not w[i][j]:
                        dfs(i,j,count)
                        count+=1

mask1 = np.array([[0,0,0,0,1],[0,1,1,0,1],[0,0,1,0,0],[1,0,0,0,1]])
find_connected_components(mask1)
print mask1
print w[1:-1,1:-1]

Input and Output:

[[0 0 0 0 1]
 [0 1 1 0 1]
 [0 0 1 0 0]
 [1 0 0 0 1]]
[[ 0.  0.  0.  0.  1.]
 [ 0.  2.  2.  0.  1.]
 [ 0.  0.  2.  0.  0.]
 [ 3.  0.  0.  0.  4.]]

use a task stack to record the parameters of the calls to `dfs` you need to perform, and pop the stack until there's nothing left in it, in a loop. — Jean-François Fabre, Jun 21 '17 at 19:15
Ok. I assume I would push into the stack in the last line of the dfs function, replacing the recursive call. Where would I pop from the stack and perform the necessary operation? — Sibi, Jun 21 '17 at 19:20
let me find an answer of mine where I recode recursive flood fill by iterative: there: https://stackoverflow.com/questions/40963288/fatal-python-error-cannot-recover-from-stack-overflow-during-flood-fill — Jean-François Fabre, Jun 21 '17 at 19:22
This is unrelated to your actual question, but none of your `global` statements are necessary. You don't need those if you're only accessing or mutating a global in-place. A `global` statement is only need if you want to be able to rebind the global name to a completely new value. — Blckknght, Jun 21 '17 at 19:40
You can just increase the maximum recursion limit too. Just set it using `import sys` and then `sys.setrecursionlimit(100000)` or any other number. — Mikael, Jun 21 '17 at 19:44
@Blckknght Yes I agree. However, I need it for the count variable. Otherwise I get the error `UnboundLocalError: local variable 'count' referenced before assignment ` — Sibi, Jun 21 '17 at 19:45
@Mikael As stated in the question, I have increased the limit to the maximum possible on my system. I still get an error. — Sibi, Jun 21 '17 at 19:46
@Jean-FrançoisFabre Could you please tell me how to adapt the method to my code and post it as an answer so I can accept it? Thanks! — Sibi, Jun 21 '17 at 19:48
@Sibi: I could try but can you fix your indentation? because the `count` line could belong to any of the loop contexts but it's wrong as it is. — Jean-François Fabre, Jun 21 '17 at 19:51
@Jean-FrançoisFabre Yes fixed! There was some error while copying the code into the SO window. — Sibi, Jun 21 '17 at 19:53

score 1 · Accepted Answer · answered Jun 22 '17 at 00:59

Have a list of locations to visit
Use a while loop visiting each location, popping it out of the list as you do.

Like so:

def dfs(x,y,c):
    global w
    locs = [(x,y,c)]
    while locs:
        x,y,c = locs.pop()
        w[x][y]=c
        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]
            if g[nx][ny] and not w[nx][ny]:
                locs.append((nx, ny, c))

Python Non Recursive Depth First Search

1 Answers1