3

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

假设我有一个边列表（G图在哪里）：

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

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

4

2 回答 2

2

解决方案 1：使用库

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

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

然后我将使用ugraphSWI-Prolog 中包含的库（感谢 Richard O'Keefe 和 Vitor Santos Costa）：

?- 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].
于 2014-11-17T05:00:52.297 回答
2

假设这是对这个问题的跟进：

首先，您需要定义连接的含义：

connected_to(R_2, A,B) :-
   (  call(R_2, A,B)
   ;  call(R_2, B,A)
   ).

然后您需要确定节点集。通常给出节点集，但似乎您希望通过所有边缘隐式定义它们：

rel_nodes(R_2, Nodes) :-
   setof(Node, Next^connected_to(R_2, Node,Next), Nodes).

现在被连接意味着每个节点都连接到所有其他节点。

is_connected(R_2) :-
   rel_nodes(R_2, Vs),
   maplist({R_2,Vs}+\V0^setof(V, closure0(connected_to(R_2), V0,V), Vs), Vs).

（所有这些都假设节点实际上是地面项。）

以下是所有缺失的元谓词声明：

:- meta_predicate connected_to(2,?,?), rel_nodes(2,?), is_connected(2).
于 2014-11-17T08:24:54.780 回答