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

Question

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

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

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

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

为什么不是邻接表？将问题建模为一个集合列表，我们需要对所有 i、j 施加一个约束：（j in a[i] <=> i in a[j]）

Answer 1

在您提供的可能性中，使用“邻接列表”可能是最好的。

您担心的是，您将不得不有许多传播者在集合之间进行引导；但是 Gecode 包含一个特殊的通道传播器，用于在集合之间进行通道：http ://www.gecode.org/doc-latest/reference/classGecode_1_1Set_1_1Channel_1_1ChannelSet.html 。这个传播器完全按照您描述的方式进行传播，并且应该尽量减少保持集合一致的努力。