Найти кластеры бактерий

Question

Мне нужно найти все кластеры бактерий, которые связаны (4-соединение) в программе Python. Входной файл, который выглядит следующим образом:

     ### 
        ##### 
        ####### 
        ####### 
        ###### 
        ###### ## 
        #### ##### 
         ## ######  #### 
        # ######  #### 
        ### ########## ##### 
       ####### #### ## ###### 
       ######### ## #  ##### 
     #   #### ###   ### 
    #####  #### #  ##  ## 
    #####     ###### # 
    ######     ######## 
    ####      ######## 
           ####### 
           ####### 

Примечание: Кластеры, которые примыкают к краю сетки не может быть подсчитывались

Этот файл будет сохранен в виде 2D массива в моем классе , Я написал эту функцию, чтобы найти все кластеры, но она создает для многих кластеров (22 вместо 5). Любая идея, что я могу делать неправильно?

Мой код:

def findAll(self): 
    self.colonies = [set()] 
    for i in range(len(self.grid)): 
     for j in range(len(self.grid[i])): 
      if self.grid[i][j] == "#": 
       added = False 
       count = 0 
       for k in self.colonies: 
        if self.checkNeighbours((i, j), k): 
         k.add((i, j)) 
         added = True 
        count += 1 
       if not added: 
        self.colonies.append({(i, j)}) 

def checkNeighbours(self, pos, current): 
    return ((pos[0] + 1, pos[1]) in current 
      or (pos[0] - 1, pos[1]) in current 
      or (pos[0], pos[1] + 1) in current 
      or (pos[0], pos[1] - 1) in current) 

Answer 1

Проблема у вас была в том, что с момента образуются две группы, вы не могли бы присоединиться к ним. Даже если в конечном итоге два кластера должны были быть соединены добавлением промежуточных узлов.

Это может быть разрешено приложением union-find data structure. Неоптимизированная версия питона:

s = """\ 
        ###     \ 
        #####     \ 
        #######    \ 
        #######     \ 
        ######     \ 
        ###### ##    \ 
        #### #####   \ 
         ## ######  ####\ 
        # ######  #### \ 
        ### ########## ##### \ 
       ####### #### ## ###### \ 
       ######### ## #  ##### \ 
     #   #### ###   ### \ 
    #####  #### #  ##  ## \ 
    #####     ###### # \ 
    ######     ########  \ 
    ####      ########  \ 
           #######  \ 
           #######  \ 
""" 
representatives = {i: i for i, c in enumerate(s) if c == '#'} 
nrows, ncols = 19, 44 

def neighbours(idx): 
    i, j = divmod(idx, ncols) 
    if i > 0: yield idx - ncols 
    if i < nrows - 1: yield idx + ncols 
    if j > 0: yield idx - 1 
    if j < ncols - 1: yield idx + 1 

def representative(a): 
    while representatives[a] != a: a = representatives[a] 
    return a 

def join(a, b): 
    repr_a, repr_b = representative(a), representative(b) 
    if repr_a != repr_b: representatives[repr_a] = repr_b 

for idx in representatives: 
    for n in neighbours(idx): 
     if s[n] == '#': join(idx, n) 

cluster_count = len(set(map(representative, representatives))) 

Результат:

6 

Вы также могли бы создать также график и используется depth first search найти компоненты связности. Преимущество вышеупомянутого метода заключается в том, что он является инкрементальным, и вы можете легко обновлять кластеры с добавлением новых точек.

Answer 2

Обнаруживающие функции легко выполняются с помощью модуля scipy ndimage measurements. У этого есть дополнительное преимущество скорости, если вы идете этим путем.

import numpy as np 
from scipy.ndimage.measurements import label, find_objects 

q = np.genfromtxt('bacteria.txt', dtype='S1', comments=':', delimiter=1) 
arr = (q == b'#') # convert to boolean mask because ' ' evaluates to True 

labelled, num_features = label(arr) 

def count_edge_objects(labelled): 
    hulls = find_objects(labelled) 
    nbr_edgeobjects = 0 
    for rowslice, colslice in hulls: 
     if (rowslice.start == 0 or rowslice.stop == labelled.shape[0] or 
      colslice.start == 0 or colslice.stop == labelled.shape[1]): 
      nbr_edgeobjects += 1 
    return nbr_edgeobjects 

print('{} objects'.format(num_features - count_edge_objects(labelled))) 
# output: 
# 4 objects 

В наборе вы показали есть 2 объекты вблизи края: один наверху и один внизу. Заметьте, что в настоящее время я предполагаю, что набор данных имеет одинаковое количество символов в каждой строке (если нет, проверьте missing_values вариант np.genfromtxt)