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

Question

我正在尝试编写一个应该适用于循环图的谓词 isway(A, B)。我试图获得的预期结果是，是否在 2 个节点之间存在路径。示例：如果我问 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.

Answer 1

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

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.

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

Write a predicate that works for cyclic graph to check if there exists a path between two nodes using prolog

predicate

prolog

cyclic-graph