python - 使用 Pandas 或 Pyspark 将 'trees' 与两列中表示的关系展平

Question

我有一系列家谱，其格式类似于以下内容:

    A
   / \
  B   C
 / \ / \
D  E F  G
  / \
 .. ..

在以下两列中表示(其中包含多棵树):

<表类="s-表"><头> child parent <正文>一个B一个C一个DB......

什么是最有效的方法来展平它，以便在新列中我得到最上面的父级？

即B = A, D = A...?

<表类="s-表"><头> child parent highest_parent<正文>一个一个B一个一个C一个一个DB一个.........

理想情况下，我想在 Spark 中执行此操作(考虑到数据集的大小)，但也可以尝试 Pandas 吗？

如果没有针对每个级别的一些非常密集的递归函数(即使我的树最多 3 级深)，我目前无法全神贯注地高效地执行此操作。

Answer 1

在 pandas 中，您可以使用 networkx

检查

df=df.dropna()
import networkx as nx
G=nx.from_pandas_edgelist(df, 'parent', 'child',create_using=nx.DiGraph())
def find_root(G,node):
    if len(list(G.predecessors(node)))>0:
        root = find_root(G,list(G.predecessors(node))[0])
    else:
        root = node
    return root

df['child'].apply(lambda x : find_root(G,x))

Out[109]: 
1    A
2    A
3    A