时间戳

首页 > 解决方案 > 递归地列出树/有向图中节点的邻居，对于图中的所有节点，一次一个“级别”？

pandas - 递归地列出树/有向图中节点的邻居，对于图中的所有节点，一次一个“级别”？

问题描述

我正在尝试从具有两列和多行的 Excel 工作表生成“佣金共享”组织的图表。左行包含分配给每个代理的唯一 ID。右侧的单元格列出了在左侧单元格中招募代理的代理的唯一 ID。我手动插入了一个新的第 1 行，其值为：agent 和hired_by

我使用以下方法将 excel 数据转换为 pandas Edgelist：

import pandas as pd
XL='path to Excel file'
df=pd.read_excel(XL,sheet_name=3)
G=nx.from_pandas_edgelist(df,'agent','hired_by',create_using=nx.Graph)

对于这些目的，使用 nx.Graph 而不是 nx.DiGraph 很重要，因为“连接方向”并不重要。重要的是“级别”，即根节点和代理之间的跳数，用于确定补偿属性。

然后，我可以使用以下代码从根目录逐级确定层次结构，然后可以将其粘贴到工作中的 .dot（有向图）文件中，只需进行少量编辑。通过工作，我的意思是它以图形方式分隔级别，因为它由以下行组成：

“node01”-> {“node02”、“node03”、“node04”、“node05”、“node06”}

for n in G.nodes():
if len(nx.shortest_path(G, 'node01', n)) == 1: 
print(nx.shortest_path(G, 'node01', n),len(nx.shortest_path(G, 'node01', n)))

这会产生如下输出：

"node01" -> {"node02", "node03", "node04", "node05", "node06"} 1
...
"node06" -> {"node10", "node11", "node07"} 2
...
"node17" -> {"node21", "node22"} 4

这很好用，唯一的问题是我必须手动更改上面代码中每个级别的数字“1”，并将输出复制并粘贴到我的 .dot 文件中，然后重新排列行，因为输出没有将所有“3 级”组合在一起。

目前这是可以接受的混乱程度，但我可能还有更多记录需要处理。

有没有办法让这项工作递归地从一个级别到另一个级别？

谢谢！

标签： pandasnetworkinggraphvizpython-3.7dot

解决方案

如果您已经创建了有向图（调用它G），您可以使用以下代码来实现您正在寻找的内容：

from collections import defaultdict


recruit_dict = defaultdict(set)

# Use .edges instead of nodes to get connections between nodes
for agent, recruited in G.edges:
    if agent == recruited:
        continue
    recruit_dict[agent].add(recruited)

with open("dot.txt", "w") as out_handle:
    for parent, children in recruit_dict.items():
        children_str = ', '.join(
            f'"{child}"' for child in sorted(children)
        )
        out_handle.write(f"\"{parent}\" -> {children_str}\n")

dot.txt给定示例输入的内容：

"1" -> "2", "3", "6"
"2" -> "4", "7"
"3" -> "5", "8"

推荐阅读