# Encoding hamcycle.dlv

Name hamcycle.dlv [Root]    Graph Problems (32)    Hamilton (17) Martin Gebser A DLV encoding for the Hamiltonian Cycle problem. By Wolfgang Faber <>. 2009-03-30 13:03 2008-11-29 00:10 No % A DLV encoding for the Hamiltonian Cycle problem. % Input graph is undirected. % By Wolfgang Faber % 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).