0

Okay, so I have the graph: enter image description here

and I want to be able to create a rule to find all the paths from X to Y and their lengths (number of edges). For example, another path from a to e exists via d, f, and g. Its length is 4.

So far my code looks like this:

edge(a,b).
edge(b,e).
edge(a,c).
edge(c,d).
edge(e,d).
edge(d,f).
edge(d,g).

path(X, Y):- 
    edge(X, Y).

path(X, Y):-
    edge(X, Z), 
    path(Z, Y).

I am a bit unsure how I should approach this. I've entered a lot of rules in that don't work and I am now confused. So, I thought I would bring it back to the basics and see what you guys could come up with. I would like to know why you done what you done also if that's possible. Thank you in advance.

Dylan
  • 53
  • 7
  • Does this answer your question? [Definition of a path/trail/walk](https://stackoverflow.com/questions/30328433/definition-of-a-path-trail-walk) – DuDa Nov 12 '20 at 20:42

1 Answers1

2

This situation has been asked several times already. Firstly, your edge/2 predicates are incomplete, missing edges like edge(c,d), edge(f,g), or edge(g,e). Secondly, you need to store the list of already visited nodes to avoid creating loops. Then, when visiting a new node, you must check that this new node is not yet visited, in the Path variable. However, Path is not yet instanciated. So you need a delayed predicate to check looping (all_dif/1). Here is a simplified version using the lazy implementation by https://stackoverflow.com/users/4609915/repeat.

go(X, Y) :-
    path(X, Y, Path),
    length(Path, N),
    write(Path), write(' '), write(N), nl.
    
path(X, Y, [X, Y]):- 
    edge(X, Y).
path(X, Y, [X | Path]):-
    all_dif(Path),
    edge(X, Z), 
    path(Z, Y, Path).

%https://stackoverflow.com/questions/30328433/definition-of-a-path-trail-walk
%which uses a dynamic predicate for defining path
%Here is the lazy implementation of loop-checking
all_dif(Xs) :-                          % enforce pairwise term inequality
   freeze(Xs, all_dif_aux(Xs,[])).      % (may be delayed)

    all_dif_aux([], _).
    all_dif_aux([E|Es], Vs) :-               
       maplist(dif(E), Vs),                 % is never delayed
       freeze(Es, all_dif_aux(Es,[E|Vs])).  % (may be delayed)

Here are some executions with comments

?- go(a,e).
[a,b,e] 3 %%% three nodes: length=2
true ;
[a,c,d,f,g,e] 6
true ;
[a,c,f,g,e] 5
true ;
[a,d,f,g,e] 5
true ;
false. %%% no more solutions

Is this a reply to your question ?

peter.cyc
  • 1,763
  • 1
  • 12
  • 19
  • If you know this is a duplicate question than mark it as such. – Guy Coder Nov 12 '20 at 20:02
  • Thanks for the reply, you answered what I needed and more, so appreciate that. Also, I didn't realise it was a duplicate question. – Dylan Nov 12 '20 at 20:23
  • The question mentions and shows an acyclic graph, so the loop avoidance isn't necessary in such a case. – jnmonette Nov 12 '20 at 21:17
  • Yes according to the illustration, but the edge/2 includes the arc e-d, which loops. That's why loop avoidance is necessary. – peter.cyc Nov 12 '20 at 22:02