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.