For a given graph i need to represent it using at most n cliques. I have problem with this task. This is similar to n-coloring of graph which is opposite of given graph (Graph b is opposite of graph A when if edge(a, b) in graph A than edge(a, b) is not in graph B). I wrote the following code:
#const n = 3.
{ color(X,1..n) } = 1 :- node(X).
:- not edge(X, Y), color(X,C), color(Y,C).
:- edge(X, Y), color(X,A), color(Y,B), A != B.
but it doesn't work for given test:
node(1).
node(2).
node(3).
node(4).
edge(1, 2).
edge(2, 1).
edge(2, 3).
edge(3, 2).
edge(3, 4).
edge(4, 3).
For example color(1) == color(2) != color(3) == color(4). When i delete one of this formulas it also doesn't work.
One solution could be to first define the complementary graph first, then choose the colors:
#const n = 3.
% one color per node
1 { color(X,1..n) } 1 :- node(X).
% yield complementary graph, without reflexive edges.
cedge(X,Y):- not edge(X,Y) ; node(X) ; node(Y) ; X<Y.
% avoid models where two nodes linked in the complementary graph have the same color
:- cedge(X,Y) ; color(X,C) ; color(Y,C).