Python recursive tree, linked list thingy

[Alexander Blinne]

Am 07.03.2012 20:49, schrieb Wanderer:
> I have a list of defective CCD pixels and I need to find clusters
> where a cluster is a group of adjacent defective pixels. This seems to
> me to be a classic linked list tree search.I take a pixel from the
> defective list and check if an adjacent pixel is in the list. If it is
> I add the pixel to the cluster and remove it from the defective list.
> I then check an adjacent pixel of the new pixel and so on down the
> branch until I don't find a defective pixel. The I move up to the
> previous pixel and check the next adjacent pixel  and so on until I'm
> back at the head I can't find any more defective adjacent pixels. How
> do you handle this sort of thing in Python?

I'd do something like (code not tested):

defective_list = [(x1, y1), (x2, y2), ...]   #list of coordinates of
                                              #defective pixel
#build one cluster:
cluster_start = defective_list.pop()         #starting point
buf = []                                     #buffer for added pixels
buf.push(cluster_start)
cluster = []
cluster.push(cluster_start)
while len(buf)>0:
     i = buf.pop()
     for b, d in itertools.product(xrange(2), [-1,1]):  #4 neighbours
         j = list(i)
         j[b] += d
         j = tuple(j)
         if outside_lcd(j) or j in cluster or j not in defective_list:
             continue
         defective_list.remove(j)
         cluster.push(j)
         buf.push(j)
return cluster

and repeat it until defective_list is empty.