在树中找到所有后代

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 pdimport networkx as nxd = {'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 Descendent0       abc        def1       abc        ghi2       abc        jkl3       mno        pqr