### 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 `edge`s 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 lookfor 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 fora 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 invocationof path succeeds... ` Call: (8) path(8, 6, [5, 1], [5, 8, 6])` which means that the second invocationof path succeeds... ` Call: (7) path(8, 6, [1], [1, 5, 8, 6])` and so the first invocationof 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.