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

我想将它们分组到所有连接的组(Connectivity) 中，如下所示：

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_componentsimport networkx as nxG=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    01    02    13    14    25    2Name: node1, dtype: int64

Answer 2

如果由于某种原因您无法使用外部库，则可以实现以下算法：import pandas as pddef bfs(graph, start):    visited, queue = set(), [start]    while queue:        vertex = queue.pop(0)        if vertex not in visited:            visited.add(vertex)            queue.extend(graph[vertex] - visited)    return visiteddef connected_components(G):    seen = set()    for v in G:        if v not in seen:            c = set(bfs(G, v))            yield c            seen.update(c)def graph(edge_list):    result = {}    for source, target in edge_list:        result.setdefault(source, set()).add(target)        result.setdefault(target, set()).add(source)    return resultdf = pd.DataFrame({'node1': ['2', '4', '17', '17', '205', '208'],                   'node2': ['4', '13', '25', '38', '208', '300']})G = graph(df[['node1', 'node2']].values)components = connected_components(G)lookup = {i: component for i, component in enumerate(components, 1)}df['group'] = [label for node in df.node1 for label, component in lookup.items() if node in component]print(df)输出  node1 node2  group0     2     4      11     4    13      12    17    25      33    17    38      34   205   208      25   208   300      2