Graph cycle detection with Prolog

Question

I am trying to write a prolog program that detects a cycle in an undirected graph. I have already consulted this question: prolog graph depth first search

and have attempted to alter the dfs algorithm presented there, in order to detect cycles. Here is my progress so far:

findCycle(Node, NextNode, Visited) :-
      ( member(NextNode, Visited), isNotParent(Node, NextNode) )
    ->
      writeln("found a cycle"), saveCycle(Node, NextNode), !
    ;
      writeln("end of findCycle").
   
saveCycle(Node, NextNode) :-
    % save to structure
 
dfs(Graph, StartNode) :-
    dfs(Graph, StartNode, []).

dfs(Graph, Node, Visited) :-
    writeln(Visited),
    \+ member(Node, Visited),
    write("visiting node "),
    write(Node), nl,
    member(NextNode, Graph.get(Node)),
    % \+ findCycle(Node, NextNode, Visited),
    dfs(Graph, NextNode, [Node|Visited]).

The graph in my implementation will be represented as a dictionary, where every key is a vertex, and the corresponding value is a list of all its neighboring vertices. Now, I have a few problems:

I need to be storing the "parent" of each vertex in a data structure, so that it can be used for cycle detection. I am not sure about how to do that. So far I have been testing the program with an example graph, whose edges I enter manually with individual terms. That is not, however, my end goal.
I also need to fix the dfs algorithm, because as it is right now, it causes stack overflow, due to the Visited list not storing all the vertices persistently. Ideally, Visited should be a dictionary instead of a list, so it can be accessed more efficiently.
Finally, if a cycle is detected, I would like to save all the vertices participating in it, into another data structure.

Though I know programming, and have written this program in C++ in the past, my grasp of prolog is at best rudimentary, so any help would be appreciated. Thanks!

CapelliC CapelliC · Accepted Answer · 2020-05-30T14:35:11

You're somewhat overengineering...

Just simplify your code to the bare needed, and you'll get what you're after... for instance:

find_cycle(G,Vs) :-
  member(V-_Edges,G), % don't care about starting point
  find_cycle(G,V,[],Vs).

find_cycle(_G,V,SeenVs,[V|SeenVs]) :-
  memberchk(V,SeenVs).
find_cycle(G,V,SeenVs,Cycle) :-
  \+memberchk(V,SeenVs),
  member(V-Es,G),
  member(Ve,Es),
  find_cycle(G,Ve,[V|SeenVs],Cycle).

?- G=[a-[b,c],b-[a,c],c-[]],find_cycle(G,C).
G = [a-[b, c], b-[a, c], c-[]],
C = [a, b, a] ;
G = [a-[b, c], b-[a, c], c-[]],
C = [b, a, b] ;
false.

Or, to avoid the duplicate search in visited edges list:

find_cycle(G,V,SeenVs,Cycle) :-
  (   memberchk(V,SeenVs)
  ->  Cycle=[V|SeenVs]
  ;   member(V-Es,G),
      member(Ve,Es),
      find_cycle(G,Ve,[V|SeenVs],Cycle)
  ).

edit after comment...

For efficiency, note I used memberchk/2 in the test, not member/2. The implementation in SWI-Prolog it's very fast, since uses the low level representation of lists (skip list), done in C. So, you should have very long lists before you start to observe some improvements using some other data structure (there are some... like rbtrees, avltrees, ...). But if your lists are so big, then the whole algorithm should be improved. Again, there are some, you can start looking in library(ugraph).

Graph cycle detection with Prolog

1 Answers