Сортировать столбец так, чтобы один столбец следовал значениям из другого столбца.

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 package. Теперь моя проблема в том, что если у меня большой набор данных, состоящий из тысяч строк, как я могу упорядочить свои данные таким образом, чтобы я мог построить дерево.

Я уже пытался отсортировать данныеРодительский столбец по значениям в дочернем столбце, используя .sort_values ​​в pandas. Это, однако, не сработало так, как я хотел. Я также попытался сделать это с группировкой по функциям и каким-то образом присвоить строкам определенный ранг на основе этого вопроса: панды сортируют столбец по значениям в другом столбце .

Это не сработало для большого набора данных.

Ниже приведен результат, который я хочу получить.

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

Если я правильно понял, что вы хотите использовать топологическую сортировку , я предлагаю вам использовать ту, которая реализована в 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

Answer 2

Определите следующую функцию:

def getDescendants(curr, par, level):
    res = [[curr, par, level]]
    children = df.query('Parent == @curr')
    for n in children.Child:
        if n != par:
            deeper = getDescendants(n, curr, level + 1)
            if len(deeper) > 0:
                res.extend(deeper)
    return res

Затем получите идентификатор «Родителя всех родителей» (из строки 0):

hd = df.iloc[0, 0]

и вызовите вышеуказанную функцию:

pd.DataFrame(getDescendants(hd, hd, 1), columns=['Child', 'Parent', 'Level'])

Эта функция делает еще больше. Он также дает уровень каждого человека в иерархии.

Альтернативный способ найти «Родителя всех родителей»

Если «Родитель всех родителей» может находиться в Для любой строки (необязательно в первой) требуется другой подход.

Если исходный DataFrame содержит дерево иерархии single , корневой узел можно прочитать как: hd = df.query('Parent == Child').iloc[0,0]. Затем создайте дерево иерархии, как указано выше.

Если существует несколько деревьев иерархии, то:

• df.query('Parent == Child').iloc[0] получает Series "корневых" идентификаторов.
• Вы должны написать цикл для каждого элемента из этого Series , вызвать getDescendants (id, id, 1) для текущего id и собирать результаты (например, как элементы списка).
• Конкатить их (по вертикали).

Answer 3

Я собираюсь сделать это в ванильном Python, а не с помощью панд. По сути, вы хотите создать набор деревьев и затем пройти их от корневых узлов этих деревьев.

Допустим, вы уже проанализировали данные и можете начать с некоторого списка processes изструктура List[Tuple[int, int]].

processes = [
    (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),
]

Мы можем представить все узлы в нашем дереве как Dict[int, List[int]] родительских дочерних отношений. Следующий метод может быть вызван в кадре путем вызова sort_processes(df.values.tolist()). Результат можно преобразовать обратно в панд, позвонив pandas.DataFrame(result, columns=['Child', 'Parent']):

from collections import defaultdict
from typing import Dict, List, Iterable, Tuple

def sort_processes(processes: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    # initialize the nodes
    nodes: Dict[int, List[int]] = defaultdict(list)
    for child, parent in processes:
        nodes[parent].append(child)

    # walk and yield pairs
    def walk_tree(parent: int) -> Iterable[Tuple[int, int]]:
        for child in sorted(nodes[parent]):
            yield (child, parent)
            # avoid infinite loops
            if parent != child:
                yield from walk_tree(child)

    # start at top level parents
    parents = [parent for child, parent in processes if parent == child]
    return list(
        pair for parent in sorted(parents) for pair in walk_tree(parent)
    )

Вызвав sort_processes(processes) Возвращает:

[
    (273500, 273500),
    (20574624, 273500),
    (1359996, 20574624),
    (1879450, 20574624),
    (2202652, 1879450),
    (18382902, 1879450),
    (19780666, 1879450),
    (19933526, 1879450),
    (18441258, 20574624),
    (19770000, 20574624),
    (18352628, 19770000),
    (18000796, 18352628),
    (19681810, 18352628),
    (19931554, 20574624),
    (20631784, 20574624),
    (20637582, 20574624),
    (20840426, 20574624),
    (20844632, 20574624),
    (20934910, 20574624),
    (20965442, 20574624),
    (21193122, 20574624),
    (21194666, 21193122),
]