% Name:   Anderson Silva
% Date:   March 10, 1999
% ================================
% This is the Depth First Algorithm
% implemented in Prolog that will
% use the graph.pl knowledge base
% ================================

% reverse_write/1
% Inverts the order of the stack.

reverse_write([]).
reverse_write([H|T]):-reverse_write(T), write(H), nl.

% solve/2
% Gives the path in the reverse
% order since dfs is implemented as
% a stack

solve(INode, Solution):- consult('graph.pl'),
                         query_goal,
                         dfs([], INode, Solution),
                         reverse_write(Solution).

% query_goal/0
% Creates the goal to be reached
% during execution
% We start with abolish, so if solve is ran more
% than once, it will make sure it
% forgets the old goals and only look for the
% new on.

query_goal :- abolish(goal(Node)),
              write('Goal? [Followed by a period]'),
              nl,
              read(Node),
              assert(goal(Node)).


% goal/1
% When the program runs for the frist time
% query_goal needs to abolish at least one goal
% and that is why goal(standard) is used.

goal(standard).

% dfs/3
% The Actual recursive algorithm for the
% Depth First Search

dfs(Path, Node, [Node|Path]):- goal(Node).
dfs(Path, Node, Sol):- arc(Node, Node1),
                       \+ member(Node1, Path),
                       dfs([Node|Path], Node1, Sol).