Encoding lparse.nontight

Name	lparse.nontight
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)." One vertex v is given as initial vertex "initialvtx(v)." The key predicate is "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)." %% One vertex v is given as initial vertex "initialvtx(v)." %% The key predicate is "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 undirected edges uedge(X,Y) :- edge(X,Y). uedge(X,Y) :- edge(Y,X). % Select edges for the cycle { dhc(X,Y) } :- uedge(X,Y). % Each vertex has at most one incoming edge in a cycle :- 2 { dhc(X,Y):uedge(X,Y) }, vtx(Y). % Each vertex has at most one outgoing edge in a cycle :- 2 { dhc(X,Y):uedge(X,Y) }, vtx(X). % Every vertex must be reachable from the initial vertex through chosen % hc(v,u) edges :- vtx(X), not r(X). r(Y) :- dhc(X,Y), uedge(X,Y), initialvtx(X). r(Y) :- dhc(X,Y), uedge(X,Y), r(X), not initialvtx(X). initialvtx(1). % Compute the final solution hc(X,Y) :- dhc(X,Y), edge(X,Y). hc(X,Y) :- dhc(Y,X), edge(X,Y).

Actions

Navigation

Encoding lparse.nontight