Encoding hierarchical-clustering_decision.gringo

Name	hierarchical-clustering_decision.gringo
Class Tree	[Root] Graph Problems (32) Hierarchical Clustering (1)
Submitter	Martin Gebser
Author	Martin Gebser and Roland Kaminski
Description	A Gringo encoding of the Hierarchical Clustering problem.
Created	2009-03-12 15:44
Modified	2009-03-12 15:49
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Choice rules
Compatible Instance Classes	Hierarchical Clustering
Input Predicates	bound/1 edge/2 levels/1 vtx/1
Output Predicates	levelvtx/2 parentedge/2
Encoding Parameter
Standalone	No
Tags	ASP Contest 09 (Martin Gebser)
Attributes
Content	#hide. #show levelvtx/2. #show parentedge/2. % normalize graph uedge(U,V) :- edge(U,V), U < V. uedge(U,V) :- edge(V,U), U < V. % every vertex is on exactly one level 1 { levelvtx(L,U) : levels(L) } 1 :- vtx(U). % a vertex U on level L>1 has exactly one parentedge 1 { parentedge(P, U) : uedge(P, U), parentedge(P, U) : uedge(U, P) } 1 :- levelvtx(L,U), L > 1. % the parentedge vertex must have level L-1 :- levelvtx(L,V),parentedge(P,V), not levelvtx(L-1,P). % every cluster has at most b elements :- not { parentedge(P,U) : vtx(U) } B, vtx(P), bound(B). % level one is handled specially :- not { levelvtx(1,U) : vtx(U) } B, bound(B). % every cluster is a clique :- parentedge(P,U), parentedge(P,V), U < V, not uedge(U,V). % level one is handled specially again :- levelvtx(1,U), levelvtx(1,V), U < V, not uedge(U,V).

Actions