Finding all paths in a graph (can tabling help?)

Help!
1

This is a simplified version of a problem I’m working on. There exists a solution without tabling, but it would be more elegant if I could use tabling instead.

Here’s a modified version of the code in Example 2: avoiding non-termination that also returns the path between two points [Note: the original post was missing one clause; I’ve edited this to including the missing code]:

:- table connection/3.
connection(X, Y, Path) :-
    connection(X, Z, Path1),
    connection(Z, Y, Path2),
    append(Path1, Path2, Path).
connection(X, Y, [X->Y]) :-  % <=== This clause was missing
connection(X, Y, [X->Y]) :-
    connection(Y, X).

connection('Amsterdam', 'Schiphol').
connection('Amsterdam', 'Haarlem').
connection('Schiphol', 'Leiden').
connection('Haarlem', 'Leiden').

print_connection_3 :-
    forall(connection(X,Y,Path),
           writeln(X->Y:Path)).

This code goes into an infinite loop because of the third argument (interestingly, it doesn’t run out of stack).

Adding a lattice option to the table directive doesn’t do what I want because that only returns one result, for example a minimal path.

So, two questions:

Is there a way to mark the 3rd argument as “don’t table this”? (I think the answer is “no”, from a conversation I had a few years ago with David S. Warren.)

If I use the connection/2 code in the example (no 3rd argument collecting the path), is there a way to read the tries for the table, to construct all the paths? I wrote this code to dump the trie, but I don’t know how to interpret it:

print_connection_2 :-
    forall(connection(X,Y), 
           writeln(X->Y)).

print_trie :-
    forall(current_table(Varient, Trie),
           ( setof(K-V, trie_gen(Trie, K, V), KVs),
             format('~q: ~q~n', [Varient,KVs])
           )).

?- print_connection_2.
?- print_trie.
2

Using your code I get (using 8.1.19-6-ga3e8a558a-DIRTY):

?- print_connection_3.
Haarlem->Amsterdam:[(Haarlem->Amsterdam)]
Leiden->Haarlem:[(Leiden->Haarlem)]
Leiden->Amsterdam:[(Leiden->Haarlem),(Haarlem->Amsterdam)]
Leiden->Amsterdam:[(Leiden->Schiphol),(Schiphol->Amsterdam)]
Leiden->Schiphol:[(Leiden->Schiphol)]
Schiphol->Amsterdam:[(Schiphol->Amsterdam)]
true.

Which query gives you an infinite loop?

3

Oops, there’s one missing clause. The code should be (and I’ve edited the original posting to include this):

:- table connection/3.
connection(X, Y, Path) :-
    connection(X, Z, Path1),
    connection(Z, Y, Path2),
    append(Path1, Path2, Path).
connection(X, Y, [X->Y]) :-  % <=== This clause was missing
    connection(X, Y).
connection(X, Y, [X->Y]) :-
    connection(Y, X).

connection('Amsterdam', 'Schiphol').
connection('Amsterdam', 'Haarlem').
connection('Schiphol', 'Leiden').
connection('Haarlem', 'Leiden').

print_connection_3 :-
    forall(connection(X,Y,Path),
           writeln(X->Y:Path)).

If you replace [X->Y] with [] in the last two connection/3 clauses, then it works (without generating a path, of course).

4

Using mode directed tabling to keep only the first (or last) answer for the third argument:

:- table(connection(+, +, -)).

Gives:

?- pl::print_connection_3.
(Haarlem->Amsterdam):[(Haarlem->Amsterdam)]
(Haarlem->Haarlem):[(Haarlem->Amsterdam),(Amsterdam->Haarlem)]
(Haarlem->Schiphol):[(Haarlem->Amsterdam),(Amsterdam->Schiphol)]
(Haarlem->Leiden):[(Haarlem->Leiden)]
(Leiden->Haarlem):[(Leiden->Haarlem)]
(Leiden->Leiden):[(Leiden->Haarlem),(Haarlem->Leiden)]
(Leiden->Schiphol):[(Leiden->Schiphol)]
(Leiden->Amsterdam):[(Leiden->Haarlem),(Haarlem->Amsterdam)]
(Schiphol->Amsterdam):[(Schiphol->Amsterdam)]
(Schiphol->Haarlem):[(Schiphol->Amsterdam),(Amsterdam->Haarlem)]
(Schiphol->Schiphol):[(Schiphol->Amsterdam),(Amsterdam->Schiphol)]
(Schiphol->Leiden):[(Schiphol->Leiden)]
(Amsterdam->Haarlem):[(Amsterdam->Haarlem)]
(Amsterdam->Leiden):[(Amsterdam->Haarlem),(Haarlem->Leiden)]
(Amsterdam->Schiphol):[(Amsterdam->Schiphol)]
(Amsterdam->Amsterdam):[(Amsterdam->Haarlem),(Haarlem->Amsterdam)]
true.

I assume you don’t want the redundant solutions above?

5

But this doesn’t get all the paths for going from A to B. (I’m OK with duplicate solutions because they’re easily removed.) Here’s an example, using a fixed number of hops:

c(X, Y) :- connection(X, Y).
c(X, Y) :- connection(Y, X).

?- forall((c('Haarlem', A), c(A, B), c(B, 'Amsterdam')), format('Haarlem->~w->~w->Amsterdam~n', [A,B])).
Haarlem->Leiden->Schiphol->Amsterdam
Haarlem->Leiden->Haarlem->Amsterdam      % Loop through Leiden
Haarlem->Amsterdam->Schiphol->Amsterdam  % Loop through Amsterdam
Haarlem->Amsterdam->Haarlem->Amsterdam   % Loop through Amsterdam

Also, I don’t want the 3 solutions that have a loop in them, and would hope that tabling gets rid of them; but I’ll accept them (and get rid of them later) if the computation terminates.