prolog - 确定图形是否在序言中连接

Question

我需要创建一个谓词 isConnected/1，它将一个图作为参数并确定在对之间是否存在无向路径。

假设我有一个边列表(其中 G 是一个图):

isEdge(G,1,2).
isEdge(G,2,3).
isEdge(G,4,5).

所以因为 3 和 4 之间没有边，所以这应该失败。
我将如何解决这个问题？我是否必须遍历每条边并将边记录在列表中？还是有更好的方法来做到这一点？

Answer 1

解决方案 1:使用库

一旦您使用图论库，这就很容易了。我将首先使用 S 表示重写您的图表:

[1-[2],2-[1,3],3-[2],4-[5],5-[4]]

然后我将使用 SWI-Prolog ( thanks to Richard O'Keefe and Vitor Santos Costa ) 中包含的库 ugraph:

?- use_module(library(ugraph)).
?- G = [1-[2],2-[1,3],3-[2],4-[5],5-[4]], vertices(G, Vs), member(V, Vs), reachable(V, G, Ws).
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 1,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 2,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 3,
Ws = [1, 2, 3] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 4,
Ws = [4, 5] ;
G = [1-[2], 2-[1, 3], 3-[2], 4-[5], 5-[4]],
Vs = [1, 2, 3, 4, 5],
V = 5,
Ws = [4, 5].

解决方案 2:“自己动手”

除了依赖现有的库，您还可以通过各种方式自己实现它(如果您想成为更好的程序员，强烈推荐!)。从头开始实现此表单的一种方法是使用 closure0/3它在二元谓词(由 SO 用户 false 创建)上实现自反传递闭包。

如果您将适当的边缘添加到您的数据库:

edge(1,2).
edge(2,1).
edge(2,3).
edge(3,2).
edge(4,5).
edge(5,4).

...你现在可以查询:

?- member(V, [1,2,3,4,5]), findall(W, closure0(edge, V, W), Ws).
V = 1,
Ws = [1, 2, 3] ;
V = 2,
Ws = [2, 1, 3] ;
V = 3,
Ws = [3, 2, 1] ;
V = 4,
Ws = [4, 5] ;
V = 5,
Ws = [5, 4].