Reversing Prolog List-CodePudding

I've written code in prolog which will return a list using the depth-first search method.

arc(a, b).
arc(a, f).
arc(b, c).
arc(b, d).
arc(b, e).
arc(f, g).
arc(f, i).
arc(i, j).
arc(i, k).

goal(i).

solve2(Node, Solution) :- depthfirst2([], Node, Solution).

depthfirst2(Path, Node, [Node|Path]) :- goal(Node).

depthfirst2(Path, Node, Sol) :- s(Node, Node1),             
                            not(member(Node1, Path)),       
                            depthfirst2([Node|Path], Node1, Sol).

When i call solve2([a], X). it will output X = [i, f, a]. How can I change that to produce
X = [a, f, i]. I've tried implementing the Reverse function but I don't know where to put it as I am calling recursively. (I have tried putting it in the base case).

CodePudding user response：

Assuming s/2 is defined by:

s(A, B):- arc(A, B).
s(A, B):- arc(B, A).

you can reverse the list after obtaining your path:

solve2(Node, Solution):- 
  depthfirst2([], Node, SolutionR), 
  reverse(SolutionR, Solution).

Test run:

?- solve2(a, X).
X = [a, f, i] ;
false.

You may also build the list in order by traversing the list where you will keep the solution, unifying step by step with each visited node:

solve2(Node, [Node|Solution]) :-
    depthfirst2([], Solution, Node).

depthfirst2(_, [], Node) :-
    goal(Node).
depthfirst2(Path, [Node1|Solution], Node) :-
    s(Node, Node1),
    not(member(Node1, Path)),
    depthfirst2([Node|Path], Solution, Node1).

CodePudding user response：

Put the reverse/2 as part of the public (wrapper) predicate.

This is how I would do it:

arc( a , b ).
arc( a , f ).
arc( b , c ).
arc( b , d ).
arc( b , e ).
arc( f , g ).
arc( f , i ).
arc( i , j ).
arc( i , k ).

% --- traverse/3 -----------------------
% 
% Traverses a directed graph
%
% traverse( Origin, Destination, Path ).
%---------------------------------------
traverse(A,Z,P) :-
    traverse(A,Z,[],Vs),
    reverse(Vs,P).

% --- traverse/4 --------------------------------------------
%
% private helper for traverse/3
%
% traverse( Origin, Destination, Visited, Path).
%
% Note that  Path is returned in most recently visited order.
%
%------------------------------------------------------------
traverse(A,Z,Vs,[Z,A|Vs]) :-  % we can get from A to Z
    arc(A,Z).                 % - if A and Z are directly connected
traverse(A,Z,Vs,P) :-         % otherwise, we can get from A to Z, if...
    arc(A,B),                 % - A is connected to some B
    \  member(B,Vs),          % - that we have not yet visited
    traverse(B,Z,[A|Vs],P).   % - and we can get from B to Z (recording that A has been visited).

And if you run this (See the Swish at https://swish.swi-prolog.org/p/MhhEiKal.pl) by invoking:

traverse(a,i,P).

You get

P = [a,f,i]