图划分软件Metis的使用

Metis是由Karypis Lab开发的一个具有强大功能的图划分软件包，可用于划分不规则图(graph)、 格(mesh)以及计算稀疏矩阵(Sparse Matrices)的Fill-Reducing Orderings。它提供了一组可以独立运行的命令行程序，同时也提供API方便集成到C/C++或Fortran程序中。

由于图划分问题np-hard性质带来的求解难度，Metis更新并不频繁（从1997年开始发布，最近一次更新是2013年3月，已经很是良心），其核心算法也不再是当前最优秀的，但并不妨碍它继续作为一个经典且稳定的第三方库在开源领域（如，国产开源CFD软件OneFLOW）中发挥重要作用。

0. 准备条件

• VS2017 / VS2019

• CMake 3.18

1. 下载&安装

参考Win10 VS安装METIS和使用METIS软件包进行图划分，这两篇博客文章已经介绍得很详细，按照步骤进行即可。有几点这里再强调一下：

• 官方文件中建议使用CMake 2.8，但CMake 2.8不支持vs2017，下载安装最新版本的CMake即可，建议使用Scoop安装。

• 配置CMake编译选项时注意选择正确的编译器版本和机器位数，如本次实验中直接选择了vs2017 + release + x64。

• 使用MSC编译器需要注释掉文件中的一行代码，不要忘了。

• 如果CMake配置的目标路径在C盘，可能需要使用管理员权限启动vs2017才能成功生成解决方案。

2. 在新项目中添加依赖

vs中引用第三方静态库永远都是关注两个文件(.h和.lib)、三个配置项：

3. Metis’ API介绍

安装完Metis后可以在目录下找到说明文档，其中介绍了命令行程序(Programs)和API的使用方法。这里主要对用于图划分的两个接口和作简单说明。

• 代码

• 运行结果

可以看出，对于上述仅划分两个子图的情况，要优于；但在我的研究课题中，算例规模和子图数目稍大一些，经过测试使用求解的质量更好。

建议： 在实际使用过程中，可能会由于算例规模的变化交替使用两种划分办法。由于这两个API参数与返回值形式完全一致，建议使用传递函数指针的方式区分调用，避免写出大量重复代码。

Github

项目实例均在vs2017/vs2019上测试，并上传至GitHub，将LearnMetis设为启动项目即可复现实验结果。

Reference

Win10 VS安装METIS

怎样在VS中用C++调用METIS提供的API

使用METIS软件包进行图划分

win10+vs2019从源代码编译 格剖分软件Metis5.1.0