# Encoding lparse.tight

Name lparse.tight [Root]    Graph Problems (32) Martin Gebser Hamilton cycle problem The graph is given as facts "vtx(X)." and "edge(X,Y)." Predicate perm(I,X) defines a permutation of vertices: vertex X in position I of the permutation. Then we make sure that two consequtive vertices in the permutation are connected. Then we build the key predicate "hc". Atom "hc(X,Y)" represents the fact that edge (X,Y) is in the Hamiltonian cycle to be constructed. 2009-03-30 13:03 2008-11-29 00:10 No %% Hamilton cycle problem %% The graph is given as facts "vtx(X)." and "edge(X,Y)." %% Predicate perm(I,X) defines a permutation of vertices: vertex X %% in position I of the permutation. Then we make sure that two %% consequtive vertices in the permutation are connected. %% Then we build the key predicate "hc". Atom "hc(X,Y)" represents the fact %% that edge (X,Y) is in the Hamiltonian cycle to be constructed. %hide. %show hc(X,Y). % Define the permutation 1 { perm(I,X) : vtx(I) } 1 :- vtx(X). 1 { perm(I,X) : vtx(X) } 1 :- vtx(I). % Two consequtive vertices in the permutation are connected :- vtx(I;I+1;X;Y), perm(I,X), perm(I+1,Y), not edge(X,Y), not edge(Y,X). :- vtx(X;Y), bound(N), perm(N,X), perm(1,Y), not edge(X,Y), not edge(Y,X). % Compute predicate "dhc" dhc(X,Y) :- vtx(I;I+1;X;Y), perm(I,X), perm(I+1,Y). dhc(X,Y) :- vtx(X;Y), bound(N), perm(N,X), perm(1,Y). % Compute predicate "hc" hc(X,Y) :- dhc(X,Y), edge(X,Y). hc(X,Y) :- dhc(Y,X), edge(X,Y).