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).
Will return no and
graph2(a,b).
graph2(b,c).
will return yes
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.
Using 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
succeeds if the following exists:
an acyclic connexion from X0
to X
, thus:
closure0(R_2, X0,X)
or more verbosely:
call(R_2, X0,X1), call(R_2, X1,X2), call(R_2, X2,X3), ..., call(R_2, Xn,X)
with X0,X1,...,Xn
all pairwise different
one edge back
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.