如何搜索矩阵中的连通元素？

Question

我有一个这种形式的矩阵：

In [1]: df = pd.DataFrame([[0, 0, 1, 1, 1], [0, 0, 0, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 1], [1, 0, 0, 1, 0]], columns = list('ABCDE'), index = list('ABCDE'))

In [2]:df
Out[2]: 
   A  B  C  D  E
A  0  0  1  1  1
B  0  0  0  1  0
C  1  0  0  0  0
D  1  1  0  0  1
E  1  0  0  1  0

数字1代表两个元素之间的联系。在这种情况下'A'连接到'D'并且'E'和'D'连接到'E'，形成一个由三个元素形成的闭合连接。我寻找最大数量的相互连接的元素，在本例中为 'A'、'D'、'E'。我可以使用 for 循环，但它对于 300x300 矩阵来说太慢了。我该如何解决？

更新 1：

df = pd.DataFrame([[0, 0, 1, 0, 0, 1], [0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 1, 1], [0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 0, 0]], columns = list('ABCDEF'), index = list('ABCDEF'))

在这种情况下，解决方案是最长的循环['D'、'F'、'A'、'C'、'E']。

是否可能只有完全连接的元素，例如，在示例中出现的情况下，'C'、'D'、'E'？

Answer 1

您似乎在寻找 IIUC，从图论的角度来看，是 graph cycles。您可以通过使用 NetworkX:

从邻接矩阵生成图形来找到循环

import networkx as nx

G = nx.from_pandas_adjacency(df, create_using=nx.DiGraph)
nx.draw(G, with_labels=True, node_color='lightblue')

您可以通过nx.simple_cycles找到图形周期，并从那里轻松获得最长的：

max(nx.simple_cycles(G), key=len)
# ['E', 'D', 'A']

更新 -

如果你只想要那些“循环”中的完全连接的元素，你想要的是图 cliques。您首先必须转换为无向，因为 nx.find_cliques 没有为有向图定义，然后使用 len 作为关键函数找到 max：

H = G.to_undirected()
nx.draw(H, with_labels=True, node_color='lightblue')

max(nx.find_cliques(H), key=len)
# ['D', 'E', 'C']

如何搜索矩阵中的连通元素？

How do I search for connected elements in a matrix?

python

graph-theory

matrix

networkx

pandas