1
\$\begingroup\$

I have some questions about Depth First Search and whether I implemented it correctly. Below is a more thorough discussion. The graph in question is a randomly colored square grid (I use 3 colors). Adjacent vertices are connected if they have the same color. The task was to compute the clusters. DFS seems perfect for the job, but I had some trouble with the implementation. The code below is working now, but I imagine there is still room for improvement.

One challenge is that in order to compute the clusters, I run a DFS for each new vertex I visit. If the vertex has not been visited before, I assume it is not part of the previous clusters. Keeping track of all these DFS is giving me some difficult, making the code a bit disorganized.

Thank you very much for your time.


For a Go game app, I need to compute the connected clusters of pieces of the same color. This is a straightfoward depth first search, but I am still missing some parts.

Initialize the board. Here I used numpy to generate a random 10 × 10 grid with possible values 0, 1, 2 (representing empty, black and white states). We are looking for connected clusters of 0s, 1s and 2s. This is called percolation.

import numpy as np

n = 10
board = (3*np.random.random((n,n))).astype(int)
print board

[[1 1 0 2 2 0 0 2 2 0]
 [1 2 2 0 1 1 1 2 2 0]
 [0 2 0 0 1 0 0 1 0 1]
 [2 2 2 0 2 2 1 2 2 0]
 [2 1 1 0 0 2 2 1 2 1]
 [0 1 2 0 0 0 2 2 2 2]
 [1 0 0 0 0 2 2 0 0 2]
 [1 1 2 2 1 0 1 1 2 1]
 [1 2 2 1 2 2 1 0 0 0]
 [1 1 0 1 0 0 2 1 1 2]]

DFS

Using a depth-first search I found on the internet I proceed to find the clusters.

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}

Here I adapt the implementation to my problem. My graph is the 10 × 10 grid and two vertices are connected if they have the same color. I have to change the algorithm a bit since I don't really define the graph vertices and edges explicitly.

# http://stackoverflow.com/questions/509211/explain-pythons-slice-notation

visited =  np.zeros((n,n)).astype(int)

cluster = []

for (a,b) in [(a,b) for a in range(n) for b in range(n)][:]:

    if visited[a,b] == 0:

        queue = [[a,b]]
        color = board[a,b]    

        cluster += [[]]

        count = 0

        while queue:

            q = queue.pop()      
            cluster[-1] += [q]

            if visited[q[0],q[1]] == 0:
                visited[q[0],q[1]] = len(cluster)

                for x in [[1,0],[0,1], [-1,0], [0,-1]]:
                    if q[0] + x[0] > -1 and q[-1] + x[-1] > -1 and q[0] + x[0] < n and q[1] + x[1] < n:
                        if visited[q[0] + x[0], q[1] + x[1]] == 0 and board[q[0] + x[0], q[1] + x[1]] == color:
                            queue += [[q[0] + x[0], q[1] + x[1]]]       
            count += 1

            if count > 20:
                break

            print count,

visited

Unfortunately I have to add a break statement, but at least the program finds the cluster containing [0, 0]. Here are all the clusters containing points in the first two:

[[[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]],
  [[0, 1], [1, 1], [1, 2]],
  [[0, 2], [0, 3]],
  [[0, 3]],
  [[0, 4]],
  [[0, 5], [1, 5], [2, 5], [1, 4], [2, 4], [1, 3]],
  [[0, 6], [1, 6], [1, 7]],
  [[0, 7]],
  [[0, 8]],...]

Debugging

I am trying to get rid of the break statement. It is very bad style. Restricting only to the first vertex I noticed the queue variable does not become empty despite the repeated q = queue.pop() statement. Why does why does that variable stay populated?

Definintely open to other implementations of the graph and DFS. Thank you so much for your help.


Progress

Here's simplified version of the error I found:

a      = [5] 
b      = [a]
b[-1] += [5]
...
a      = [5,5]

Even though we changed the variable b, the variable a has also changed.

Defining cluster += [[]] instead of cluster += [queue] has worked.

Another toy example [1, 2, 3].pop() = 3 so we pop off the last item - I thought it was the first.

With those changes the program works to my satisfaction and now it is ready for Code Review.

\$\endgroup\$
  • 1
    \$\begingroup\$ I have attempted to move the context code into the quote blocks to help make the actual question more clear. But I'm still struggling to understand exactly what it is you're asking and would like. Could you provide a tl;dr for your question to sum it up and clarify exactly what you're looking for? As-is, this seems quite disorganized and confusing. \$\endgroup\$ – nhgrif Aug 17 '15 at 22:58
  • \$\begingroup\$ @nhgrif if you don't have time to read maybe move on to the next question? \$\endgroup\$ – john mangual Aug 18 '15 at 1:23
  • 1
    \$\begingroup\$ As it stands, your question is collecting close votes (it has 3, all for "Unclear what you're asking"). I'm not even a Python developer and it wouldn't be very likely I'd be able to post an answer even if your question were clear. My comment was a recommendation so that your question could remain open and collect answers (and be interesting enough). As it stands, your question lacks clarity. Leave it as-is at your own risk. \$\endgroup\$ – nhgrif Aug 18 '15 at 1:29
  • \$\begingroup\$ @nhgrif Well I am asking about my implmentation of DFS and whether it can be improved \$\endgroup\$ – john mangual Aug 18 '15 at 10:33
  • \$\begingroup\$ You mention some necessary changes in the end but have not done the changes in the actual code. \$\endgroup\$ – Janne Karila Aug 19 '15 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.