pandas DF 中的分组连通图

Question

我有一个 pandas DF，其中每列代表一个节点，两列代表一条边，如下所示：

 import pandas as pd
df = pd.DataFrame({'node1': ['2', '4','17', '17', '205', '208'],
               'node2': ['4', '13', '25', '38', '208', '300']})

所有节点都是无向的，即您可以从一个到另一个undirected_graph

我想将它们分组为所有连接的组（连接），如下所示：

df = pd.DataFrame({'node1': ['2', '4','17', '17', '205', '208'],
           'node2': ['4', '13', '25', '38', '208', '300']
            ,'desired_group': ['1', '1', '2', '2',  '3', '3']})

例如，前两行之所以被分组，是因为它可以从节点 2 到达节点 13（通过 4）。

我设法找到的最接近的问题是这个： pandas - 根据列值将数据框重塑为边缘列表，但据我了解，这是一个不同的问题。

对此的任何帮助都会很棒，提前致谢。

Answer 1

使用networkx connected_components

import networkx as nx

G=nx.from_pandas_edgelist(df, 'node1', 'node2')

l=list(nx.connected_components(G))

L=[dict.fromkeys(y,x) for x, y in enumerate(l)]

d={k: v for d in L for k, v in d.items()}

#df['New']=df.node1.map(d)
df.node1.map(d)
0    0
1    0
2    1
3    1
4    2
5    2
Name: node1, dtype: int64