有条件的最长路径查找

Question

我正在尝试解决 Python/Pandas 中的一个问题，我认为这与最长路径算法密切相关。我正在使用的 DataFrame 具有以下结构：

import numpy as np 
import pandas as pd

data = {
    "cusID": ["001", "001", "001", "001", "001", "001", "002", "002", "002"],
    "start": ["A", "B", "C", "D", "A", "E", "B", "C", "D"],
    "end": ["B", "C", "D", "A", "E", "A", "C", "D", "E"]
}
df = pd.DataFrame(data)
print(df)

  cusID start end
0   001     A   B
1   001     B   C
2   001     C   D
3   001     D   A
4   001     A   E
5   001     E   A
6   002     B   C
7   002     C   D
8   002     D   E

对于每个客户，我想找到不包含 A 的最长序列。例如，对于客户 001，可以查看序列如下：

A -> B -> C -> D -> A -> E -> A

其中B -> C -> D是长度为 3 的最长序列。

我正在寻找的结果数据帧如下：

  cusID longestSeq
0   001          3
1   002          4

虽然我无法编写太多代码来解决这个问题，但这里有一些我的想法：首先，很明显我需要按 cusID 对原始 DataFrame 进行分组，以分别分析两个序列中的每一个。我的一个想法是应用一些函数将 DataFrame 转换为这种格式：

  cusID                       seq
0   001     [A, B, C, D, A, E, A]
1   002              [B, C, D, E]

然后分别处理每个列表，并使用某种计数器来获取排除 A 的路径长度的最大值。我的问题是将该逻辑转录为代码（如果正确）。任何帮助，将不胜感激。

Answer 1

第一步是对序列进行归一化。

seqs = pd.concat([
    df.drop(columns="end").rename(columns={"start":"node"}),
    df.groupby("cusID").tail(1).drop(columns="start").rename(columns={"end":"node"})
])
seqs = seqs.sort_values("cusID", kind="mergesort").reset_index(drop=True)

>>> seqs
   cusID node
0    001    A
1    001    B
2    001    C
3    001    D
4    001    A
5    001    E
6    001    A
7    002    B
8    002    C
9    002    D
10   002    E

然后，使用zero_runs我们定义：

def longest_non_a(seq):
    eqa = seq == "A"
    runs = zero_runs(eqa)
    return (runs[:,1] - runs[:,0]).max()
    
result = seqs.groupby("cusID")["node"].apply(longest_non_a)

>>> result
cusID
001    3
002    4
Name: node, dtype: int64