# Encoding master_hc.lp

Name master_hc.lp [Root]    Graph Problems (32)    Hamilton (17) Martin Gebser Martin Gebser PROJECTED Hamilton cycle problem The graph is given by facts "vtx(C,V)." and "edge(C1,V1,C2,V2)." where C,C1,C2 and V,V1,V2 are numbers of clumps, resp., of clumps' vertices. One vertex V of a clump C is given as initial vertex "initialvtx(C,V)." The key predicate is "master_hc". Atom "master_hc(C1,C2)" expresses that some "edge(C1,V1,C2,V2)" connects distinct clumps in the Hamiltonian cycle. The instances of "master_hc(C1,C2)" in an answer set themselves provide a small Hamiltonian cycle, built from a subset of the edges in the full cycle. 2009-08-19 17:24 2009-08-19 17:24 Hierarchic Representation edge/4initialvtx/2vtx/2 master_hc/2 No Solution Projection (Martin Gebser) %% PROJECTED Hamilton cycle problem %% %% The graph is given by facts "vtx(C,V)." and "edge(C1,V1,C2,V2)." where %% C,C1,C2 and V,V1,V2 are numbers of clumps, resp., of clumps' vertices. %% One vertex V of a clump C is given as initial vertex "initialvtx(C,V)." %% The key predicate is "master_hc". Atom "master_hc(C1,C2)" expresses that %% some "edge(C1,V1,C2,V2)" connects distinct clumps in the Hamiltonian cycle. %% Select edges for the cycle % { hc(C1,V1,C2,V2) } :- edge(C1,V1,C2,V2). hc(C1,V1,C2,V2) :- not not_hc(C1,V1,C2,V2), edge(C1,V1,C2,V2). not_hc(C1,V1,C2,V2) :- not hc(C1,V1,C2,V2), edge(C1,V1,C2,V2). %% Each vertex has at most one incoming edge in a cycle % :- 2 { hc(C1,V1,C2,V2):edge(C1,V1,C2,V2) }, vtx(C2,V2). :- hc(C1,V1,C2,V2), hc(C1,V3,C2,V2), edge(C1,V1,C2,V2), edge(C1,V3,C2,V2), V1 != V3. :- hc(C1,V1,C2,V2), hc(C3,V3,C2,V2), edge(C1,V1,C2,V2), edge(C3,V3,C2,V2), C1 != C3. %% Each vertex has at most one outgoing edge in a cycle % :- 2 { hc(C1,V1,C2,V2):edge(C1,V1,C2,V2) }, vtx(C1,V1). :- hc(C1,V1,C2,V2), hc(C1,V1,C2,V3), edge(C1,V1,C2,V2), edge(C1,V1,C2,V3), V2 != V3. :- hc(C1,V1,C2,V2), hc(C1,V1,C3,V3), edge(C1,V1,C2,V2), edge(C1,V1,C3,V3), C2 != C3. %% Every vertex must be reached from the initial vertex r(C2,V2) :- hc(C1,V1,C2,V2), edge(C1,V1,C2,V2), initialvtx(C1,V1). r(C2,V2) :- hc(C1,V1,C2,V2), edge(C1,V1,C2,V2), r(C1,V1), not initialvtx(C1,V1). :- vtx(C,V), not r(C,V). %% Adding the following for more efficient search (not needed for correctness) outgoing(C1,V1) :- hc(C1,V1,C2,V2), edge(C1,V1,C2,V2). :- vtx(C1,V1), not outgoing(C1,V1). %% Derive "master_hc" from "hc" master_hc(C1,C2) :- hc(C1,V1,C2,V2), edge(C1,V1,C2,V2), C1 != C2. %% Each clump has at most one incoming edge in a cycle :- master_hc(C1,C2), master_hc(C3,C2), edge(C1,V1,C2,V2), edge(C3,V3,C2,V4), C1 != C3. %% Each clump has at most one outgoing edge in a cycle :- master_hc(C1,C2), master_hc(C1,C3), edge(C1,V1,C2,V2), edge(C1,V4,C3,V3), C2 != C3. %% Output PROJECTION to "master_hc" #hide. #show master_hc(C1,C2).