Cycle detection in a graph

Question

We are given a graph with the following facts:

edge(a,b)
edge(a,c)
edge(b,a)
edge(c,d)
edge(d,d)
edge(d,e)
edge(e,f)
edge(f,g)
edge(g,e)

And we are asked to define a rule, cycle(X), that determines if there is a cycle starting from the node X.

I am really lost on how to do this, I tried attempting to traverse the nodes and checking if the next one would be the starting one again but I cannot seem to get it to work

Stacistacia

Answer 1

Archie's idea is a good starting point, but it will create an infinite loop if it finds another cycle while searching for the path.

I also haven't used prolog for years, but you will need something like path(X,Y,Visited), where you keep track of the visited nodes, preventing the endless loops.

Bequeath

Answer 2

I used Depth First Search with visited node list if we encounter any visited node during traversal it returns true. I tested with small inputs it looks like working correctly.

cycle(X):- cycleh(X,[X]).
cycleh(X,Visited) :- edge(X,Y), (member(Y,Visited) -> !,true; cycleh(Y,[Y|Visited])).

Shawntashawwal

Answer 3

I haven't been using Prolog for some time, but here is my approach to this problem.

You could make rule path(X,Y) that checks if there exists path from node X to Y. A path is a single edge or an edge leading to a path. Having this, it's easy to find cycle starting from node X -- it will be simply path(X,X). Here is my implementation (taken from the top of my head and not necessarily correct, but gives the idea):

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

cycle(X) :- path(X,X).

Pinpoint

Take edge(a,b). edge(b,c). edge(c,b). and the query ?- cycle(X). Depth first Prolog will run into an infinite loop, and not find the cycle. – After

Answer 4

This should do the trick:

cycle( X ) :-
  cycle( X , [] ).

cycle( Curr , Visited ) :-
  member( Curr, Visited ) ,
  !. 
cycle( Curr , Visited ) :-
  edge( Curr , Next ) ,
  cycle( Next , [Curr|Visited] ) .

Although it appears to be a similar solution to @Gökhan Uras -- great minds think alike! Or something B^)

The basic logic is that you have a cycle if the current node has already been visited (the first clause in the cycle/2 helper predicate. At that point, we cut(!) and declare success The reason for the cut (!) is that without it, backtracking would result in revisiting a node already visited and thus an infinite set of cycles.

If the current node has not been visited, we grab an edge anchored at the current node and visit that. Backtracking into the 2nd clause of cycle/2 visits the next edge, so once a particular path is exhausted, cycle/2 backtracks and tries another path.

Carlacarlee

Answer 5

If your Prolog system has a forward chainer, you could use it to determine cycles. But watch out, it might eat quite some memory, since it will generate and keep the path/2 facts.

Here is how you would need to formulate the rules in a forward chainer that does not eliminate automatically duplicates. The \+ is there to explicitly eliminate the duplicates:

:- forward edge/2.
:- forward path/2.

path(X,Y) :- edge(X,Y), \+ path(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y), \+ path(X,Y).
cycle(X) :- path(X,X).

To make the example a little bit more interesting what concerns the result, I have dropped the edge(d,d). Here is a sample run:

?- postulate(edge(a,b)), postulate(edge(a,c)), postulate(edge(b,a)),    
postulate(edge(c,d)), postulate(edge(d,e)), postulate(edge(e,f)), 
postulate(edge(f,g)), postulate(edge(g,e)), cycle(X).
X = a ;
X = b ;
X = e ;
X = f ;
X = g

The postulate/1 predicate here posts an event and keeps the propagator of the forward chainer running. How to write your forward rules depends on the Prolog systems respective library you are using.

P.S.: There is still some research going on:
http://x10.sourceforge.net/documentation/papers/X10Workshop2011/elton_slides.pdf

After

Answer 6

It's been a while since I used Prolog, but perhaps this approach will work: A path is a sequence of edges where each edge starts on the node the previous edge ended on (e.g. a -> b, b -> c, c -> d). The trivial path is a single edge, and more complex paths can be formed by taking an existing path and adding an edge to it. A cycle is a path that starts and ends on the same node. Can you use these definitions to build your Prolog rules?

Crosscut