Find All The Ancestors Of Leaf Nodes In A Tree With Pandas

I have a table that has two columns, 'parent' and 'child'. This is a download from SAP (ERP) for SETNODE table. Need to create a dataframe in python that has each level as it's own

Solution 1:

This can be solved using the networkx library. First, build a directed graph from the DataFrame, and then find all ancestors of the leaf nodes.

import networkx as nx

leaves = set(df.child).difference(df.parent)
g = nx.from_pandas_edgelist(df, 'parent', 'child', create_using=nx.DiGraph())
ancestors = {
    n: nx.algorithms.dag.ancestors(g, n) for n in leaves
}

(pd.DataFrame.from_dict(ancestors, orient='index')
   .rename(lambda x: 'parent_{}'.format(x+1), axis=1)
   .rename_axis('child')
   .fillna(''))

      parent_1 parent_2 parent_3
child                           
h            a        c        f
g            a        c         
d            a        b