python - 对列进行排序，使一列位于另一列的值之后

Question

我有一个表示公司层次结构树的大型数据集。举个例子，我可能有如下内容:

Child                 Parent
273500                273500
20574624              273500
2202652               1879450
19933526              1879450
18000796              18352628
18352628              19770000
1359996               20574624
1879450               20574624
18441258              20574624
20637582              20574624
20840426              20574624
20844632              20574624
20934910              20574624
20965442              20574624
21193122              20574624
21194666              21193122
19770000              20574624
19681810              18352628
19931554              20574624
18382902              1879450
19780666              1879450
20631784              20574624

可以看到，第一行是父节点。

我想做的是按照这样一种方式对数据进行排序，即它实际上代表一个层次结构，从顶部开始到层次结构的底部。我想这样做的原因是因为我想计算树的高度。为此，首先我需要构建树。我已经知道如何使用 treelib 包 构建树。我现在的问题是，如果我有一个包含数千行的大型数据集，我如何才能以能够构建树的方式对数据进行排序。

我已经尝试过使用 pandas 中的 .sort_values 按子列中的值对父列进行排序。然而，这并没有按照我想要的方式工作。我还尝试按功能对组执行此操作，并根据以下问题以某种方式为行赋予一定的排名:pandas sort a column by values in another column .

这不适用于大型数据集。

下面是我想要得到的结果。

Child         Parent
273500        273500   # The first row is the parent row
20574624      273500   # I want all children that belong to this parent node
1879450       20574624 #  
18441258      20574624
19770000      20574624
19931554      20574624
20631784      20574624
20637582      20574624
20840426      20574624
20844632      20574624
20934910      20574624
20965442      20574624
21193122      20574624
2202652       1879450 # Now, I want all the children that belong to 1879450
18382902      1879450 # and so on
19780666      1879450
19933526      1879450
18352628      19770000
18000796      18352628
19681810      18352628
1359996       20574624
21194666      21193122

对于这么小的数据集，可以轻松地手动排序。但是对于包含数千行的大型数据集，这可能有点麻烦。

Answer 1

如果我没理解错你想要的是topological sort , 我建议你使用 networkx 中实现的那个:

edges = df[df.child != df.parent].reset_index()
dg = nx.from_pandas_edgelist(edges, source='parent', target='child', create_using=nx.DiGraph)
order = list(nx.lexicographical_topological_sort(dg))

result = df.set_index('parent').loc[order, :].dropna().reset_index()
print(result)

输出

      parent       child
0     273500    273500.0
1     273500  20574624.0
2   20574624   1359996.0
3   20574624   1879450.0
4   20574624  18441258.0
5   20574624  20637582.0
6   20574624  20840426.0
7   20574624  20844632.0
8   20574624  20934910.0
9   20574624  20965442.0
10  20574624  21193122.0
11  20574624  19770000.0
12  20574624  19931554.0
13  20574624  20631784.0
14   1879450   2202652.0
15   1879450  19933526.0
16   1879450  18382902.0
17   1879450  19780666.0
18  19770000  18352628.0
19  18352628  18000796.0
20  18352628  19681810.0
21  21193122  21194666.0

如果你想保持列的顺序 (['child', 'parent']) 只需这样做:

result = df.set_index('parent').loc[order, :].dropna().reset_index().reindex(['child', 'parent'], axis=1)

确保导入所需的库:

import networkx as nx
import pandas as pd