Depth-first visit of a graph

Help!
1

Hello,
I’m using: SWI-Prolog version9.0.4 for x86_64-linux

For a university assignment I have to write the following prolog program:

dfv(R,N): performs the DFS of a graph (which may contain cycles). Precisely, if the graph has n nodes and the visit starts from node a, the first n solutions of the query dfv(a,N) must return each N node to be visited in the correct order. To represent the graph, use the predicate arc(a,b), which is true if there is an arc between node a and node b.

For now my attempts have been completely in vain, could someone help me? Thanks in advance.

2

Where are you stuck? Is it the depth-first part or the dealing with cycles part? If you can write a predicate for depth-first traversal without worrying about cycles, it’s relatively straightforward to modify the code to deal with cycles.

If you’re having trouble writing the code in Prolog, try writing it in your favourite programming language without any destructive assignments (that is, in a pure functional style). [If your favourite programming language is C, I suggest you choose a higher level one instead, such as Python, Racket, or Haskell.]

3

Anyway, for the next person who has this problem assigned to them, I thought I’d post the answer. I’m sure their instructor will give them 100% for it.

dfs(F, T) :- phrase(dfs(F), T).

dfs(F) --> {F=..[X] }, [X].
dfs(F) --> {F=..[Op,X,Y]}, dfs(X), dfs(Y), [Op].
2 Likes
4

Your problem is solved in this SO question. The look for the “Implementation” section at the bottom. With this, your dfv(R,N), given that you have defined your arcs, would be defined as:

dfv(R, N) :- path(arc, _, R, N).