查找共享公共元素的行

Question

我有一个2D numpy数组，每行包含2个整数。 我想找到所有属于共享元素的行的元素组的组（也称为从edgelist数组中的图的连通分量）。 例如，对于以下数组：

[[ 0  4]
 [ 0  7]
 [ 1  2]
 [ 1 13]
 [ 2  1]
 [ 2  9]
 [ 3 14]
 [ 3 16]
 [ 4  0]
 [ 4  5]
 [ 5  4]
 [ 5  6]
 [ 6  5]
 [ 6  7]
 [ 7  0]
 [ 7  6]]

该组将包含以下内容

[[ 0  4  5  6  7]
 [ 1  2 13  9]
 [ 3 14 16]]

- bs15ansj

---

你是在问：给定一组边，如何找到它们的连通分量？这些边是有向的吗？请编辑问题以澄清。 - myrtlecat

你需要纯NumPy解决方案还是任何一种都可以？ - Ehsan

很抱歉，我对图论术语不是很了解，但是我相信 Ehsan 已经编辑了问题以澄清我的意思。 - bs15ansj

Answer 1

如果可以使用库，假设你的数组是a（请注意，你不能将组件作为numpy数组，因为它们可能是非矩形数组，在numpy中不存在，因此它会将它们输出为集合）：

import networkx as nx
G=nx.Graph()
G.add_edges_from(a)
print(sorted(nx.connected_components(G), key = len, reverse=True))
#[{0, 4, 5, 6, 7}, {1, 2, 13, 9}, {16, 3, 14}]

如果您需要一个不需要额外库的纯numpy解决方案，请查看这个通用解决方案： https://stackoverflow.com/a/61764414/4975981

- Ehsan

---

这是使用图论连通分量的内容。 - Scott Boston

@Ehsan，我不完全知道“numpyic”的含义，但是在你的参考资料中没有矢量化的解决方案。我已经设法在C级别上实现了它（几乎），但仍然想知道是否存在纯矢量化的numpy版本。 - mathfux

谢谢您的建议，这显然是最简单的回答，但是是的，我希望得到一个纯numpy的答案。我自己能够得到的最好的答案是遍历行并且如果元素尚未使用A[np.where(np.isin(A,row))[0]]找到，则添加到列表中。然而，由于节点之间的边形成五元连接图，第五个节点（距离行中的节点两个节点）总是被遗漏，上面的代码需要在找到集合的四个节点后再次调用。如果我的术语不正确，请原谅，我是一名研究病毒外壳的生物学家！ - bs15ansj

@mathfux 尽管链接的答案在某种程度上使用了向量化方法，但我并没有看到我声称它是这样的。我只是将其称为一种仅使用numpy（因此在某种程度上是Numpyic），而不是外部库的解决方案。我不知道是否有完全向量化的高效解决方案。感谢您的回答帖子。我怀疑igraph使用DFS来查找集群。 - Ehsan

@bs15ansj 不客气。我会在这里添加链接的答案，尽管我不确定它是否比networkx更快。这也取决于你的图有多密集。你的图是否被认为是稀疏的（意味着数组中的行数与数组中最大唯一元素的数量的数量级相同）？ - Ehsan

Answer 2

我相信有更快的方法，但我并没有研究图论，你可以从这里开始；

x = [[ 0,  4],
 [ 0,  7],
 [ 1,  2],
 [ 1, 13],
 [ 2,  1],
 [ 2,  9],
 [ 3, 14],
 [ 3, 16],
 [ 4,  0],
 [ 4,  5],
 [ 5,  4],
 [ 5,  6],
 [ 6,  5],
 [ 6,  7],
 [ 7,  0],
 [ 7,  6]]

nodes = list(set([item for sublist in x for item in sublist]))
grps = {n: g for n, g in zip(nodes, range(len(nodes)))}

for v in x:
    t = grps[v[0]]
    f = grps[v[1]]
    if t != f:
        for n in grps:
            if grps[n] == f:
                grps[n] = t

ret = [[k for k, v in grps.items() if v==g] for g in set(grps.values())]
print(ret)

- Helios

Answer 3

根据图论，您需要从边的数组中创建一个图，然后找到该图的连通组件。对于我来说，纯numpy方案似乎太难了，但您仍然可以使用以C语言编写的igraph将其提升至C级别（与纯Python的networkx不同）。您需要先安装python-igraph。

微不足道的情况下，igraph.Graph.clusters()方法返回一个特殊实例的igraph.clustering.VertexClustering类，它可以转换为list：

import igraph
arr = np.array([[0, 4], [0, 7], [1, 2], [1, 9], [2, 1], [2, 8], [3, 10], 
                [3, 11], [4, 0], [4, 5], [5, 4], [5, 6], [6, 5], [6, 7], [7, 0], [7, 6]])
g = ig.Graph()
g.add_vertices(12)
g.add_edges(arr)
i = g.clusters() 
print(list(i))
#output: [[0, 4, 5, 6, 7], [1, 2, 8, 9], [3, 10, 11]]

igraph 也支持绘制这些连通组件，就像在networkx中一样，但您可能需要从非官方二进制文件下载pycairo并安装它，以解锁igraph.plot选项：

pal = ig.drawing.colors.ClusterColoringPalette(len(i)) #passing a number of colors 
color = pal.get_many(i.membership) # a list of color codes for each vertex
ig.plot(g,  bbox = (200, 100), vertex_label=g.vs.indices,
        vertex_color = color, vertex_size = 12, vertex_label_size = 8)

通用情况

注意，如果使用初始数组而不是平凡数组，则igraph会抛出InternalError。这是因为在添加边之前必须声明每个顶点，并且所有顶点都不允许有缺失的编号（实际上是允许的，但重新索引是静默完成的，旧名称可以使用“name”属性访问）。可以编写自定义函数来从重新标记的边创建图以解决此问题：

def create_from_edges(edgelist):
    g = ig.Graph()
    u, inv = np.unique(edgelist, return_inverse=True)
    e = inv.reshape(edgelist.shape)
    g.add_vertices(u) #add vertices, not reindexed
    g.add_edges(e) #add edges, reindexed
    return g

arr = np.array([[0, 4], [0, 7], [1, 2], [1, 13], [2, 1], [2, 9], [3, 14], 
                [3, 16], [4, 0], [4, 5], [5, 4], [5, 6], [6, 5], [6, 7], [7, 0], [7, 6]])
g = create_from_edges(arr)
i = g.clusters()
print(list(i))
#output: [[0, 4, 5, 6, 7], [1, 2, 8, 9], [3, 10, 11]]

新标签被用于输出（因此使其不正确），但仍然可以像这样访问旧标签：

print('new_names:', g.vs.indices)
print('old_names:', g.vs['name'])
>>> new_names: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> old_names: [0, 1, 2, 3, 4, 5, 6, 7, 9, 13, 14, 16]

它们可以用于预览原始图形（vertex_label 现在不同）：

pal = ig.drawing.colors.ClusterColoringPalette(len(i)) #passing a number of colors 
color = pal.get_many(i.membership) ##a list of color codes for each vertex
ig.plot(g,  bbox = (200, 100), vertex_label=g.vs['name'], 
        vertex_color = color, vertex_size = 12, vertex_label_size = 8)

最后，您需要使用旧的顶点名称来修复输出。可以像这样完成：

output = list(i)
old_names = np.array(g.vs['name'])
fixed_output = [old_names[n].tolist() for n in output]
#new output: [[0, 4, 5, 6, 7], [1, 2, 9, 13], [3, 14, 16]]

- mathfux