python - Getting all descendants of a parent from a pandas dataframe parent child table

Question

I have a Pandas dataframe containing parent ids and child ids. I need help building an updated dataframe listing every descendant of each parent.

For clarification on what the output should look like, here is a post on dba.stackexchange using SQL to accomplish what I am trying to do in python.

Here's an example of the input DataFrame:

     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

Below is the actual example data hardcoded as a 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]
    }
)

Here is my attempt to at using a recursive list building strategy

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

...which currently just duplicates the data because I am not correctly traversing the tree.

The format of the output should follow the format of the input. I want a two column table of parent and child IDs as demonstrated in the example output below.

Here's the expected output from the above data:

    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

Bonus points for adding an additional column of depth/distance from parent_id to child_id for each row. TIA

Answer 1

This should return the parent and child ids in the two columns that you wanted:

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