查找共享公共元素的行

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

Answer 2

就图论而言，您需要从边数组创建一个图，然后找到该图的连通分量。纯粹的基于解决方案对我来说似乎太难了，但你仍然可以使用用 C 编写的（与纯 Python 不同）numpy使其成为 C 级别。您需要先安装。igraphnetworkxpython-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]]

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] = t

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

print(ret)