graph - 减少 METIS 中图分区的通信量

Question

我一直在使用 METIS 对图进行分区。到目前为止，我没有使用任何特殊选项，所以我假设 METIS 正在对图形进行分区，同时最小化边缘切割。

问题是，我正在处理的图很少有有很多邻居的顶点。我想这意味着我将不得不通过减少通信量而不是边缘切割的选项。

我该怎么做呢？我不明白第 26 页第 5.8 节中的 vsize 参数有什么意义。我需要弄乱 ncon 或 vwgt 或 objval 吗？我只是做 options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_VOL 并将其传递给函数吗？

另外，对于顶点数可能不是 2 的幂的图，我应该使用哪个函数变体？k-way（很可能）或二等分？

我会在 METIS 论坛上问这些问题，但不幸的是，我注册它已经有一段时间了，他们的网站没有任何回复，所以我在这里问。

Answer 1

'vsize' 用于指定与顶点关联的通信量。对于大多数应用程序，您不需要指定它，因为它被假定为一个。如果没有平衡约束，可以忽略 ncon 和 vwgt。objval 变量只是让您知道生成的分区的目标值是多少（切边的总权重或总通信量）。

您将希望对大量分区使用 k-way 分区，因为它往往会更快，并且可能会产生更高质量的结果。两者都将处理两个分区的非幂。顶点的数量无关紧要。