查找共享公共元素的行

Question

我有一个 2D numpy 数组，其中每行包含 2 个整数。我想找到属于共享公共元素的行的所有元素组（也称为边列表数组中图形的连接组件）。例如，对于数组：

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

Answer 1

如果您可以使用库，假设您的数组是a（请注意，您不能将组件作为 numpy 数组，因为它们可以是 numpy 中不存在的非矩形数组，因此这会将它们作为集合输出）：import networkx as nxG=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}]

Answer 2

就图论而言，您需要从边数组创建一个图，然后找到该图的连通分量。纯粹的基于解决方案对我来说似乎太难了，但你仍然可以使用用 C 编写的（与纯 Python 不同）numpy使其成为 C 级别。您需要先安装。igraphnetworkxpython-igraph小事例igraph.Graph.clusters()方法返回一个特殊的igraph.clustering.VertexClustering类实例，可以转换为list：import igrapharr = 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 vertexig.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 garr = 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 vertexig.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]]

Answer 3

我确信有更快的方法，而且我不研究图论，但你可以从这个开始；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] = tret = [[k for k, v in grps.items() if v==g] for g in set(grps.values())]print(ret)