使用METIS软件包进行图划分

目录

• • 0 前言
  • 1 安装METIS
  • 2 安装CMake GUI
  • 3 用CMake GUI编译METIS
  • 4 修改gk_arch.h文件
  • 5 用VS生成解决方案
  • 6 在VS中进行图划分
  • 参考文献

0 前言

1 安装METIS

（1）下载软件包
下载地址：http://glaros.dtc.umn.edu/gkhome/metis/metis/download
软件包：metis-5.1.0.tar.gz

（2）解压软件包
右击软件包，进行解压。

5 用VS生成解决方案

（1）打开VS，选择“文件打开项目/解决方案”，打开METIS的Build文件夹下的METIS.sln文件，出现下图。

输入文件格式： 第1行的7和11表示图有7个顶点和11条边；第i+1行表示点i所邻接的点，后面紧跟边的权重，例如第2行的前两个数“4 1”，表示顶点1（图示中）与顶点5邻接，邻接边权重为1。（提示：若原始图的顶点id与行数不一致，需做一步转换，可创建一个文件记录行数与原顶点id的对应关系。）

输出文件内容：

输出文件格式： 第一列的数字为graph.txt中的行 ，代表顶点id；原图被划分为两部分，通过第二列的0和1区分，示例中0 1 2 4 为一部分，3 5 6 为另一部分。

参考文献

[1] George Karypis and Vipin Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Scientific Computing 20(1): 359-392(1998).