prolog - 编写一个适用于循环图的谓词，以使用 prolog 检查两个节点之间是否存在路径

Question

我正在尝试编写一个适用于循环图的谓词 isway(A, B)。我试图得到的预期结果是，两个节点之间是否存在路径。例如：如果我问 isway(a, f)，期望它回答是或否。下面是我的代码，但它永远不会起作用，并且总是给我 false 作为输出。

%given facts

edge(a,b).
edge(a,c).
edge(b,c).
edge(c,d).
edge(c,e).
edge(d,e).
edge(f,g).
edge(g,h).

edge2(d,a).
edge2(h,f).
edge2(X,Y) :- edge(X,Y).

%my implementation
isway(A,B) :- edge2(A,B,[]).

edge2(A,B,V) :- edge(A,X), not(member(X,V)), (B = X ; edge2(X,B,[A|V])).

%my output
?- isway(b,a). %I expect true for this one
false

?- isway(a,f). %False for this is ok but I am not confident about my logic
false.

标签： prologpredicatecyclic-graph

Answer 1

您可以使用制表来计算边关系的传递闭包：

edge(a,b).
edge(a,c).
edge(b,c).
edge(c,d).
edge(c,e).
edge(d,e).
edge(f,g).
edge(g,h).

edge(d,a). % acyclic
edge(h,f). % acyclic

:- table path/2.
path(X, Y) :- edge(X, Y).
path(X, Y) :- path(X, Z), path(Z, Y).

然后，查询按您的预期工作：

?- path(a, f).
false.

?- path(b, a).
true.