Get detailed path in PROLOG wide search

Question

Given the width search on graphs in Prolog, a graph where one node connects to the other via the connected fact(a,b). connected(b,c). connected(b,e). And so on, the algorithm would normally work by returning to the user the shortest route between a starting node, the first node or not, and the destination node, which could also be either. The algorithm would look like this:

/* Chegar de A a Z, retornando caminho percorrido P,
   comecando de um caminho vazio
*/
path(A,Z,P) :- path1(A,Z,[],P).

/* Se ja' cheguei ao destino, parar a busca e incluir
   destino na lista contendo o caminho percorrido */
path1(Z,Z,L,L).

/* Se ainda nao cheguei no destino, encontrar caminho
   parcial de A para Y,  adicionar `a lista contendo o
   caminho parcial e continuar a busca a partir de Y
*/
path1(A,Z,L,P) :- (conectado(A,Y);conectado(Y,A)),
       \+ member(Y,L),
      path1(Y,Z,[Y|L],P). /* encontra caminho parcial de */
                          /* Y a Z */

However I seek something different for my application, I need not receive the shortest path between the starting point and the destination, but rather I want to receive the virtual path that the algorithm has traveled to obtain this result. That is, if he had to check all of us of the same width, only then to increase the depth, since this that the search in width does obviously, I want to receive not the direct path to the goal, but the figurative path that the algorithm had to do, that is, that the way he returns me contains us all in the same width before passing to the next level, instead of not including them in the answer to seeing that there is a shorter path. Basically I do not want to receive the best ideal path from X to Y, but rather the path that the algorithm searches in width had to go through in the graph to return me this path, as if it were a debug

Answer 1

Its implementation is not of search in width, but of depth. Prolog’s SLD resolution has this characteristic of always looking for the rules in the order they are presented in the program, which in your case causes conectados(A, Y) as in a graph.

That said, I see 3 ways you can get what you want:

1. Manually, using trace to follow all internal steps;
2. With good old printf-oriented debug, printing the way explored so far;
3. Accumulating the steps in a changing term.

Let’s start with alternative #2 with the function format/2. In my version, the edges of the graph are stored as caminho(A, B), and I keep the depth reached from the origin. This would allow to reconstruct a tree of the attempts.

conectado(A, B) :- caminho(A, B); caminho(B, A).

path(estação(A), estação(Z), P) :-
    path_(A, Z, [A], P1, 0),
    reverse(P1, P).

path_(Z,Z,L,L, _).
path_(A,Z,L,P, Depth) :-
    conectado(A, Y),
    \+ member(Y, L),
    %%%%
    format("#~d: caminho(~w, ~w)~n", [Depth, A, Y]),
    %%%%
    Depth1 is Depth+1,
    path_(Y, Z, [Y|L], P, Depth1).

In alternative #3, we will use the predicate nb_setarg/3, that changes the argument of a struct in a changeable way, without undoing in the backtrack.

Note that Debug receives debug([]) initially, but as it is modified as part of the search, writeln(Debug) will print something other than the initial -- an operation that is not logical!

conectado(A, B) :- caminho(A, B); caminho(B, A).

path(estação(A), estação(Z), P) :-
    Debug = debug([]),
    path(estação(A), estação(Z), P, Debug),
    writeln(Debug).

path(estação(A), estação(Z), P, Debug) :-
    path_(A, Z, [A], P1, 0, Debug),
    reverse(P1, P).

path_(Z,Z,L,L, _, _).
path_(A,Z,L,P, Depth, Debug) :-
    conectado(A, Y),
    \+ member(Y, L),
    %%%%
    arg(1, Debug, Changes),
    Changes1 = [passo(Depth, A, Y)|Changes],
    nb_setarg(1, Debug, Changes1),
    %%%%
    Depth1 is Depth+1,
    path_(Y, Z, [Y|L], P, Depth1, Debug).

You can run this code on Swish (SWI-Prolog online) in a notebook, using a section of the SP metro as an example!