# Encoding partitioning_chk.lp

Name partitioning_chk.lp [Root]    Miscellaneous (45)    ASP Contest 09 (45) Martin Gebser Martin Gebser and Roland Kaminski 2009-03-13 21:35 2009-03-22 17:10 No #hide. #show partition/2. :- partition(U,K), not vtx(U). :- partition(U,K), not parts(K). % 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). % check partition of vertices :- parts(K), vtxbound(V), not 1 { partition(U,K) : vtx(U) } V. :- vtx(U), not 1 { partition(U,K) : parts(K) } 1. % 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).