python - 如何在矩阵中搜索连接元素？

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没有为有向图定义，然后找到 max使用 len作为关键功能:

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

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