寻找细菌的聚集群。

Question

我需要在Python程序中查找所有连接的细菌簇（4连通性）。输入是一个长这样的文件：

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

注意：紧贴网格边缘的簇不能被计算。

这个文件以二维数组的形式保存在我的类中。我编写了这个函数来查找所有簇，但它创建了太多的簇（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)

- user4424299

---

你确定这张图片里没有6个细菌吗？ - user

哦，我明白了，那些是集群。底部的集群应该被忽略？如果是这样，你可能想把它添加到问题本身而不是这里，这样读者就可以轻松地看到它。 - user

你能发布一下 checkNeighbours 的代码吗？ - Moritz

你能否对你的算法策略进行一些评论？你是在尝试计算强连通分量吗？ - runDOSrun

您的问题被称为“连通区域标记”，最简单的算法是两遍扫描（因为您可能会在看到它们连接之前在一行上开始两个组件，因此需要在后面将它们合并）。 - Francis Colas

Answer 1

你遇到的问题是，在形成了两个聚类后，无法将它们合并。即使最终这两个聚类应该通过添加中间节点来合并。

可以通过应用并查集数据结构来解决这个问题。以下是一个未经优化的Python版本：

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

你也可以创建一个图，并使用 深度优先搜索 查找连接组件。上述方法的优点是它是增量的，您可以通过添加新点轻松更新聚类。

- JuniorCompressor

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

在你展示的数据集中，有两个接近边缘的对象：一个在顶部，一个在底部。请注意，我目前假设数据集每行具有相等数量的字符（如果不是，则查看 np.genfromtxt 的 missing_values 选项）。

- Oliver W.

---

很棒！你还可以使用(np.unique(np.r_[labelled[0], labelled[-1], labelled[:, 0], labelled[:, -1]]) > 0).sum()作为count_edge_objects(labelled)的替代方案。 - unutbu