graph-theory - 在数据记录中添加循环边缘 (bddbddb)

Question

我有以下规则来查找图形中的所有路径。

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

但是，我还希望对于每个节点 n，添加边 n->n(如果尚不存在)。

在没有任何节点关系的情况下如何做到这一点？

Answer 1

仅在 Prolog 中，您可以编写:

path(X,X).
path(X,Y) :- false, edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

or somewhat shorter and more terminating using closure0/3.

path(X,Y) :-
   closure0(edge, X,Y).

In (many definitions of) Datalog as a subset of Prolog, facts like path(X,X). are not permitted, since they admit an infinite set of solutions.

So you need to restrict that fact to a finite set of nodes. However, since you do not have an explicit definition of nodes, you need to make up one based on the edges you have:

node(X) :-
   edge(X,_).
node(Y) :_
   edge(_,Y).

现在导致:

path(X,X) :-
   node(X).
path(X,Y) :-
   edge(X,Z),
   path(Z,Y).