Python recursive tree, linked list thingy

[MRAB]

On 07/03/2012 19:49, Wanderer wrote:
> 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)