путь графа в прологе

Question

Я создал правила для получения пути графа с ребрами, определенными следующим образом:

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

, но теперь мне нужно сделать это, когда факты, например:

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

У меня было это:

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]).

и я знаю, что проблема в графике (Origin, Inter), но я не знаю, как настроить его, чтобы он мог войти в списокЯ пытался graph(Origin, [Inter|_]), но, очевидно, он просто проверяет первый.Любая помощь (даже если это не код) будет принята с благодарностью.

Answer 1

Предположим, ориентированные графы:

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

Answer 2

Вот мое решение, которое работает на ориентированных или ненаправленных графах с циклами или без них.

Используя предложение @larsmans, вы можете выполнить эту работу с помощью списка смежности, такого как ввод.

Он также пытается найти все пути без повторного посещения.

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).

Answer 3

Мне удалось решить эту проблему, если у кого-то есть такая же проблема:

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).