windows 安装metis_图划分软件Metis的使用（win10+vs2017）

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

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

在我当前的研究课题中一个子问题涉及到图划分，使用Metis的C/C++接口成功求解了该问题。本文主要记录一下Metis软件包的简单使用过程，更多内容请参考Karypis Lab官网。

0. 准备条件VS2017

CMake 3.18

1. 下载&安装

参考Win10 VS安装METIS和使用METIS软件包进行图划分，这两篇博客文章已经介绍得很详细，按照步骤进行即可。有几点这里再强调一下：官方文件BUILD-Windows.txt中建议使用CMake 2.8，但CMake 2.8不支持vs2017，下载安装最新版本的CMake即可，建议使用Scoop安装。

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

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

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

2. 在新项目中添加依赖

vs中引用第三方静态库永远都是关注两个文件(.h和.lib)、三个配置项：附加包含目录：.h文件所在的目录附加包含目录附加库目录：.lib文件所在的目录附加库目录附加依赖项：.lib文件附加依赖项建议：在新项目中建立Lib/目录，将用到的第三方库文件都复制到该目录，使用相对路径配置附加包含/库目录(如上述图中所示)，避免使用绝对路径，这样可以方便项目在不同机器之间迁移和节约协同开发成本。如下图所示：使用相对路径配置依赖项

3. Metis’ API介绍

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

Metis提供了Recursive和Kway两种划分方式，分别基于multilevel recursive bisection和multilevel k-way partitioning实现。我们这里不关心其核心算法思路，仅关注其具体使用场景，下面这段话摘自官网的Discussions：”This function(METIS_PartGraphKway) should be used to partition a graph into a large number of partitions(greater than 8). If a small number of partitions is desired, the METIS_PartGraphRecursive should be used instead, as it produces somewhat better partitions.”

即求解划分子图数目较多时(官方建议划分8个以上子图)使用METIS_PartGraphKway，小规模划分使用METIS_PartGraphRecursive能获得质量更好的解，在后面的实验中也验证了这点。

此外，重点关注以下几个参数(更多参数信息请参考文档manual.pdf)：nvtxs: 节点数目。

ncon: 节点权重维度，默认1。

xadj,adjncy: Metis使用压缩图(CSR)表示图的邻接关系，详情参考文档Metis’ API/Graph data structure部分。

vwgt: 节点权重列表，设为NULL表示节点无权重或所有节点权重相同，相当于按照子图中节点的数目平衡划分。

adjwgt: 边的权重列表，默认优化目标为切断边的权重之和最小，设为NULL则表示按照切边数最小划分。

nparts: 要划分的子图数目。

objval: 目标函数值。

part: 保存划分结果。

4. Demo注意：Demo使用了manual.pdf中的一个简单带权算例，怎样在VS中用C++调用METIS提供的API和使用METIS软件包进行图划分两篇博客文章中也使用了同样的算例。但通过我个人的学习与理解，认为他们在调用API时出现了明显的失误并已经在各自文章的评论区出指出了问题，如果我的理解有误，欢迎批评指正。算例图示及文件格式算例图示及文件格式代码

#include #include #include #include #include #include

using namespace std;

vector func(vector &xadj, vector &adjncy, vector &adjwgt, decltype(METIS_PartGraphKway) *METIS_PartGraphFunc) {

idx_t nVertices = xadj.size() – 1; // 节点数 idx_t nEdges = adjncy.size() / 2; // 边数 idx_t nWeights = 1; // 节点权重维数 idx_t nParts = 2; // 子图个数≥2 idx_t objval; // 目标函数值 vector part(nVertices, 0); // 划分结果

int ret = METIS_PartGraphFunc(&nVertices, &nWeights, xadj.data(), adjncy.data(),

NULL, NULL, adjwgt.data(), &nParts, NULL,

NULL, NULL, &objval, part.data());

if (ret != rstatus_et::METIS_OK) { cout << “METIS_ERROR” << endl; }

cout << “METIS_OK” << endl;

cout << “objval: ” << objval << endl;

for (unsigned part_i = 0; part_i < part.size(); part_i++) {

cout << part_i + 1 << ” ” << part[part_i] << endl;

}

return part;

}

int main() {

ifstream ingraph(“graph.txt”);

int vexnum, edgenum;

string line;

getline(ingraph, line);

istringstream tmp(line);

tmp >> vexnum >> edgenum;

vector xadj(0);

vector adjncy(0); // 压缩图表示 vector adjwgt(0); // 节点权重

idx_t a, w;

for (int i = 0; i < vexnum; i++) {

xadj.push_back(adjncy.size());

getline(ingraph, line);

istringstream tmp(line);

while (tmp >> a >> w) {

adjncy.push_back(a – 1); // 节点id从0开始 adjwgt.push_back(w);

}

}

xadj.push_back(adjncy.size());

ingraph.close();

vector part = func(xadj, adjncy, adjwgt, METIS_PartGraphRecursive);

//vector part = func(xadj, adjncy, adjwgt, METIS_PartGraphKway);

ofstream outpartition(“partition.txt”);

for (int i = 0; i < part.size(); i++) { outpartition << i + 1 << ” ” << part[i] << endl; }

outpartition.close();

return 0;

}运行结果METIS_PartGraphRecursive划分结果：METIS_PartGraphKway划分结果：

可以看出，对于上述仅划分两个子图的情况，METIS_PartGraphRecursive要优于METIS_PartGraphKway；但在我的研究课题中，算例规模和子图数目稍大一些，经过测试使用METIS_PartGraphKway求解的质量更好。建议：在实际使用过程中，可能会由于算例规模的变化交替使用两种划分办法。由于这两个API参数与返回值形式完全一致，建议使用传递函数指针的方式区分调用，避免写出大量重复代码。

Github

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

ReferenceWin10 VS安装METIS_qq_40611993的博客-CSDN博客log.csdn.net

相关资源：jFB精良分班软件绿色版-教育工具类资源-CSDN文库

来源：涂薏杭