Как получить цепочку всех связанных ребер на DAG (pandas \ networkx)

Question

у меня есть DAG, который я конвертирую в pandas_DF

DF:

df=pd.DataFrame({'dad':[1, 2, 3, 4,5, "T1", "T2"],
          'children':["T1","T1","T2","T2",6,"T3","T3"]})
print (df)

Я хочу получить список всех узлов \ ребер, которые связаны в моем DAG (график ), поэтому это будет выглядеть так:

df=pd.DataFrame({'dad':[1, 2, 3, 4,5, "T1", "T2","T3"],
          'children':["T1","T1","T2","T2",6,"T3","T3","X"],
           'chain':[0,0,0,0,0,[1,2],[3,4],[1,2,3,4,"T1","T2"]] })

Мне нравится знать связь между ребрами по всей цепочке, например, новый столбец «цепочка». это может быть новый столбец, как здесь, и порядок тоже не важен

Я использую pandas и networkx, но я буду рад узнать новую библиотеку DAG, например networkx для python.

График выглядит так, как будто внутри него 2 дерева введите описание изображения здесь

Answer 1

Вы можете использовать networkx, как предлагает @QuangHoang, вот так:

import pandas as pd
import networkx as nx

df=pd.DataFrame({'dad':[1, 2, 3, 4,5, "T1", "T2"],
          'children':["T1","T1","T2","T2",6,"T3","T3"]})
G = nx.from_pandas_edgelist(df, 'dad','children', create_using=nx.DiGraph())
df['chain'] = df['dad'].transform(lambda x: list(G.predecessors(x)))
df

Вывод:

  dad children   chain
0   1       T1      []
1   2       T1      []
2   3       T2      []
3   4       T2      []
4   5        6      []
5  T1       T3  [1, 2]
6  T2       T3  [3, 4]

Я думаю, вам нужны все компоненты DiGraph ... вот способ сгенерировать эти подграфы с помощью цепочек.

import pandas as  pd
import networkx as nx

df=pd.DataFrame({'dad':[1, 2, 3, 4,5, "T1", "T2"],
          'children':["T1","T1","T2","T2",6,"T3","T3"]})
G = nx.from_pandas_edgelist(df, 'dad','children', create_using=nx.DiGraph())
df['chain'] = df['dad'].transform(lambda x: list(G.predecessors(x)))


w_list = list(nx.weakly_connected_components(G))
df_comp = pd.DataFrame({'dad': [list(n)[-1] for n in w_list], 
              'children':['X' for _ in w_list], 
              'chain': [list(x) for x in w_list]})

df_out = pd.concat([df, df_comp])
df_out

Вывод:

  dad children                     chain
0   1       T1                        []
1   2       T1                        []
2   3       T2                        []
3   4       T2                        []
4   5        6                        []
5  T1       T3                    [1, 2]
6  T2       T3                    [3, 4]
0  T3        X  [1, 2, 3, 4, T1, T2, T3]
1   6        X                    [5, 6]

Answer 2

я стараюсь, код выглядит хорошо, но я получаю ошибку

df=pd.DataFrame({'dad':[1, 2, 3, 4,5, "T1", "T2"],
          'children':["T1","T1","T2","T2",6,"T3","T3"]})
G = nx.from_pandas_edgelist(df, 'dad','children', create_using=nx.DiGraph())
df['chain'] = df['dad'].transform(lambda x: list(G.predecessors(x)))

df_comp = pd.DataFrame({'dad': [list(n)[-1] for n in w_list], 
              'children':['X' for _ in w_list], 
              'chain': [list(x) for x in list(nx.weakly_connected_components(G))]})

df_out = pd.concat([df, df_comp])

ValueError: все массивы должны быть одинаковой длины