pandas DF 中的组连接图

Question

我有一个 Pandas DF，其中每列代表一个节点，两列代表一个边，如下所示： import pandas as pddf = 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_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

Answer 2

如果由于某种原因您无法使用外部库，则可以实现以下算法：

import pandas as pd

def 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 visited

def 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 result

df = 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  group

0     2     4      1

1     4    13      1

2    17    25      3

3    17    38      3

4   205   208      2

5   208   300      2