Prolog,确定图是否为非循环 [英] Prolog, Determine if graph is acyclic
问题描述
我需要定义一个谓词acyclic/1,该谓词将一个图作为输入并确定该图是否是非循环的.因此,根据我的理解
I need to define a predicate acyclic/1 that takes a graph in as input and determine if that graph is acyclic. So from my understanding
graph1(a,b).
graph1(b,c).
graph1(c,a).
将返回否,并且
graph2(a,b).
graph2(b,c).
将返回是
我做了一个谓词,以确定图中是否有2个节点连接在一起,如果连接,它们将返回是.
I made a predicate to determine if 2 nodes in a graph are connected and if so they will return yes.
isConnected(X,Y) :- a(X,Z), isConnected(Z,Y).
有没有一种方法可以用来确定图是否是非循环的?
is there a way that I can use this to determine if a graph is acyclic?
我不想使用任何预定义的谓词.
I do not want to use any predefined predicates.
推荐答案
使用 closure0/3
:
:- meta_predicate acyclic(2).
:- meta_predicate cyclic(2).
acyclic(R_2) :-
\+cyclic(R_2).
cyclic(R_2) :-
closure0(R_2, X0,X),
call(R_2, X,X0).
?- acyclic(graph2).
true.
?- acyclic(graph1).
false.
如果存在以下情况,则
cyclic/1
成功:
cyclic/1
succeeds if the following exists:
-
从
X0
到X
的无环连接,因此:
an acyclic connexion from
X0
toX
, thus:
closure0(R_2, X0,X)
或更详细:
call(R_2, X0,X1), call(R_2, X1,X2), call(R_2, X2,X3), ..., call(R_2, Xn,X)
与X0,X1,...,Xn
都成对出现
一个边缘向后
call(R_2, X,X0).
所以这是一个循环.换句话说,循环图是包含至少一个循环的图.该循环由一个非循环部分和一个边缘向后组成.只是这条边缘向后才使它成为一个循环.
so that is a cycle. In other words, a cyclic graph is a graph that contains at least one cycle. And that cycle consists of an acyclic part plus one edge back. And it is only this edge back that makes this a cycle.
这篇关于Prolog,确定图是否为非循环的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!