algorithm - 如何从 DAG 中删除“跳过”边缘？（如何只找到从每个节点到每个接收器的最长路径？）

Question

在两个单独的项目中，我都遇到过这个问题，但我仍然没有很好的解决方案，所以我认为值得在这里描述一下。考虑以下问题：

我有一组出现在语料库中的字符串及其计数。我想将计数合并到也出现在语料库中的任何子字符串中。

这是一个关闭但不正确的示例来演示它。我们创建了一个字符串的有向图，其中从每个节点到它的每个子字符串都存在一条边。然后我们按拓扑顺序对计数求和。

counts = {"hi":1, "hillo": 1,  "hillotoo":1, "hillotoothree": 1, "what": 1}

graph = nx.DiGraph()
graph.add_nodes_from(counts.keys())

for str1, str2 in combinations(graph.nodes, 2):
    if str1 in str2:
        graph.add_edge(str2, str1)
    elif str2 in str1:
        graph.add_edge(str1, str2)

for node in nx.topological_sort(graph):
    for neighbor in graph.neighbors(node):
        counts[neighbor] += counts[node]

最后，'hi 的计数应该是 4，hi + hillo + hillotoo + hillotoothree。但是，此代码会生成: {'hi': 8, 'hillo': 4, 'hillotoo': 2, 'hillotoothree': 1, 'what': 1}，因为还有更多通往 'hi' 的路径以指数方式求和。这是因为对于子字符串，根据定义，从每个字符串到其每个子字符串都有一条直接边。相反，我需要对从每个节点到图中从该节点到接收器的每条路径上的下一个较小子字符串的计数求和，并删除/避免从节点到节点的“跳过”边，进一步沿着路径到达接收器。

（注意：这个简单的字符串示例实际上有一个简单的解决方案：首先复制计数，然后只将原始计数添加到新计数中。但是，这仅是因为从每个字符串到其每个子字符串都有一条直接边，所以这个解决方案完全避开了图。在一般情况下，这个假设不成立。在那里，我们确实需要沿路径求和，但只需要沿从每个节点到每个接收器的最长路径求和，而不采取任何“跳过”边缘以避免过度计数。）

试试这个！谢谢。

标签： algorithmgraphgraph-algorithmdirected-acyclic-graphstopological-sort