Encoding partitioning_decision.gringo

Name partitioning_decision.gringo [Root]    Graph Problems (32) Martin Gebser Martin Gebser and Roland Kaminski A Gringo encoding of Partitioning for weighted graphs. 2009-03-12 17:24 2009-03-22 17:09 Partitioning edge/2edgebound/1parts/1vtx/1vtxbound/1weight_wtedge/3 partition/2 No ASP Contest 09 (Martin Gebser) #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).