%% this version of DFS keeps track of the path so far as it
%% explores, enabling it to avoid loops.

:- ensure_loaded(showPath).

dfs :-
  dfs(Path),
  showPath(Path).

dfs(Path) :-
  start(S),
  dfs(S,Path).

dfs(S,Path) :- dfs1(S,[S],Path).

dfs1(S,Path,ReversePath) :-
  goal(S),
  reverse(Path,ReversePath).

dfs1(S,SoFar,Path) :-
  arc(S,S2),
  not(member(S2,SoFar)),
  dfs1(S2,[S2|SoFar], Path).