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

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


    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.

comments:

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