在树中找到所有后代

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