约束编程求解器（gecode）图的模型建议

Question

问题：给定一个带标签的（1..n）无向图，在Gecode中创建一个模型来寻找具有给定序列度的超图：

难点：主要难点是找到花哨的模型来准确表达度数：

为什么不用邻接矩阵？因为图往往又大又稀疏

为什么不用边列表？我们要添加边，但我们不知道有多少，CP 需要预定义的变量数量（我说得对吗？）

为什么不用邻接表？ 将问题建模为集合列表我们需要对所有 i、j 施加约束：(j in a[i] <=> i在 [j])

Answer 1

在您提供的可能性中，使用 "Adjacency list" 可能是最好的。

您担心的是您将需要许多传播者在集合之间建立通道；然而 Gecode 包括一个特殊的通道传播器来在集合之间进行通道：http://www.gecode.org/doc-latest/reference/classGecode_1_1Set_1_1Channel_1_1ChannelSet.html。这个传播者完全按照你描述的方式传播，应该尽量减少保持集合一致的努力。