在Python中对分层父/子列表进行排序

Question

我对在 PYTHON 中管理父/子关系中的层次结构有一个小小的担忧。

为了提供一些背景信息，我有一个由 x 个字段组成的表。以下是我感兴趣的：

• 产品_id
• parent_ref
• child_ref

该表代表了几种产品的扁平结构（product_id = 车型）。

第一个父级是车身，我们在上面安装门、发动机支架、发动机，发动机本身由数百个零件等组成......

有些车型重复使用其他车辆的零件，相同的发动机，相同的离合器...

这是我的案例，我有一个大约 180 万行的文件，向我展示了每个产品的结构。

我想创建一个“级别”的概念，它是根据结构中的位置计算的。例如，我知道所有第一个子级（即级别 1）在父列中的值为“-1”。

`Ex: 
Product_id           Parent_ref            child_ref
BMW316E46              -1                  15G0001-013    --> First parent
BMW316E46              -1                  15G0001-014    --> Second parent
BMW316E46          15G0001-013             14G0009-001    --> First parent first child...
BMW316E46          15G0001-013             14G0017-001    --> First parent second child...
BMW316E46          15G0001-013             14G0018-001`   --> Each child can be (or not) a parent as well

我的目标是为每个产品（Product_id）制定一个结构，并为每个子项指定一个级别列，该列取决于父项，并且是可视的。也就是说，孩子的身份将是相对于父母的（我事先不知道可能有多少级）。

类似这样的事情：

Product_id    Parent_ref     Child_ref    Level (with visual identation)
BMW316E46       -1          15G0001-013     1
BMW316E46    15G0001-013    14G0009-001     __2
BMW316E46    15G0001-013    14G0017-001     __2
BMW316E46    14G0017-001    14G0017-001     ____3
BMW316E46       -1          15G0001-014     1
BMW316E46    15G0001-014    14G0009-001     __2
BMW316E46    15G0001-014    14G0017-001     __2

我在Python中尝试了类似的方法，为每个循环创建一个数组以找出不同的孩子，但它仅适用于第一个循环，因为我需要分离每个父母的不同孩子......

df = pd.read_csv("file.csv")


for index, row in df.iterrows():
    if row['parent_ref'] == "'-1":
        array_lvl_1.append(row['child_ref'])
        parent_level = alc[count]
        df.loc[index, 'level'] = parent_level
        count += 1


for index, row in df.iterrows():
    if row['parent_ref'] in array_lvl_1:
        for value in array_lvl_1:
            array_lvl_1_1.append(row['child_ref'])
            df.loc[index, 'level'] = alc[count2]
            count2 += 1

但它不是递归的，它迫使我创建与级别一样多的表，而且我事先不知道级别数。

Answer 1

由于这是一个图形问题，我将使用

networkx

在

topological_generations

的帮助下获取每个节点的深度，并使用

dfs_edges

以 DFS 顺序生成边列表：

import networkx as nx

def make_hierarchy(g):
    G = nx.from_pandas_edgelist(g, create_using=nx.DiGraph,
                                source='Parent_ref', target='Child_ref')
    depth = {n: f'{"_"*(d-1)}{d}' for d, l in
             enumerate(nx.topological_generations(G))
             for n in l}
    return (pd
       .DataFrame(nx.dfs_edges(G), columns=['Parent_ref', 'Child_ref'])
       .assign(Product_id=g.name,
               Level=lambda d: d['Child_ref'].map(depth)
              )
    )[['Product_id', 'Parent_ref', 'Child_ref', 'Level']]

# compute the hierarchy per group
out = df.groupby('Product_id', group_keys=False).apply(make_hierarchy)

# optional, left justify the strings
out['Level'] = out['Level'].str.ljust(out['Level'].str.len().max())

输出：

  Product_id   Parent_ref    Child_ref Level
0  BMW316E46           -1  15G0001-013   1  
1  BMW316E46  15G0001-013  14G0009-001   _2 
2  BMW316E46  15G0001-013  14G0017-001   _2 
3  BMW316E46  14G0017-001  14G0018-001   __3
4  BMW316E46           -1  15G0001-014   1  

使用的输入（与问题中的输入略有不同，有 3 个级别）：

0  BMW316E46           -1  15G0001-013
1  BMW316E46           -1  15G0001-014
2  BMW316E46  15G0001-013  14G0009-001
3  BMW316E46  15G0001-013  14G0017-001
4  BMW316E46  14G0017-001  14G0018-001

图表：