ASP Clingo - 將圖分解爲n個集羣

Question

對於給定的圖，我需要使用至多n個集團來表示它。 我有這個任務的問題。 這與圖的n染色相似，與給定的圖相反（當圖A中的邊（a，b）比邊（a，b）不在圖B中時，圖b與圖A相反。我寫了下面的代碼：

#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. 

，但它並不適用於特定的測試工作：

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). 

例如顏色（1）==顏色（2）=色彩（3）==顏色（4）。 當我刪除這個公式之一，它也不起作用。

Answer 1

一個解決辦法可能是先定義complementary graph第一，然後選擇顏色：

#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).