Please wait ...

Benchmark(s) have been added to cart.

Tag has been added.

• Login
• Links
• FAQs
• Contact

Navigation

• Instance
  • Show Instances
• Problem
  • Show Problems
• Show Tags
• Search
• Cart

Encoding master_hc.lp

Name	master_hc.lp
Class Tree	[Root]    Graph Problems (32)    Hamilton (17)    HierarchicCycle (1)
Submitter	Martin Gebser
Author	Martin Gebser
Description	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.
Created	2009-08-19 17:24
Modified	2009-08-19 17:24
Languages	lparse Gringo 2.0.2
Language Features
Compatible Instance Classes	Hierarchic Representation
Input Predicates	edge/4 initialvtx/2 vtx/2
Output Predicates	master_hc/2
Encoding Parameter
Standalone	No
Tags	Solution Projection (Martin Gebser)
Attributes
Content	%% 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).