Clever Geek Handbook

Prolog, Determine If a Graph is Acyclic

I need to define an acyclic / 1 predicate that takes a graph as input and determines if that graph is acyclic. Therefore 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 two nodes in the graph are connected, and if so, they will return yes.

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

is there a way i can use this to determine if a graph is acyclic?

I don't want to use predefined predicates.

+2


source to share


2 answers


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:



  • acyclic link from X0

    to X

    , thus:

    closure0(R_2, X0,X)

    or in more detail:

    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 this is a loop. In other words, a cyclic graph is a graph that contains at least one cycle. And this cycle consists of an acyclic part plus one edge back. And only this edge back makes it a cycle.

+2


source


The recursive predicate isConnected / 2 skips the base case:

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


(assuming we're checking graph1 of course).

In any case, you cannot use isConnected / 2, as Prolog will loop over and over.

0


source






More articles:


All Articles