Please wait ...

Benchmark(s) have been added to cart.

Tag has been added.

• Login
• Links
• FAQs
• Contact

Navigation

• Instance
  • Show Instances
• Problem
  • Show Problems
• Show Tags
• Search
• Cart

Encoding lparse.tight

Name	lparse.tight
Class Tree	[Root]    Graph Problems (32)    Hamilton (17)    HamiltonianCycle (6)
Submitter	Martin Gebser
Author
Description	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.
Created	2009-03-30 13:03
Modified	2008-11-29 00:10
Languages	lparse
Language Features
Compatible Instance Classes
Input Predicates
Output Predicates
Encoding Parameter
Standalone	No
Tags
Attributes
Content	%% 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).