Example of execution of graph search algorithm

Below is a trace of the execution of the query

?- path(1, 6, [1], Path).

using the Prolog code for path given in lectures, and the edges given in lectures, that is:

path(Node, Node, _, [Node]).                      % rule 1
path(Start, Finish, Visited, [Start | Path]) :-   % rule 2
     edge(Start, X),
     not(member(X, Visited)),
     path(X, Finish, [X | Visited], Path).

edge(1, 5).     edge(1, 7).
edge(2, 1).     edge(2, 7).
edge(3, 1).     edge(3, 6).
edge(4, 3).     edge(4, 5).
edge(5, 8).
edge(6, 4).     edge(6, 5).
edge(7, 5).
edge(8, 6).     edge(8, 7).

The trace was produced using the SWI Prolog trace facility. Comments on what is happening are shown at right.

?- trace.

?- path(1, 6, [1], Path).

  Call: (7)  path(1, 6, [1], _G289)
original query
  Call: (8)  edge(1, _L208)
try to match first goal in body of rule 2
  Exit: (8)  edge(1, 5)
... and succeed, with _L208 = 5
^ Call: (8)  not(member(5, [1]))
second goal of body of rule 1
  Call: (9)  lists:member(5, [1])      
  Call: (10) lists:member(5, [])
  
  Fail: (10) lists:member(5, [])
  
  Fail: (9)  lists:member(5, [1])
member fails
^ Exit: (8)  not(member(5, [1]))
so not(member...) succeeds
  Call: (8)  path(5, 6, [5, 1], _G344)
third goal in body of rule 2 -
recursively look for a path from 5 to 6
  Call: (9)  edge(5, _L246)
look for an edge leaving 5
  Exit: (9)  edge(5, 8)
and succeed: _L246 = 8
^ Call: (9)  not(member(8, [5, 1]))
second goal as before
  Call: (10) lists:member(8, [5, 1])
 
  Call: (11) lists:member(8, [1])
 
  Call: (12) lists:member(8, [])
 
  Fail: (12) lists:member(8, [])
 
  Fail: (11) lists:member(8, [1])
 
  Fail: (10) lists:member(8, [5, 1])
 
^ Exit: (9)  not(member(8, [5, 1]))
 
  Call: (9)  path(8, 6, [8, 5, 1], _G353)
again recursively call path to look
for a path from 8 to 6.
  Call: (10) edge(8, _L267)
first goal of third invocation of path
  Exit: (10) edge(8, 6)
first goal succeeds
  Call: (10) not(member(6, [8, 5, 1]))
 
  ...
 
^ Exit: (10) not(member(6, [8, 5, 1]))
second goal succeeds
  Call: (10) path(6, 6, [6, 8, 5, 1], _G362)
fourth call to path, looking for
a path from 6 to 6...
  Exit: (10) path(6, 6, [6, 8, 5, 1], [6])
this time rule 1 applies, & succeeds at once
  Call: (9)  path(8, 6, [8, 5, 1], [8, 6])
which means that the third invocation
of path succeeds...
  Call: (8)  path(8, 6, [5, 1], [5, 8, 6])
which means that the second invocation
of path succeeds...
  Call: (7)  path(8, 6, [1], [1, 5, 8, 6])
and so the first invocation
of path succeeds...

Path = [1, 5, 8, 6]

Yes

To turn off tracing, type notrace! at the prompt (?-).

UNSW's CRICOS Provider No. is 00098G
Copyright © Bill Wilson, 2002, 2006. The original path code is due to Claude Sammut.