# Encoding lparse.nontight

Name lparse.nontight [Root]    Graph Problems (32) Martin Gebser 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. 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)." %% 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).