查找树中的所有后代

Question

我有一个像这样的df：

d = {'Parent': ['abc', 'abc', 'def', 'mno'], 'Child': ['def', 'ghi', 'jkl', 'pqr']}
df = pd.DataFrame(data=d)

并希望获得以下 DF：

d2 = {'Ancestor': ['abc', 'abc', 'abc', 'mno'], 'Descendant': ['def', 'ghi', 'jkl', 'pqr']}
df2 = pd.DataFrame(data = d2)

其中abc和mno是唯一的祖先，其余的被列为各自祖先的后代。

到目前为止，我已经尝试了networkx但没有任何运气。

编辑：示例仅显示三层，但树结构可以是任意数量的层。

Answer 1

我认为您可以使用带有有向图的newtorkx来做到这一点：

import pandas as pd
import networkx as nx
d = {'Parent': ['abc', 'abc', 'def', 'mno'], 'Child': ['def', 'ghi', 'jkl', 'pqr']}
df = pd.DataFrame(data=d)
dG = nx.from_pandas_edgelist(df, 'Parent', 'Child', create_using=nx.DiGraph())
df2 = pd.DataFrame({'Ancenstor':[[i for i in nx.ancestors(dG,i) if i not in df['Child'].tolist()][0] for i in df.Child],
'Descendent':df['Child']})
df2 

输出：

Ancenstor Descendent
0       abc        def
1       abc        ghi
2       abc        jkl
3       mno        pqr