Encoding tsp.dlv

Name	tsp.dlv
Class Tree	[Root] Graph Problems (32) Hamilton (17) TravelingSalespersonSuite (5)
Submitter	Martin Gebser
Author	Wolfgang Faber
Description
Created	2009-03-30 13:03
Modified	2009-03-10 13:06
Languages	dlv
Language Features
Compatible Instance Classes	TravelingSalespersonSuite
Input Predicates	bound/1 edge/2 edgewt/3 maxweight/1 vtx/1
Output Predicates	hc/2
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). :- maxweight(M), #sum{ W,X,Y: hc(X,Y), edgewt(X,Y,W) } > M.

Actions