确定两个集团是否不同

Question

假设我有一个图，并希望在图中找到两个不同的类群。团是图顶点的子集，其中所有顶点都是连通的。剪贴画3的两个团(a，b，c)和(b，c，d)的例子图：

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

​

​

得到两个团很容易：

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

它可以工作，但我不喜欢它需要两行。我如何把它放在一个约束中？

Answer 1

，我如何将它放在一个约束中？

这有点棘手，因为您基本上想要一个存在主义的量化：“集团之间必须至少有一个顶点的差异”，所以简单地插入导出differ/0的规则主体是行不通的。(因为这将是对所有顶点的普遍量化)

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

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

然而，取决于输入图的大小，我可以想象这可能会导致性能问题。

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

part)

• Configure
• 只查找一个组(基本上是注释掉clique2
• ，即通过从clingo.

请求的答案集的数量，您实际想要的组数)。

在您的场景中，这将是..$clingo -n 2 clique.asp，附加的额外奖励是，每个答案集只得到一个组，以及您想要的多个(不同的)集群。