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
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.