How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)

Question

In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem:

I have a set of strings that appear in a corpus with their counts. I would like to merge the counts into any substrings that also appear in the corpus.

Here's a close, but incorrect example to demonstrate it. We create a directed graph of strings, where an edge exists from each node to each of its substrings. We then sum counts in topological order.

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]

In the end, 'hi's count should be 4, hi + hillo + hillotoo + hillotoothree. However, this code produces: {'hi': 8, 'hillo': 4, 'hillotoo': 2, 'hillotoothree': 1, 'what': 1}, because there's many more paths to 'hi' that get exponentially summed. This is because with substrings, there is a direct edge from every string to every one of its substrings by definition. Instead, I need to sum counts from each node to the next smaller substring on each path from that node to a sink in the graph, and remove/avoid "skip" edges from nodes to nodes further down paths to a sink.

(NOTE: This simple string example actually has a straightforward solution: copy the counts first, and only add the original counts to the new ones. However, this works only because there is a direct edge from every string to every one of its substrings, so this solution sidesteps the graph entirely. In the general case, this assumption does not hold. There, we do need to sum along paths, but only along the longest path from each node to each of its sinks, without taking any "skip" edges to avoid overcounting.)

Have a crack at this! Thanks.

Answer 1

On the question from title

For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order: $$ d(v)= \begin{cases} 0\text{ if } v = s\\ -\infty \text{ if } v \not= s \land v \in S\\ 1 + max_{(v, u) \in E} d(u) \end{cases} $$ You can run this algorithm for every $s \in S$ to get the solution for whole problem.

On your problem

Unfortunately your approach won't work, look at this graph:

A
|\
B |
| D
C |
|/
E

If you would look only for longest path to E from A, you would ignore existence of node D. So unfortunately I think you need to go with more "brute force" approach where you will have to run BFS/DFS from every node in the graph and check the number of reached nodes.