用Pandas或Pypark在两列中表示的关系展平“树”

Question

我收集的家谱格式与以下类似：

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

用以下两列（包含多棵树）表示：

^{tb1}$

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

即B=A，D=A

^{tb2}$

理想情况下，我希望在Spark中这样做（考虑到数据集的大小），但也可以尝试Pandas

如果没有对每一层都使用非常密集的递归函数（即使我的树最多有3层深），我目前无法高效地完成这项工作

Answer 1

import pandas as pd
import numpy as np
df = pd.DataFrame({
    "child": ['A','B','C','D','E','F','G','H','I','A1','B1','C1','D1','E1','F1','G1','H1','I1'],
    "parent": [np.NaN,'A','A','B','B','C','C','G','G',np.NaN,'A1','A1','B1','B1','C1','C1','G1','G1']
})

upper_parent_list = list(df[df['parent'].isna()]['child'])
['A', 'A1']

df['upper_parent'] = df['parent'].fillna(df['child'])

   child parent upper_parent
0      A    NaN            A
1      B      A            A
2      C      A            A
3      D      B            B
4      E      B            B
5      F      C            C
6      G      C            C
7      H      G            G
8      I      G            G
9     A1    NaN           A1
10    B1     A1           A1
11    C1     A1           A1
12    D1     B1           B1
13    E1     B1           B1
14    F1     C1           C1
15    G1     C1           C1
16    H1     G1           G1
17    I1     G1           G1

while df['upper_parent'].isin(upper_parent_list).sum()!=df.shape[0]:
    for up_par in upper_parent_list:
        child_list = list(df[df['upper_parent'].isin([up_par])]['child'])
        df['upper_parent'] = np.where(df['parent'].isin(child_list), up_par, df['upper_parent'])
print(df)

   child parent upper_parent
0      A    NaN            A
1      B      A            A
2      C      A            A
3      D      B            A
4      E      B            A
5      F      C            A
6      G      C            A
7      H      G            A
8      I      G            A
9     A1    NaN           A1
10    B1     A1           A1
11    C1     A1           A1
12    D1     B1           A1
13    E1     B1           A1
14    F1     C1           A1
15    G1     C1           A1
16    H1     G1           A1
17    I1     G1           A1