Print all cycles of the graph for the specified node of the graph, Prolog

Question

I'm newbie in the Prolog world. I'm trying to write predicate for printing all cycles of the graph for the specified node of the graph, which is the element of the given node. My graph looks like this.

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

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

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

Unfortunately now I cannot find cycle for specific node. For example I'm looking for all cycles for node d.

Answer 1

What you are looking for sounds like transitive-closure to me... no need to reinvent the wheel!

Simply build upon tried-and-tested code shown in "Definition of a path/trail/walk" and define:

in_cycle(R_2, AZ, Path) :-                  % cf. "simple cycle"
   First = AZ,
   Last  = AZ,
   path(R_2, Path, First, ButLast),         % all "hops" but the last one ...
   call(R_2, ButLast, Last).                % ... and here comes the last one

Sample query #1 using SICStus Prolog 4.3.2:

| ?- in_cycle(edge, d, Path).
Path = [d,c,b,a,e] ? ;
Path = [d,a,e] ? ;
no

In sample query #2, we look at the transitive closure of the symmetric closure of edge/2:

| ?- in_cycle(symm(edge), d, Path).
Path = [d,c] ? ;
Path = [d,c,b,a] ? ;
Path = [d,c,b,a,e] ? ;
Path = [d,c,e] ? ;
Path = [d,c,e,a] ? ;
Path = [d,a] ? ;
Path = [d,a,e] ? ;
Path = [d,a,e,c] ? ;
Path = [d,a,b,c] ? ;
Path = [d,a,b,c,e] ? ;
Path = [d,e] ? ;
Path = [d,e,c] ? ;
Path = [d,e,c,b,a] ? ;
Path = [d,e,a] ? ;
Path = [d,e,a,b,c] ? ;
no

All solutions of query #1 also fulfill the more general query #2—monotonic Prolog^1,2,3 at work:)

Answer 2

I think the problem is that you simply do not have any logic written to return the cycle.

Cycles that originate from a node

This is not that hard, you already use an accumulator, you simply need a mechanism that once the cycle is found, return your accumulator as cycle. You can do this by providing an additional parameter to cycle:

cycle(Node,Cycle) :-
    cycle(Node,[],Cycle).

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

In this implementation I used reverse/2 since this will give you the correct order of the nodes (edge-wise). If you are not interested in this (for instance you only wish to analyze the cycle, and you can analyze this the opposite way, you can simply substitute Cycle in the first clause of cycle/3 with [Curr|Visited].

The problem is however that if you call this predicate, it returns:

?- cycle(d,Cycle).
Cycle = [d, c, b, a, e, d] ;
Cycle = [d, c, b, a, e, c] ;
Cycle = [d, a, e, d] ;
Cycle = [d, a, e, c, b, a].

It thus not searches for cycles where d is part of the cycle per se, it searches for all cycles that can originate from d. This is probably not what you want.

Cycles with a given node

You can however rewrite the predicate: you will need to store the node from which you originate:

cycle(Node,Cycle) :-
    edge(Node,Next),
    cycle(Node,Next,[Node],Cycle).

So here we look for every edge/2 originating from Node and we call cycle/4 with the initial Node (to check when we have found a cycle), the Next node, the list of visited [Node]s and the Cycle parameter to return found cycles.

Now there are three possible options for cycle/4:

• We arrive at the original node, in that case we have found a cycle where Node is part from, we do processing similar to the first version:

  cycle(Curr,Curr,Visited,Cycle) :-
      !,
      reverse([Curr|Visited],Cycle).
  

• We arrive in a node we already visited: Curr is an element of Visited, in that case we need to break off search: otherwise we will cycle for an infinite amount of times:

  cycle(_,Curr,Visited,_) :-
      member(Curr,Visited),
      !,
      fail.
  

  fail is a predicate that states the branch fails. This can be useful, because now we specify how it can fail.

• Finally we simply visited another edge and try to find the next node:

  cycle(Node,Curr,Visited,Cycle) :-
      edge(Curr,Next),
      cycle(Node,Next,[Curr|Visited],Cycle).
  

The full version is:

cycle(Node,Cycle) :-
    edge(Node,Next),
    cycle(Node,Next,[Node],Cycle).

cycle(Curr,Curr,Visited,Cycle) :-
    !,
    reverse([Curr|Visited],Cycle).
cycle(_,Curr,Visited,_) :-
    member(Curr,Visited),
    !,
    fail.
cycle(Node,Curr,Visited,Cycle) :-
    edge(Curr,Next),
    cycle(Node,Next,[Curr|Visited],Cycle).

Which generates:

?- cycle(d,Cycle).
Cycle = [d, c, b, a, e, d] ;
Cycle = [d, a, e, d] ;

All are thus cycles starting from d and visiting d again. We can make the code a bit more efficient by compressing the second and third scenario in one clause:

cycle(Node,Cycle) :-
    edge(Node,Next),
    cycle(Node,Next,[Node],Cycle).

cycle(Curr,Curr,Visited,Cycle) :-
    !,
    reverse([Curr|Visited],Cycle).
cycle(Node,Curr,Visited,Cycle) :-
    \+ member(Curr,Visited),
    edge(Curr,Next),
    cycle(Node,Next,[Curr|Visited],Cycle).

Where \+ means not.