title: Prolog graph find path without loops, checking edges
body: <p>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).</p>
  
  <p>Here is my current code:</p>
  
  <pre><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).
  </code></pre>
  
  <p>For the above example this returns for example:</p>
  
  <pre><code>path(a,b,[a,b],[ac])
  path(a,b,[a,c,b],[ac,ac])
  </code></pre>
  
  <p>Now I thought I could simply replace the <code>\+ memberchk(X,[Y|P1])</code> with <code>\+ memberchk(Edge,S)</code> 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.</p>
  
  <p>Can someone explain to me where this is going wrong?</p>