Depth First Search Algorithm Prolog

Question

I am hoping you could help me with this.

I am trying to learn about Depth First search algorithm in Prolog and I have come across the following code

go(Start, Goal) :-
   empty_stack(Empty_been_list),
   stack(Start, Empty_been_list, Been_list),
   path(Start, Goal, Been_list).

% path implements a depth first search in PROLOG

% Current state = goal, print out been list
path(Goal, Goal, Been_list) :-
    reverse_print_stack(Been_list).

path(State, Goal, Been_list) :-
    mov(State, Next),
    % not(unsafe(Next)),
    not(member_stack(Next, Been_list)),
    stack(Next, Been_list, New_been_list),
    path(Next, Goal, New_been_list), !.

reverse_print_stack(S) :-
    empty_stack(S).
reverse_print_stack(S) :-
    stack(E, Rest, S),
    reverse_print_stack(Rest),
    write(E), nl.

I kind of understand what is going on, but I cant for the life of me find or invent some facts that I can use with it.

Please help. Even if its a really simple set of facts, I just need somewhere to start

Thank you in advance

Answer 1

You just need to make facts that describe the valid moves in a graph.

So for instance, if you have nodes A, B, C, and D, every edge on the graph would have a mov() fact. If A had edges to B and C, and B had an edge to D, your facts would be

mov(A, B).
mov(A, C).
mov(B, D).

Basically, draw a graph and write a fact like the above for every path from a node to another node.

Answer 2

The Following is an example of DFS used in prolog code

% solve( Node, Solution):
%    Solution is an acyclic path (in reverse order) between Node and a goal

solve( Node, Solution)  :-
  depthfirst( [], Node, Solution).

% depthfirst( Path, Node, Solution):
%   extending the path [Node | Path] to a goal gives Solution

depthfirst( Path, Node, [Node | Path] )  :-
   goal( Node).

depthfirst( Path, Node, Sol)  :-
  s( Node, Node1),
  \+ member( Node1, Path),                % Prevent a cycle
  depthfirst( [Node | Path], Node1, Sol).

depthfirst2( Node, [Node], _)  :-
   goal( Node).

depthfirst2( Node, [Node | Sol], Maxdepth)  :-
   Maxdepth > 0,
   s( Node, Node1),
   Max1 is Maxdepth - 1,
   depthfirst2( Node1, Sol, Max1).


goal(f).
goal(j).
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).

In order to test this code head over to Swish SWI prolog and paste this into terminal.

Then query the code and type on right hand side: solve(a, Sol)

The solution will be: Sol = [j, e, b, a]

You can debug this code by typing: trace, (solve(a, Sol)).

The Following is an example of BFS used in prolog code

Head over to swish and query it using the same steps as before

The solution will be: Sol = [f, c, a]

% solve( Start, Solution):
%    Solution is a path (in reverse order) from Start to a goal

solve( Start, Solution)  :-
  breadthfirst( [ [Start] ], Solution).

% breadthfirst( [ Path1, Path2, ...], Solution):
%   Solution is an extension to a goal of one of paths

breadthfirst( [ [Node | Path] | _], [Node | Path])  :-
  goal( Node).

breadthfirst( [Path | Paths], Solution)  :-
  extend( Path, NewPaths),
  append( Paths, NewPaths, Paths1),
  breadthfirst( Paths1, Solution).

extend( [Node | Path], NewPaths)  :-
  bagof( [NewNode, Node | Path],
         ( s( Node, NewNode), \+ member( NewNode, [Node | Path] ) ),
         NewPaths),
  !.

extend( Path, [] ).              % bagof failed: Node has no successor
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(c,f).
s(c,g).
s(d,h).
s(e,i).
s(e,j).
goal(j).
goal(f).

Hope this helps for understanding DFS and BFS

Use this diagram to help you understand the tree