Menu
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
308
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
As long as your IDs never have cycles, I think this should work
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
Returns:
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]
One problem is that you don't pass the dataframe to the function here, so you need to be careful about what you name it. You could probably improve it by finding a way to implement this function without the inner dfs function relying on a dataframe named df existing.
34
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
