METIS串行图形分割器

Question

METIS图划分算法用于划分大型图。我有一个图，实际上是一片森林。我想知道METIS在这种情况下是如何进行分区的？

Answer 1

实际上，METIS可以划分大图，但这并不意味着它不能管理较小的图或不同类型的图。

森林只是一种没有圈的特殊类型的图，其中我们可以有断开的部分……

与任何其他类型的图一样，METIS将执行三级分区算法：

1. 粗化(在您的例子中，您使用的是森林图，因此它可能会非常快地完成，因为这种类型的图可能会有少量的边或connections)
2. Initial partitioning
3. Uncoarsening +细粒度平衡。

所以基本上，一切都会像任何类型的图一样工作。

根据我的个人经验，我确实发现METIS在处理不连通的图(而森林是不连通的图)时没有给我最优的结果，所以我实现了自己的逻辑来寻找所有连接的顶点组，然后使用METIS来划分这个组(这是连接的)……

我推荐阅读来自METIS library documentation的关于METIS的文章。