Longest path problems and tabling

Help! Algorithm
1

I’m coding a dynamic programming approach to a longest path problem (in a directed acyclic graph). The vertices are naturally represented by pairs of positive integers. The edges are easy to verify but a little tricky to generate (few correct edges among many candidates).

Now tabling for a predicate pLength(V,L) that “returns” the length L of the longest path starting from the vertex V seems attractive since to find L one needs only to search for the maximum length of paths over neighbors of V and increase that by one. To do so efficiently would seem to require an efficient way to generate the edges that begin at V and connect to neighbors of V: edge(V,W). (The graph has no cycles, so this means the vertices appear in directed chains.)

I see there is an older thread, Finding all paths in a graph (can tabling help?), so I’ll look there next. However at first glance it seems to dwell on the issue that when a graph is not directed, path following can lead to infinite looping.

My thought about generating the edges to begin with is to use a dynamic predicate to assert them all (up to some moderate limit) before calling the pLength predicate. In other words, build the graph once and for all (asserting the vertices and edges that are of interest).

I think this might make a good test case for various flavors of tabling.

2

What might work is anwer subsumption or mode directed tabling.

3

Noting this mostly for others that may find this topic and want some other ideas.

I don’t know if this will work (thinking memory or time constraints for large graphs) for your particular problem but is something I would explore.

Use a topological sort. top_sort/2

4

Thanks, Eric: That’s an interesting idea. My intended application is a DAG with a somewhat natural “grading” (it models a game in which a positive number of red and/or blue candies are eaten at each step).

What a topological sort does for you is impose a total ordering on vertices that is compatible with partial ordering of the DAG. It might be useful in reducing the search space for some problems.