Azure Cosmos图中指定源最长公共子序列的Gremlin查询问题

问题背景 #

通过Gremlin查询语句 g.V().hasLabel('A').repeat(out()).until(__.not(out())).path().by('id') 获取到指定源的所有最长路径，返回结果包含三条路径：

• ["k", "B", "C"]
• ["A", "B", "E"]
• ["D", "B", "E"]

需要从这些路径中提取出最长公共子序列 B,E，该子序列在路径["A", "B", "E"]和["D", "B", "E"]中重复出现。

实现思路 #

核心是对比所有路径的子序列，找出在至少两条路径中存在的最长子序列：

1. 确认所有路径长度一致（本次案例中均为3）
2. 两两配对路径，计算每对的最长公共子序列
3. 从所有公共子序列中筛选出长度最长的结果

示例代码 #

paths = [
    ["k", "B", "C"],
    ["A", "B", "E"],
    ["D", "B", "E"]
]

common_subsequences = set()

# 遍历所有路径对，计算最长公共子序列
for i in range(len(paths)):
    for j in range(i+1, len(paths)):
        path1, path2 = paths[i], paths[j]
        m, n = len(path1), len(path2)
        
        # 动态规划表初始化
        dp = [[0]*(n+1) for _ in range(m+1)]
        for x in range(1, m+1):
            for y in range(1, n+1):
                if path1[x-1] == path2[y-1]:
                    dp[x][y] = dp[x-1][y-1] + 1
                else:
                    dp[x][y] = max(dp[x-1][y], dp[x][y-1])
        
        # 回溯获取子序列
        x, y = m, n
        subseq = []
        while x > 0 and y > 0:
            if path1[x-1] == path2[y-1]:
                subseq.append(path1[x-1])
                x -= 1
                y -= 1
            elif dp[x-1][y] > dp[x][y-1]:
                x -= 1
            else:
                y -= 1
        
        if subseq:
            common_subsequences.add(tuple(reversed(subseq)))

# 筛选最长公共子序列
longest_subseq = max(common_subsequences, key=lambda s: len(s))
print(f"最长公共子序列: {list(longest_subseq)}")

说明 #

• 代码通过动态规划计算两两路径的最长公共子序列，再通过回溯还原具体序列
• 最终得到的B,E是符合需求的、出现次数最多的最长公共子序列

内容的提问来源于stack exchange，提问作者place holder