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

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

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?

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

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?

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.