如何使用Pandas从层次数据结构中识别根节点

Question

我有一个数据表，里面有以下几列：Parent（父节点）、Parent_Rev（父节点版本）、Child（子节点）和ChildRev（子节点版本）。在这个结构中，Parent是父节点，而Child是子节点。Parent_Rev和ChildRev则记录了各自节点的不同版本。一个Child可能出现在Parent这一列中，并且它自己也可以有子节点，这些子节点在Child和Child_Rev这两列中表示。

这种层级关系会一直延续，直到找到一个Parent不再作为任何其他值的Child出现为止。

为了生成想要的输出，需要遍历所有的值，识别出所有可能的层级和组合，直到到达顶层节点。在检查可能的连接时，Node（节点）和Rev（版本）的组合应该被视为唯一的，而不仅仅是Node的值。

示例输入数据表：

Parent	Parent_Rev	Child	Child_REV
A1	1	B1	1
B1	1	C1	1
C1	1	D1	1
D1	1	E1	1
A2	1	B2	1
B2	1	C2	1
C2	1	C2	1
A3	1	B3	3
A4	1	B3	3

import pandas as pd

df1 = pd.DataFrame({'Node1': ['A1','B1','C1','D1','A2','B2','C2','A3','A4'],
                    'Node1_Rev': ['1','1','1','1','1','1','1','1','1'],
                    'Node2': ['B1','C1','D1','E1','B2','C2','C2','B3','B3'],
                    'Node2_Rev': ['1','1', '1','1','1','1','1','3','3']
}
)

示例输出数据表：

Root	Root_Rev	Parent	Parent_Rev	Child	Child_REV
A1	1	A1	1	B1	1
A1	1	B1	1	C1	1
A1	1	C1	1	D1	1
A1	1	D1	1	E1	1
A2	1	A2	1	B2	1
A2	1	B2	1	C2	1
A2	1	C2	1	C2	1
A3	1	A3	1	B3	3
A4	1	A4	1	B3	3

对于更大的数据集，有什么高效的方法可以生成输出，以更新所有父子输入组合的根和版本吗？

Answer 1

使用networkx来构建你的图，然后通过weakly_connected_components来找到每个子图的根节点，接着创建一个数据框（DataFrame）并使用merge进行合并：

G = nx.from_edgelist((zip(zip(df['Node1'], df['Node1_Rev']),
                          zip(df['Node2'], df['Node2_Rev']))),
                    create_using=nx.DiGraph)

roots = {v for v, d in G.in_degree() if d == 0}

mapper = {}
for c in nx.weakly_connected_components(G):
    r = next(iter(c & roots))
    for n in c:
        mapper[n] = r
        
out = (pd.DataFrame(mapper, index=['Root', 'Root_Rev']).T
         .merge(df, left_index=True, right_on=['Node1', 'Node1_Rev'],
                how='right')
      )

输出结果：

  Root Root_Rev Node1 Node1_Rev Node2 Node2_Rev
0   A1        1    A1         1    B1         1
1   A1        1    B1         1    C1         1
2   A1        1    C1         1    D1         1
3   A1        1    D1         1    E1         1
4   A2        1    A2         1    B2         1
5   A2        1    B2         1    C2         1
6   A2        1    C2         1    C2         1
7   A3        1    A3         1    B3         3
8   A4        1    A4         1    H4         3

图示：

每个子图可能有多个根节点

如果一个子图中可能有多个根节点，你需要调整上面的代码来保留所有根节点。不过，具体的处理方式是未定义的（你可以选择把它们放在一个列表中，或者展开成多行……）。

这里有一种通用的方法来将一个节点与它的实际根节点关联起来：

G = nx.from_edgelist((zip(zip(df['Node1'], df['Node1_Rev']),
                          zip(df['Node2'], df['Node2_Rev']))),
                    create_using=nx.DiGraph)

roots = {v for v, d in G.in_degree() if d == 0}

mapper = {}
for n in G:
    a = nx.ancestors(G, n) & roots
    mapper[n] = list(zip(*a)) if len(a)>1 else next(iter(a), n)
        
out = (pd.DataFrame(mapper, index=['Root', 'Root_Rev']).T
         .merge(df, left_index=True, right_on=['Node1', 'Node1_Rev'],
                how='right')
         #.explode(['Root', 'Root_Rev']) # optional
      )

输出结果：

        Root Root_Rev Node1 Node1_Rev Node2 Node2_Rev
0         A1        1    A1         1    B1         1
1         A1        1    B1         1    C1         1
2         A1        1    C1         1    D1         1
3         A1        1    D1         1    E1         1
4         A2        1    A2         1    B2         1
5         A2        1    B2         1    C2         1
6         A2        1    C2         1    C2         1
7         A3        1    A3         1    B3         3
8         A5        1    A4         1    B3         3
9         A5        1    A5         1    A4         1
10  (A5, A3)   (1, 1)    B3         3    B4         4 # this node has 2 roots

使用explode的输出结果：

   Root Root_Rev Node1 Node1_Rev Node2 Node2_Rev
0    A1        1    A1         1    B1         1
1    A1        1    B1         1    C1         1
2    A1        1    C1         1    D1         1
3    A1        1    D1         1    E1         1
4    A2        1    A2         1    B2         1
5    A2        1    B2         1    C2         1
6    A2        1    C2         1    C2         1
7    A3        1    A3         1    B3         3
8    A5        1    A4         1    B3         3
9    A5        1    A5         1    A4         1
10   A5        1    B3         3    B4         4 # exploded
10   A3        1    B3         3    B4         4 # into 2 rows

图示：