linux - 如何使用 METIS 使用边权重对图进行分区，以使切边最少？

Question

我有 METIS 输入文件，其中包含图形的边权重。我想用 METIS 对图进行分区，这样 METIS 摘要报告中的切边是 METIS 的可能性最小的。可以是rb、kway或其他算法或选项。

那么什么选项最有效？

目前，以下选项最适合我。

gpmetis -ptype=rb metis.input.file num.of.partitions

Answer 1

使用 k 路分区 (-ptype=kway)，您可以选择最小化切边 (-objtype=cut) 或最小化总通信量 (-objtype=vol)。这两个概念非常相似(参见METIS manual)。

我发现最小化总通信量比切边效果更好，这是因为，当边有权重时，METIS 中的切边被定义为边权重切割的总和。事实证明，最小化这种“切边”会产生更多的边界顶点。

如果所有边权重(暂时)设置为 1，Edgecut 的性能确实会好得多，但使用其他选项会更简单。

来源:METIS 手册和个人经验。