% hamgraph.lp -- Chapter 6, Section 6.1
% Last Modified: 1/29/14
% Finding Hamiltonian cycles in a directed graph.
% Problem: Given a directed graph G and an initial vertex v0, find a path
%          from v0 to v0 that enters each vertex exactly once.
% A path will be represented by a collections of statements of the form
% in(v1, v2) for each directed edge from vertex v1 to v2 in the cycle.

% A path leaves each vertex at most once:
-in(V2,V) :- in(V1,V),
             vertex(V2), 
             V1 != V2.

% A path enters each vertex at most once:
-in(V,V2) :- in(V,V1),
             vertex(V2), 
             V1 != V2.
             
% reached(V) holds if the path enters vertex V on its way 
% from the initial vertex:           
reached(V2) :- init(V1),
               in(V1,V2).
               
reached(V2) :- reached(V1),
               in(V1,V2).
                    
-reached(V) :- vertex(V), not reached(V). 

% Every vertex of the graph must be reached:
:- -reached(V).

% Path generation using disjunction:
in(V1,V2) | -in(V1,V2) :- edge(V1,V2).

% Alternative path generation using a choice rule:
%{in(V1,V2) : edge(V1,V2)}.

% Input graph:
vertex(a).  vertex(b).  vertex(c).  vertex(d).  vertex(e).
edge(a,b).  edge(b,c).  edge(c,d).  edge(d,e).
edge(e,a).  edge(a,e).  edge(d,a).  edge(c,e).
init(a).