Найти самую длинную цепочку родитель-потомок в кадре данных

Question

Сценарий

У меня есть кадр данных.Каждая строка содержит элемент, который может быть, но не обязательно, связан с родительским элементом или дочерним элементом, например, двусвязным списком.Строки не отсортированы, но идентификатор родительского элемента должен быть меньше идентификатора дочернего элемента.

import pandas as pd
import numpy as np

df = pd.DataFrame(columns=['Item Id', 'Parent Id', 'Child Id'],
                  data=[[1006, np.nan, np.nan],
                        [1001, np.nan, 1005],
                        [1004, 1003, 1007],
                        [1003, 1002, 1004],
                        [1005, 1001, np.nan],
                        [1002, np.nan, 1003],
                        [1007, 1004, np.nan]
                        ])
print(df)
#    Item Id  Parent Id  Child Id
# 0     1006        NaN       NaN
# 1     1001        NaN    1005.0
# 2     1004     1003.0    1007.0
# 3     1003     1002.0    1004.0
# 4     1005     1001.0       NaN
# 5     1002        NaN    1003.0
# 6     1007     1004.0       NaN

Таким образом, кадр данных содержит 3 цепочки:

• 1001 => 1005
• 1002 => 1003 => 1004 => 1007
• 1006

Вопрос

Как найти длинудлинная цепочка в этом фрейме данных?(т.е. 3 в данном кадре данных)

Answer 1

По предложению @ bli я преобразовал фрейм данных в ориентированный граф, используя networkx , и получил ответ с помощью dag_longest_path() и dag_longest_path_length().

import networkx as nx
G=nx.from_pandas_edgelist(df[~df['Child Id'].isna()], 'Item Id', 'Child Id', 
                          edge_attr=True, create_using=nx.DiGraph())

Выход

>>> print(nx.dag_longest_path(G))
[1002, 1003, 1004, 1007.0]
>>> print(nx.dag_longest_path_length(G))
3

Answer 2

AFAIK, ни pandas, ни лежащий в основе numpy не будут хороши в решении вопроса о графике.

Но вы можете представить каждую цепочку списком, построить список всех цепочек, а затем отсортировать их.Я использовал бы вспомогательный dict, чтобы связать каждый элемент с его цепочкой:

chains = []
seen = {}

for _, row in df.sort_values("Item Id").iterrows():
    itemId = row['Item Id']
    childId = row['Child Id']
    if itemId in seen:
        chain = seen[itemId]
    else:                                     # this is a new chain
        chain = seen[itemId] = [itemId]
        chains.append(chain)
    if not np.isnan(childId):                 # add the child to the end of the chain
        seen[childId] = chain
        chain.append(childId)
chains.sort(key=lambda x: len(x))             # and sort the list of chains

(Этот алгоритм использует свойство, согласно которому идентификатор родительского элемента должен быть меньше, чем идентификатор дочернего элемента)

СВаш входной фрейм данных дает:

>>> print(chains)
[[1006.0], [1001.0, 1005.0], [1002.0, 1003.0, 1004.0, 1007.0]]

Answer 3

Это один из способов сделать это.Это НЕ оптимизировано вообще, но оно даст вам то, что вы хотите, без рекурсии:

data = [[1006, None, None],
        [1001, None, 1005],
        [1004, 1003, 1007],
        [1003, 1002, 1004],
        [1005, 1001, None],
        [1002, None, 1003],
        [1007, 1004, None]
    ]


class Node:
    def __init__(self, value, parent=None, child=None):
        self.value = value
        self.parent = parent
        self.child = child


nodes = {}
parent_ids = []

for entry in data:
    (itm, parent, child) = entry
    nodes[itm] = Node(itm, parent, child)
    if parent is None:
        parent_ids.append(itm)

for parent_id in parent_ids:
    chain = [str(parent_id)]
    node = nodes[parent_id]
    while node.child is not None:
        chain.append(str(node.child))
        node = nodes[node.child]
    print(" -> ".join(chain))

Вывод:

1006
1001 -> 1005
1002 -> 1003 -> 1004 -> 1007

Answer 4

Я бы взял всех родителей, которые имеют 'np.nan' в их родительском идентификаторе.рекурсивно проверять каждого родителя, пока не найдет самую длинную цепочку.Или же можно сделать и обратное, ищите те, у кого 'np.nan' в их Child Id, они являются последней частью цепочки и рекурсивно возвращаются до тех пор, пока не останется родитель.