Python recursive tree, linked list thingy

[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?

 

[Ian Kelly]

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?

A set of defective pixels would be the probable choice, since it
offers efficient membership testing.

 

[MRAB]

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?

Something like this could work:

clusters = []

while defective_set:
to_do = {defective_set.pop()}
done = set()

while to_do:
pixel = to_do.pop()

neighbours = {n for n in defective_set if are_adjacent(n, pixel)}

defective_set -= neighbours
to_do |= neighbours

done.add(pixel)

clusters.append(done)

 

[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 += 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.

 

[Ian Kelly]

A set of defective pixels would be the probable choice, since it
offers efficient membership testing.

Some actual code, using a recursive generator:

def get_cluster(defective, pixel):
yield pixel
(row, column) = pixel
for adjacent in [(row - 1, column), (row, column - 1),
(row, column + 1), (row + 1, column)]:
if adjacent in defective:
defective.remove(adjacent)
for cluster_pixel in get_cluster(defective, adjacent):
yield cluster_pixel


defective = {(327, 415), (180, 97), (326, 415), (42, 15),
(180, 98), (325, 414), (325, 415)}
clusters = []

while defective:
pixel = defective.pop()
clusters.append(list(get_cluster(defective, pixel)))

from pprint import pprint
pprint(clusters)


Cheers,
Ian

 

[Enrico Franchi]

How
do you handle this sort of thing in Python?

I believe that the best thing to do is a Union-Find algorithm.

Depending on the exact nature of your problem, you may also want to
check out the Hoshen-Kopelman Algorithm. Although the algorithm itself
is rather efficient, it was born in the context of percolation, that is
to say with the assumption that the "broken" (or colored) cells are much
more likely than in your context.

 

[Robert Kern]

I believe that the best thing to do is a Union-Find algorithm.

Another term this problem is finding the "connected components". Here is some
code from Stefan van der Walt for this:

http://mentat.za.net/source/connected_components.tar.bz2
http://mentat.za.net/cgi-bin/hgwebdir.cgi/ccomp

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

 

[Wanderer]

A set of defective pixels would be the probable choice, since it
offers efficient membership testing.

Some actual code, using a recursive generator:

def get_cluster(defective, pixel):
    yield pixel
    (row, column) = pixel
    for adjacent in [(row - 1, column), (row, column - 1),
                     (row, column + 1), (row + 1, column)]:
        if adjacent in defective:
            defective.remove(adjacent)
            for cluster_pixel in get_cluster(defective, adjacent):
                yield cluster_pixel

defective = {(327, 415), (180, 97), (326, 415), (42, 15),
             (180, 98), (325, 414), (325, 415)}
clusters = []

while defective:
    pixel = defective.pop()
    clusters.append(list(get_cluster(defective, pixel)))

from pprint import pprint
pprint(clusters)

Cheers,
Ian

This works for me and I can modify it to look for column defects also.
It also shows I know less about Python then I thought I did. I had to
read up on generators and iterators to understand the code.

Thanks