graph recursion in prolog

Tag: prolog , artificial-intelligence Author: dslin3 Date: 2013-10-22

The graph is shown in the figure below. I have to tell whether there is path between the two nodes and print the path also. For instance: my query is path(a,c). then it will return True. Now when i am giving the query as path(g,f), Ist and 2nd results are True and after that instead of terminating, its starts looping around. I am a novice in prolog. Please suggest some solution for stopping the recursion after getting the correct number of pathsThe graph These are the facts


    path(X,Y):- arc(X,Y).
    path(X,Y):- arc(X,Z),path(Z,Y).
By 'correct number of paths' you mean you want the program to find all the paths (display a number) and then stop?
The query path(X,Y):- arc(X,Z),path(Z,Y). makes your program display a million results. If you want just the paths to be shown, type path(X,Y). But because of the second path query,you'll get millions of results
path(X,Y):- arc(X,Z),path(Z,Y). should be changed into path(X,Y):-path(X,Y). Is it
No. Try path(X,Y):- arc(X,Z),path(Z,Y),!.

Best Answer

You are traversing a directed graph. Assuming that it is acyclic, this should enumerate all the possible paths:

path(X,Y) :- % a path exists from X to Y 
  arc(X,Y)   % IF an edge exists *from* X *to* Y
  .          %
path(X,Y) :- % Otherwise, a path exists from X to Y
  arc(X,Z) , % IF an outbound path from X exists
  Z \== Y ,  % whose destination (Z) is NOT Y, and
  path(X,Y)  % a path exists from Z to Y
  .          % Easy!

We're using \==/2 here because this predicate might be invoked with unbound argument(s).

Another way to write it might be:

path(X,Y) :-  % A path exists from X to Y
  arc(X,Z) ,  % IF an outbound path from X exists,
  (           % AND
    Z = Y     % Y is that destination (Z)
  ;           % OR
    path(Z,Y) % Y can be reached from Z.
  ) .

If your graph is cyclic, you'll need to build and carry along with you as you go a list of visited nodes, so you can skip visiting nodes you've already seen, lest you go down the rabbit hole of infinite recursion.


when i am giving query path(g,f). then its giving out of local stack. for cyclic graph. its not working