Prolog graph find path without loops, checking edges

Question

I am trying to find a path in a graph in Prolog. I managed to get this working with some snippet I found online. However, it keeps track of nodes to avoid visiting them twice, while I need it to not visit the same edge twice. This probably comes down to the same thing in most graphs, but because I want to use it to calculate paths from points on edges to other points on edges, I don't want it to return a path from a point to an adjacent node to the opposite node (say, if we had an edge AC from node A to node C, with a point B in the middle, A-C-B would not be an acceptable path because it traveled AC twice).

Here is my current code:

path(A,B,Nodes,Edges) :- path1(A,[B],Nodes,Edges).
path1(A,[A|P1],[A|P1],[]).
path1(A,[Y|P1],Nodes,Edges) :- 
   connected(X,Y,Edge), \+ memberchk(X,[Y|P1]), path1(A,[X,Y|P1],N1,E1), append(E1,[Edge],Edges).

connected(a,c,ac). % connected(Node1,Node2,Edge) need not represent an edge:
connected(a,b,ac). % it may also refer to a point on the edge.
connected(b,c,ac).

For the above example this returns for example:

path(a,b,[a,b],[ac])
path(a,b,[a,c,b],[ac,ac])

Now I thought I could simply replace the \+ memberchk(X,[Y|P1]) with \+ memberchk(Edge,S) to make sure the same edge doesn't end up in the path twice, which would solve the problem. However, when I do so, Prolog says that there is no path.

Can someone explain to me where this is going wrong?

roelandvanbeek roelandvanbeek · Accepted Answer · 2012-10-04T18:32:18

This answer helped me out a great deal: apparently it is because you can't use the path that hasn't yet been instantiated to check for loops. It suggests using freeze\2, but I don't know how to handle that in JIProlog. I'll open a new question for that.

Prolog graph find path without loops, checking edges

1 Answers