i have been writing code so that im able to search if there is a path in a graph and if there is one i would want to print out the path, if there is one i would like to print out all of them. i have a condition that writes the path if the predicate is true but it never prints, how should i go about this?
%graph
edge(a,b).
edge(a,c).
edge(b,c).
edge(c,d).
edge(c,e).
edge(d,e).
edge(f,g).
edge(g,h).
% condition
allways(X,Y) :-
edge(X,Y).
% recursion
allways(X,Y) :-
edge(X,B),
allways(B,Y).
%print out path if there is one (its meant to print out all paths it can find)
allways(P,Y) == true -> writepath(X,Y).
writepath(X,Y):-
edge(X,Y).
writepath(X,Y) :-
edge(X,B),
write(B),
writepath(B,Y).
Have you considered adding a list as third argument to collect the nodes along the path? Instead of using write/1 to output every node, you'd have a list with all nodes from start to destination for every solution. Consider the following change to your code:
allways(X,Y,[X,Y]) :-
edge(X,Y).
allways(X,Y,[X|Nodes]) :-
edge(X,B),
allways(B,Y,Nodes).
If there is an edge between X and Y it's the end of the path and both nodes are in the list. Otherwise there has to be an intermediary node B and only X is in the list. This predicate yields the desired result:
?- allways(a,e,P).
P = [a, b, c, e] ;
P = [a, b, c, d, e] ;
P = [a, c, e] ;
P = [a, c, d, e] ;
false.
Now you get a list of nodes for every path from start to destination. However, this query only terminates because the graph you provided is acyclic. Consider adding an edge such that the graph contains a cycle:
edge(a,b).
edge(a,c).
edge(b,c).
edge(c,e).
edge(c,d).
edge(d,e).
edge(f,g).
edge(g,h).
edge(c,a). % <- new edge
Now the above query loops because of the newly added cycle:
?- allways(a,e,P).
P = [a, b, c, e] ;
P = [a, b, c, d, e] ;
P = [a, b, c, a, b, c, e] ;
P = [a, b, c, a, b, c, d, e] ;
P = [a, b, c, a, b, c, a, b, c, e] ;
P = [a, b, c, a, b, c, a, b, c, d, e] ;
P = [a, b, c, a, b, c, a, b, c, a, b, c, e] ;
.
.
.
If you do not want this behaviour, you can add a list of visited nodes as an additional argument. I would also suggest a more descriptive name, say start_dest_path/3 for the calling predicate and start_dest_path_visited/4 for the actual relation:
:- use_module(library(apply)).
start_dest_path(S,D,P) :-
start_dest_path_visited(S,D,P,[]).
start_dest_path_visited(S,D,[S,D],Vs) :-
maplist(dif(S),Vs),
edge(S,D).
start_dest_path_visited(S,D,[S|Nodes],Vs) :-
maplist(dif(S),Vs),
edge(S,X),
start_dest_path_visited(X,D,Nodes,[S|Vs]).
The predicate start_dest_path/3 is calling start_dest_path_visited/4 with an empty accumulator. The goal maplist(dif(S),Vs) in start_dest_path_visited/4 makes sure the node S has not already been visited. Now the query terminates with the cycle as well:
?- start_dest_path(a,e,P).
P = [a, b, c, e] ;
P = [a, b, c, d, e] ;
P = [a, c, e] ;
P = [a, c, d, e] ;
false.
Although the path cannot contain cycles this definition allows the path to be one big cycle. Consider the following query:
?- start_dest_path(a,a,P).
P = [a, b, c, a] ;
P = [a, c, a] ;
false.
If you want to exclude such solutions, add a goal maplist(dif(D),Vs) to the non-recursive rule of start_dest_path_visited/4.
Note how the predicate start_dest_path_visited/4 still resembles the structure of allways/2 from your original post with two additional arguments (path and list of visited nodes) and an additional goal (maplist/2). You can see a slightly different definition for weighted paths in this and in this answer. You might also be interested in a more generic definition as suggested in this question and the corresponding answers.
