Encoding hamcycle.dlv

Name	hamcycle.dlv
Class Tree	[Root] Graph Problems (32) Hamilton (17) HamiltonianCycle (6)
Submitter	Martin Gebser
Author
Description	A DLV encoding for the Hamiltonian Cycle problem. By Wolfgang Faber <>.
Created	2009-03-30 13:03
Modified	2008-11-29 00:10
Languages	dlv
Language Features
Compatible Instance Classes
Input Predicates
Output Predicates
Encoding Parameter
Standalone	No
Tags
Attributes
Content	% A DLV encoding for the Hamiltonian Cycle problem. % Input graph is undirected. % By Wolfgang Faber <wf@wfaber.com> % Work on the directed representation. A directed HC of this exists iff an % undirected HC exists in the undirected graph. It is just easier to deal with. arc(X,Y) :- edge(X,Y). arc(Y,X) :- edge(X,Y). % Take the vertex identified by bound() as arbitrary starting point. % Choose an outgoing arc and work the way along the thus constructed path. in_hm(X,Y) v out_hm(X,Y) :- bound(X), arc(X,Y). in_hm(X,Y) v out_hm(X,Y) :- reached(X), arc(X,Y). reached(Y) :- in_hm(_,Y). % Each node must have exactly one incoming and one outgoing arc of the HC. :- vtx(X), not #count{ Y: in_hm(X,Y)} = 1. :- vtx(Y), not #count{ X: in_hm(X,Y)} = 1. % The HC must be connected. :- vtx(X), not reached(X). % Finally express the HC using edge representations of the input graph. hc(X,Y) :- in_hm(X,Y), edge(X,Y). hc(X,Y) :- in_hm(Y,X), edge(X,Y).

Actions