Finding an acyclic path, Path, from A to Z in Graph.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: acyclic_path.pl

% Figure 9.20  Finding an acyclic path, Path, from A to Z in Graph.
 
 
 
 
 
% path( A, Z, Graph, Path): Path is an acyclic path from A to Z in Graph
 
 
 
:- op( 900, fy, not).
 
 
 
path( A, Z, Graph, Path)  :-
 
  path1( A, [Z], Graph, Path).
 
 
 
path1( A, [A | Path1], _, [A | Path1] ).
 
 
 
path1( A, [Y | Path1], Graph, Path)  :-
 
  adjacent( X, Y, Graph),
 
  not member( X, Path1),                        % No-cycle condition
 
  path1( A, [X, Y | Path1], Graph, Path).
 
 
 
not Goal  :-
 
  Goal, !, fail
 
  ; 
 
  true.