从pandas数据框的父子表中获取所有子代

Question

我有一个 Pandas 数据框，其中包含父 ID 和子 ID。我需要帮助构建一个更新的数据框，列出每个父级的所有后代。

为了澄清输出应该是什么样子，这里有一篇关于使用 SQL 在 Python 中实现我正在尝试做的事情的 dba.stackexchange 帖子。

以下是输入数据框的示例：

     parent_id            child_id
0         3111                4321
1         2010                3102
2         3000                4023
3         1000                2010
4         4023                5321
5         3011                4200
6         3033                4113
7         5010                6525
8         3011                4010
9         3102                4001
10        2010                3011
11        4023                5010
12        2110                3000
13        2100                3033
14        1000                2110
15        5010                6100
16        2110                3111
17        1000                2100
18        5010                6016
19        3033                4311

以下是硬编码为DataFrame的实际示例数据。

df = pd.DataFrame(
    {
        'parent_id': [3111, 2010, 3000, 1000, 4023, 3011, 3033, 5010, 3011, 3102, 2010, 4023, 2110, 2100, 1000, 5010, 2110, 1000, 5010, 3033],
        'child_id': [4321, 3102, 4023, 2010, 5321, 4200, 4113, 6525, 4010, 4001, 3011, 5010, 3000, 3033, 2110, 6100, 3111, 2100, 6016, 4311]
    }
)

这是我尝试使用递归列表构建策略的结果。

parent_list = []

def recurse(parent, child, root_parent):

    # initialize on first run of each branch
    if root_parent is None:
        root_parent = parent
        parent_list.append((parent, child))
        recurse(parent, child, root_parent)

    # for each parent find every child recursively
    for index, row in df.iterrows():
        if row['parent_id'] is child:
            parent_list.append((root_parent, row['child_id']))
            recurse(row['parent_id'], row['child_id'], root_parent)

# recurse down each parent branch
for i, r in df.iterrows():
    recurse(r['parent_id'], r['child_id'], None)

return parent_list

...目前只是因为我没有正确遍历树形结构而导致数据重复。

输出格式应与输入格式保持一致。我想要一个父ID和子ID的双列表格，如下面示例输出所示。

以下是上述数据的预期输出：

    parent_id  child_id
0        1000      2010
1        1000      2100
2        1000      2110
3        1000      3000
4        1000      3011
5        1000      3033
6        1000      3102
7        1000      3111
8        1000      4001
9        1000      4010
10       1000      4023
11       1000      4113
12       1000      4200
13       1000      4311
14       1000      4321
15       1000      5010
16       1000      5321
17       1000      6016
18       1000      6100
19       1000      6525
20       2010      3011
21       2010      3102
22       2010      4001
23       2010      4010
24       2010      4200
25       2100      3033
26       2100      4113
27       2100      4311
28       2110      3000
29       2110      3111
30       2110      4023
31       2110      4321
32       2110      5010
33       2110      5321
34       2110      6016
35       2110      6100
36       2110      6525
37       3000      4023
38       3000      5010
39       3000      5321
40       3000      6016
41       3000      6100
42       3000      6525
43       3011      4010
44       3011      4200
45       3033      4113
46       3033      4311
47       3102      4001
48       3111      4321
49       4023      5010
50       4023      5321
51       4023      6016
52       4023      6100
53       4023      6525
54       5010      6016
55       5010      6100
56       5010      6525

为每行添加一个深度/距离列，从parent_id到child_id，加分项。谢谢。

- taky2

---

你能否根据示例链接中的数据框添加预期输出？ - Bharath M Shetty

你觉得在数据框中为每个父节点使用DFS遍历怎么样？ - Cyclotron3x3

你认为ID中会出现循环吗？ - ConorSheehan1

更新：永远不应该存在循环。 - taky2

Answer 1

这应该返回你想要的两列中的父ID和子ID：

import pandas as pd
import numpy as np
import itertools

df = pd.DataFrame(
    {
        'parent_id': [3111, 2010, 3000, 1000, 4023, 3011, 3033, 5010, 3011, 3102, 2010, 4023, 2110, 2100, 1000, 5010, 2110, 1000, 5010, 3033],
        'child_id': [4321, 3102, 4023, 2010, 5321, 4200, 4113, 6525, 4010, 4001, 3011, 5010, 3000, 3033, 2110, 6100, 3111, 2100, 6016, 4311]
    }
)

def get_child_list(df, parent_id):
    list_of_children = []
    list_of_children.append(df[df['parent_id'] == parent_id]['child_id'].values)

    for i_, r_ in df[df['parent_id'] == parent_id].iterrows():
        if r_['child_id'] != parent_id:
            list_of_children.append(get_child_list(df, r_['child_id']))

    # to flatten the list 
    list_of_children =  [item for sublist in list_of_children for item in sublist]
    return list_of_children


new_df = pd.DataFrame(columns=['parent_id', 'list_of_children'])
for index, row in df.iterrows():
    temp_df = pd.DataFrame(columns=['parent_id', 'list_of_children'])

    temp_df['list_of_children'] = pd.Series(get_child_list(df, row['parent_id']))
    temp_df['parent_id'] = row['parent_id']

    new_df = new_df.append(temp_df)

print new_df

- amanbirs

---

谢谢！这个很好用。另外，快速调用.drop_duplicates()可以从new_df中删除所有冗余数据。 - taky2

Answer 2

只要你的ID没有循环依赖，我认为这应该可以工作。

    def get_children(id):
        list_of_children = []

        def dfs(id):
            child_ids = df[df["parent_id"]==id]["child_id"]
            if child_ids.empty:
                return 
            for child_id in child_ids:
                list_of_children.append(child_id)
                dfs(child_id)

        dfs(id)
        return list_of_children

    df["list_of_children"] = df["parent_id"].apply(get_children)
    df

返回：

    parent_id  child_id                                                                 list_of_children

0        3111      4321                                                                           [4321]

1        2010      3102                                                   [3102, 4001, 3011, 4200, 4010]

2        3000      4023                                             [4023, 5321, 5010, 6525, 6100, 6016]

3        1000      2010  [2010, 3102, 4001, 3011, 4200, 4010, 2110, 3000, 4023, 5321, 5010, 6525, 610...

4        4023      5321                                                   [5321, 5010, 6525, 6100, 6016]

5        3011      4200                                                                     [4200, 4010]

6        3033      4113                                                                     [4113, 4311]

7        5010      6525                                                               [6525, 6100, 6016]

8        3011      4010                                                                     [4200, 4010]

9        3102      4001                                                                           [4001]

10       2010      3011                                                   [3102, 4001, 3011, 4200, 4010]

11       4023      5010                                                   [5321, 5010, 6525, 6100, 6016]

12       2110      3000                           [3000, 4023, 5321, 5010, 6525, 6100, 6016, 3111, 4321]

13       2100      3033                                                               [3033, 4113, 4311]

14       1000      2110  [2010, 3102, 4001, 3011, 4200, 4010, 2110, 3000, 4023, 5321, 5010, 6525, 610...

15       5010      6100                                                               [6525, 6100, 6016]

16       2110      3111                           [3000, 4023, 5321, 5010, 6525, 6100, 6016, 3111, 4321]

17       1000      2100  [2010, 3102, 4001, 3011, 4200, 4010, 2110, 3000, 4023, 5321, 5010, 6525, 610...

18       5010      6016                                                               [6525, 6100, 6016]

19       3033      4311                                                                     [4113, 4311]

一个问题是你没有将数据框传递给函数，所以你需要注意你给它命名的内容。你可以通过找到一种方法来实现这个函数，而不依赖于一个名为df的数据框存在来改进它。

- ConorSheehan1

---

抱歉，我在缩减代码以便关注函数的递归部分时失去了一些上下文。感谢您的提示！ - taky2

这个建议非常好，但不完全是我要找的格式。然而，结合这个答案和@amanbirs的答案可能会非常有价值。 - taky2