% Figure 9.21   Path-finding in a graph:  Path is 
% an acyclic path with cost Cost from A to Z in Graph.


% path( A, Z, Graph, Path, Cost):
%    Path is an acyclic path with cost Cost from A to Z in Graph

path( A, Z, Graph, Path, Cost)  :-
  path1( A, [Z], 0, Graph, Path, Cost).

path1( A, [A | Path1], Cost1, _, [A | Path1], Cost1).

path1( A, [Y | Path1], Cost1, Graph, Path, Cost)  :-
   adjacent( X, Y, CostXY, Graph),
   not( member( X, Path1)), % extra parentheses needed in SWI
   Cost2 is Cost1 + CostXY,
   path1( A, [X, Y | Path1], Cost2, Graph, Path, Cost).

% adjacent for weighted digraphs represented by node and 
% arc sets (represented as lists)
adjacent( X,Y,CostXY,digraph(_,Arcs)) :-
 member( a(X,Y,CostXY),Arcs).

% example 1: any path
test1(A, Z, Graph, Path, Cost) :-
 A = s, Z = u, 
 Graph = digraph( [s,t,u,v], [a(s,t,3),a(t,v,1),a(t,u,5),a(u,t,2),a(v,u,2)]),
 path( A,Z,Graph,Path,Cost).

% example 2: "shortest" (cheapest) path
test2(A, Z, Graph, MinPath, MinCost) :-
 A = s, Z = u, 
 Graph = digraph( [s,t,u,v], [a(s,t,3),a(t,v,1),a(t,u,5),a(u,t,2),a(v,u,2)]),
 path( A,Z,Graph,MinPath,MinCost),
 not( (path(A,Z,Graph,_,Cost), Cost < MinCost)).

% example 3: "longest" (most expensive) path
test3(A, Z, Graph, MaxPath, MaxCost) :-
 A = s, Z = u, 
 Graph = digraph( [s,t,u,v], [a(s,t,3),a(t,v,1),a(t,u,5),a(u,t,2),a(v,u,2)]),
 path( A,Z,Graph,MaxPath,MaxCost),
 not( (path(A,Z,Graph,_,Cost), Cost > MaxCost)).
