Найти всех предков листовых узлов в дереве с пандами

Question

У меня есть таблица, которая имеет два столбца, «родитель» и «ребенок».Это загрузка из SAP (ERP) для таблицы SETNODE.Необходимо создать в Python информационный фрейм, в котором каждый уровень является отдельным столбцом по отношению к своему родительскому и всем предшествующим уровням.

В Python 3+.

Для полного отношения существует неизвестное (или постоянно меняющееся) количество уровней, поэтому не всегда можно определить максимальный уровень.Я хотел бы создать полную таблицу данных, которая показывает ВСЕ родительские / дочерние отношения для всех уровней.Сейчас это около 15 уровней, но, вероятно, может доходить до 20 и более с другими данными, с которыми я работаю.

Например (example_df) из двух столбцов:

example_df = pd.DataFrame({'parent:['a','a','b','c','c','f'],'child':['b','c','d','f','g','h']})

Чтобы получить выходной кадр данных (solution_example):

solution_example = pd.DataFrame({'child':['h','f','d'],'parent_1':['a','a','a'],'parent_2':['c','c','b'],'parent_3':['f', 'none', 'none']})

Answer 1

Это можно решить с помощью библиотеки networkx.Сначала создайте ориентированный граф из DataFrame, а затем найдите всех предков конечных узлов.

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