Получить все непосредственно промежуточные и конечные родительские узлы дочернего узла во фрейме данных pandas

Question

У меня есть фрейм данных с родительскими дочерними отношениями, который выглядит следующим образом:

**child                Parent              relationship**

   A1x2                 bc11                direct_parent
   bc11                 Aw00                direct_parent
   bc11                 Aw00                ultimate_parent
   Aee1                 Aee0                direct_parent
   Aee1                 Aee0                ultimate_parent

Я хотел бы получить всех предков для всех дочерних узлов в новом фрейме данных. Результат будет выглядеть примерно так:

node                   ancesstory_tree

A1x2                    [A1x2,bc11,Aw00]   
Aee1                    [Aee1,Aee0]

Примечание. В реальном наборе данных может быть много прямых узлов-предшественников между дочерним и конечным родителем.

Answer 1

Другой подход, использующий from_pandas_edgelist и ancestors из пакета networkx:

import networkx as nx

# Create the Directed Graph
G = nx.from_pandas_edgelist(df,
                            source='Parent',
                            target='child',
                            create_using=nx.DiGraph())

# Create dict of nodes and ancestors
ancestors = {n: {n} | nx.ancestors(G, n) for n in df['child'].unique()}

# Convert dict back to DataFrame if necessary
df_ancestors = pd.DataFrame([(k, list(v)) for k, v in ancestors.items()],
                            columns=['node', 'ancestry_tree'])

print(df_ancestors)

[ out]

   node       ancestry_tree
0  A1x2  [A1x2, Aw00, bc11]
1  bc11        [bc11, Aw00]
2  Aee1        [Aee1, Aee0]

---

Чтобы отфильтровать «промежуточных детей» из выходной таблицы, вы можете отфильтровать по последним дочерним элементам только с помощью метода out_degree - там, где последние дочерние элементы должны иметь выходную степень == 0

last_children = [n for n, d in G.out_degree() if d == 0]

ancestors = {n: {n} | nx.ancestors(G, n) for n in last_children}

df_ancestors = pd.DataFrame([(k, list(v)) for k, v in ancestors.items()],
                            columns=['node', 'ancestry_tree'])

[out]

   node       ancestry_tree
0  A1x2  [A1x2, Aw00, bc11]
1  Aee1        [Aee1, Aee0]

Answer 2

• Создать словарь отношений
• Пройти через каждый child, который также не является parent
• Отслеживать путь предков, а также set потомков
  • Это важно, потому что мы хотим завершить while l oop, если мы столкнемся с узлом, который уже был замечен

---

relate = dict(zip(df.child, df.Parent))
paths = {}
nodes = {}
for child in cp.keys() - {*cp.values()}:
    paths[child] = [child]
    nodes[child] = {child}
    parent = relate[child]
    while parent in relate and parent not in nodes[child]:
        paths[child].append(parent)
        nodes[child].add(parent)
        parent = relate[parent]
    paths[child].append(parent)

pd.Series(paths).rename_axis('node').reset_index(name='ancestry_tree')


   node       ancestry_tree
0  Aee1        [Aee1, Aee0]
1  A1x2  [A1x2, bc11, Aw00]