Пролог, определите, является ли граф ациклическим

Question

Мне нужно определить предикат acyclic/1, который принимает граф в качестве входных данных и определить, является ли этот граф ациклическим. Так что из моего понимания

graph1(a,b).
graph1(b,c). 
graph1(c,a). 

Вернется нет и

graph2(a,b).
graph2(b,c). 

вернется да

Я сделал предикат, чтобы определить, связаны ли 2 узла в графе, и если да, то они вернут да.

isConnected(X,Y) :- a(X,Z), isConnected(Z,Y).

Есть ли способ, которым я могу использовать это, чтобы определить, является ли граф ациклическим?

Я не хочу использовать какие-либо предопределенные предикаты.

Answer 1

С помощью 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 успешно, если существует следующее:

1. ациклическая связь от X0 в X, таким образом:

   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 все попарно разные

2. один край назад

   call(R_2, X,X0).

так что это цикл. Другими словами, циклический граф - это граф, который содержит хотя бы один цикл. И этот цикл состоит из ациклической части плюс один край назад. И только этот край назад делает это циклом.

Answer 2

Ваш рекурсивный предикат isConnected/2 пропускает базовый вариант:

isConnected(X,Y) :- graph1(X,Y).

(конечно, при условии, что мы проверяем graph1).

В любом случае, вы не можете использовать isConnected/2, так как Prolog будет циклически повторяться на циклических графах.