Search code examples
prologdirected-acyclic-graphs

Finding the path length of an Acyclic Graph in Prolog

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.

Solution

  • 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 ?