确定两个集团是否不同

Question

假设我有一个图表并想在图表中找到 2 个不同的派系。团是图顶点的子集，所有这些顶点都连接在一起。具有 2 个派系 (a,b,c) 和 (b,c,d) 的派系大小为 3 的示例图：

edge(a,b). edge(a,c). edge(b,c). edge(d,c). edge(d,b).
vertex(X;Y) :- edge(X,Y).

获得 2 个派系相当容易：

#const cs=3. % cliquesize
cs{clique1(X) : vertex(X)}cs.
:- clique1(X), clique1(Y), X!=Y, not edge(X,Y), not edge(Y,X).
cs{clique2(X) : vertex(X)}cs.
:- clique2(X), clique2(Y), X!=Y, not edge(X,Y), not edge(Y,X).

#show clique1/1.
#show clique2/1.

给出：

Answer: 1
clique2(d) clique1(a) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 2
clique2(d) clique1(d) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 3
clique2(a) clique1(a) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 4
clique2(a) clique1(d) clique2(b) clique2(c) clique1(b) clique1(c)
SATISFIABLE

可以解释为：

Answer 1: (a,b,c), (b,c,d)
Answer 2: (b,c,d), (b,c,d)
Answer 3: (a,b,c), (a,b,c)
Answer 4: (b,c,d), (a,b,c)

但是如何测试两个派系是否不同？我试过了

differ() :- clique1(X), clique2(Y), X!=Y.
:- not differ().

但这对输出没有影响。如何测试两个小集团是否不同？

现在我找到了这个解决方案：

differ() :- clique1(X), vertex(X), not clique2(X).
:- not differ().

它可以工作，但我不喜欢它需要 2 行。如何将其置于一个约束中？

Answer 1

How do I put it in one constraint?

这有点棘手，因为您基本上想要一个存在量化：“派系之间必须至少有一个顶点差异”，所以简单地插入您的规则的主体派生 differ/0 是行不通的。（因为这将是对所有顶点的通用量化）

我认为以下内容符合您对单行约束的要求：

:- #count{X : clique1(X), not clique2(X)} < 1.

但是，根据您的输入图有多大，我可以想象这可能会导致性能问题。

我不确定您的确切要求，但也许您可以采取稍微不同的方法：

只找一个clique（基本上注释掉clique2部分）
通过您从 clingo 请求的答案集数量配置您实际想要的派系数量。

在你的场景中，那将是 ..$clingo -n 2 clique.asp，还有额外的好处，即每个答案集你只能得到一个派系，无论你想要多少（不同的）派系。

确定两个集团是否不同

determining if two cliques are different

answer-set-programming

clingo