Encoding partitioning_decision.gringo

Name	partitioning_decision.gringo
Class Tree	[Root] Graph Problems (32) Partitioning (1)
Submitter	Martin Gebser
Author	Martin Gebser and Roland Kaminski
Description	A Gringo encoding of Partitioning for weighted graphs.
Created	2009-03-12 17:24
Modified	2009-03-22 17:09
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Choice rules Weight constraints
Compatible Instance Classes	Partitioning
Input Predicates	edge/2 edgebound/1 parts/1 vtx/1 vtxbound/1 weight_wtedge/3
Output Predicates	partition/2
Encoding Parameter
Standalone	No
Tags	ASP Contest 09 (Martin Gebser)
Attributes
Content	#hide. #show partition/2. % normalize the graph uedge(U,V) :- edge(U,V), U < V. uedge(U,V) :- edge(V,U), U < V. uedge(U,V,W) :- uedge(U,V), weight_wtedge(U,V,W). uedge(U,V,W) :- uedge(U,V), weight_wtedge(V,U,W). % select a partition of vertices 1 { partition(U,K) : vtx(U) } V :- parts(K), vtxbound(V). 1 { partition(U,K) : parts(K) } 1 :- vtx(U). % check that the sum of the weights between % two partitions is lower than edgebound :- not [ adjacent(U,V,X,Y) : uedge(U,V,W) = W ] E, edgebound(E), parts(X;Y), X < Y. adjacent(U,V,X,Y) :- uedge(U,V), partition(U,X), partition(V,Y), X < Y. adjacent(U,V,X,Y) :- uedge(U,V), partition(U,Y), partition(V,X), X < Y. % check reachability reach(K,U) :- partition(U,K), not partition(V,K) : vtx(V) : V < U. reach(K,V) :- uedge(U,V), reach(K,U), partition(V,K). reach(K,V) :- uedge(V,U), reach(K,U), partition(V,K). :- partition(U,K), not reach(K,U).

Actions