graph path in prolog

Question

I've made the rules to obtain a path of a graph with the edges defined as follows:

graph(a,b).
graph(a,a).
graph(b,c).

but now I need to do it when the facts being, for example:

graph(a,[a,b,e]).
graph(b,[c,d]).
graph(d,[]).

I had this:

path(Origin, Dest, List) :- path(Origin, Dest, List, [Origin]).
path(X, X, List, Temp) :- reverse(Temp, List).
path(Origin, Dest, List, Temp) :- graph(Origin, Inter),
                                 not(member(Inter, Temp)),
                                 path(Inter, Dest, List, [Inter|Temp]).

and I know that problem is in graph(Origin, Inter), but I don't know how to tweak it so it can go inside the list, I've tried graph(Origin, [Inter|_]) but obviously it just checks the first one. Any help (even if it's not code) would be greatly appreciated.

Answer 1

Assuming directed graphs:

edge(X,Y) :- graph(X,Nodes), member(Y,Nodes).

Answer 2

I managed to solve it, in case someone else has the same problem:

node(X) :- graph(X,_).
allnodes(Nodes) :- setof(X, node(X), Nodes).

path(Origin,Dest,List) :- allnodes(X),
                          path(Origin, Dest, List1, X, X),
                          reverse(List1,List),!.
path(X,X,[X],_,_).
path(Origin,Dest,[Dest|List],[X|_],AN) :- graph(X, Inter),
                                 member(Dest, Inter),
                                 path(Origin,X,List,AN,AN).
path(Origin,Dest,List,[X|Y],AN) :- graph(X, Inter),
                                 \+ member(Dest, Inter),
                                 path(Origin,Dest,List,Y,AN).

Answer 3

Here's my solution that works on directed or undirected graphs, with or without cycles.

Using @larsmans suggestion you can make this work with adjacency-list like input.

edge(X,Y) :- graph(X,Nodes), member(Y,Nodes).

It also tries to find all paths, without revisiting.

c(1,2).
% ... c(X,Y) means X and Y are connected

d(X,Y):- c(X,Y).
d(X,Y):- c(Y,X).
% Use d instead of c to allow undirected graphs

findPathHelper(_, Begin, [], End):- d(Begin, End).
findPathHelper(Front, Begin, [Next|NMiddle], End):-
    not(member(Begin,Front)),
    d(Begin, Next),
    append([Front,[Begin]], NFront),
    findPathHelper(NFront, Next, NMiddle, End).

findPath(Start, End, Path):-
    findPathHelper([], Start, Middle, End),
    append([[Start],Middle,[End]], Path).