0
node(a).
node(b).
node(c).
node(d).
node(e).
node(f).
node(g).
node(h).
edge(a,b).
edge(b,c).
edge(c,a).
edge(c,e).
edge(c,d).
edge(d,e).
edge(d,h).
edge(e,g).
edge(g,e).
edge(e,f).
edge(f,g).
parent(X,Y):-edge(X,Y).
child(X,Y):-parent(Y,X).
path(X,Y):-edge(X,Y).
path(X,Y):-edge(X,Z),path(Z,Y).
path(X,Y,Z):- 
length_of_path(X,Y,1):-edge(X,Y).
length_of_path(X,Y,N):-edge(X,Z),length_of_path(Z,Y,N1),N is N1+1.
connected(X,Y):-path(X,Y); path(Y,X).
undirected_edge(X,Y):-edge(X,Y);edge(Y,X).
undirected_path(X,Y):-path(X,Y);path(Y,X).
tpath(Node1,Node2):-edge(Node1, SomeNode), edge(SomeNode,Node2).

Path(X,Y) needs to find a directed path from node X to node Y. However, in my case there is a problem because there is infinite recursion (nodes e,f,g are a circle).

Path(X,Y,Z) needs to find a directed path from node X to node Y and store in Z.

length_of_path(X,Y,Z), Z is length of path from X to Y.

What makes these 3 questions difficult is that you need to take into account that there are circles in the graph. I'm not sure how to solve this problem.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Laurent Cousineau
  • 41
  • 3

1 Answers1

2

The straight-forward approach is to keep track of the path so far and not go to a node you've already visited. Here is one implementation: Definition of a path/trail/walk

If I take that and add your node/1 and edge/2 definitions, I get:

?- path(edge, Path, e, X).
Path = [e],
X = e ;
Path = [e, g],
X = g ;
Path = [e, f],
X = f ;
Path = [e, f, g],
X = g ;
false.
User9213
  • 1,316
  • 6
  • 12