2

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.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Sam
  • 53
  • 3
  • Welcome to Stack Overflow! Please read http://stackoverflow.com/tour to understand how this site works ; if an answer is OK to you, accept it by clicking on the checkmark! – false Nov 16 '14 at 21:52
  • Please do read the tour! Otherwise Stack Overflow will not be very helpful to you. – false Nov 16 '14 at 22:36

2 Answers2

2

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:

  1. 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

  2. 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.

false
  • 10,264
  • 13
  • 101
  • 209
0

Your recursive predicate isConnected/2 misses the base case:

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

(assuming we are checking graph1, of course).

Anyway, you cannot use isConnected/2, since Prolog will loop on cyclic graphs.

CapelliC
  • 59,646
  • 5
  • 47
  • 90