Metis从安装到使⽤全教程（Linux）
Metis全教程
Metis的安装
下载到本地后解压等操作本⽂不再叙述。
基本环境配置
在编译和安装METIS 5.0时要做好以下⼏个基本操作：
1. 你需要⼀个⽀持C99标准的C编译器 .Gcc也可以.
2. 你需要安装GNU make 以及 Cmake 2.8（/）
3. 在 include/metis.h 中修改以下代码，做到与⾃⼰计算机位数匹配(32bit or 64 bit).
//if your system is 64 bit.
#define IDXTYPEWIDTH 64
/
/if your system is 32 bit
#define IDXTYPEWIDTH 32
编译以及安装
1. 在metis的顶层⽂件夹下执⾏
make config
2. 在metis的顶层⽂件夹下执⾏
make
3. 执⾏完上述步骤后，build⽂件夹中会出现Linux-x86_64⽂件夹，进去可以看到build后的结果，接下来需要进⾏安装METIS. make install
若上述操作报错，原因是否为**Error at include/ake:36(file): file INSTALL cannot copy file**. 若是则需要修改make install的地址。
由于默认的安装前缀为 /usr/loacl. 所以我们需要根据⾃⼰METIS 的⽂件地址进⾏修改。
make config prefix=~/myroot/
//my root为你的metis顶层⽂件夹的地址
到此位置METIS的 编译 以及 安装 全部结束。
使⽤METIS中programs
gpmetis [options] graphfile nparts
//options 为许多具体参数，可以参见上述pdf
//graphfile 为graph的⽂件
//nparts 为想要分成⼏部分
上图为⼀个简单的实例，左边为⽆向⽆权图，右边为⽆向有权图，我们以左图为例进⾏介绍。
Graph File
7 11 // 7个顶点，11条边
5 3 2 //顶点1的领结点:5 3 2
1 3 4 //顶点2的领结点:1 3 4
5 4 2 1 //顶点3的领结点:5 4 2 1
2 3 6 7 //顶点4的领结点:2 4 6 7
1 3 6 //顶点5的领结点:1 3 6
5 4 7 //顶点6的领结点:5 4 7
6 4 //顶点7的领结点:6 4
我们将其格式放⼊⼀个txt中，名称为，将其放⼊gpmetis所在的⽂件夹下build/Linux-x86_64/programs 执⾏以下操作：
./ 3
//把中表⽰的图分成3份
我们可以得到⼀个part.3的⽂件以及终端⾥出现如下图所⽰结果
由上图可以看到分图结果为
part1: 6 7
part2: 1 3 5
part3: 2 4
具体的切图细节信息在第⼀个图中可以看出，Edgecut为6即切的过程经过了6条边。具体信息可以在pdf中进⾏查阅。
使⽤METIS API
上述过程为调⽤METIS中的program进⾏分图，如何把METIS接⼊到我们的程序做到普遍使⽤是接下来要讨论的问题。在METIS中提供了9个API，其中我们主要讨论接⼊graph的API，分别为
METIS_PartGraphRecursive
METIS_PartGraphKway
每个API的具体参数见上述manual 的pdf. 这两个API为两个不同切图⽅法，⼀个为multilevel recursive
bisection，另⼀个为multilevel k-way partition.
下⾯通过⼀个简单的demo(test.cpp)进⾏调⽤API
#include<cstddef>/* NULL */
#include<metis.h>
#include<iostream>
#include<vector>
// Build with
// g++ -std=c++11 test.cpp -o test.o -lmetis
//run with
./test.o
int main(){
idx_t nVertices =6;
idx_t nEdges    =7;
idx_t nWeights  =1;
idx_t nParts    =2;
idx_t objval;
std::vector<idx_t>part(nVertices,0);
// Indexes of starting points in adjacent array
std::vector<idx_t> xadj ={0,2,5,7,9,12,14};
// Adjacent vertices in consecutive index order
std::vector<idx_t> adjncy ={1,3,0,4,2,1,5,0,4,3,1,5,4,2};
linux教程第五版pdf下载
// Weights of vertices
/
/ if all weights are equal then can be set to NULL
std::vector<idx_t>vwgt(nVertices * nWeights,0);
int ret =METIS_PartGraphKway(&nVertices,& nWeights, xadj.data(), adjncy.data(), NULL,NULL,NULL,&nParts,NULL,
NULL,NULL,&objval, part.data());
std::cout << ret << std::endl;
for(unsigned part_i =0; part_i < part.size(); part_i++){
std::cout << part_i <<" "<< part[part_i]<< std::endl;
}
return0;
}
运⽤该API需要注意它的Input，也就是传⼊API中的数据。在这⾥它⽤到的是CSR数据转换，具体实现算法可以⾃⾏搜索CSR格式，下图为CSR的⼀个实际转换过程。
上图为⼀个graph，每⼀个数字代表⼀个结点，其中的连接线代表⼀个边，则我们需要两个数组进⾏储存这些信息从⽽完成CSR格式转换
adjncy为从0开始每个点的领结点，xadj为adjncy中的下标位置。
xadj 第⼀个为0，则第⼀个结点(0)从adjncy的第0位开始。
xadj 第⼆个为2，则第⼆个结点(1)从adjncy的第2位开始。(位数0~2中间的值1 5 为第⼀个顶点的领结点)
xadj 第三个为5，则第三个结点(2)从adjncy的第5位开始。(位数2-5中间的值0 2 5 为第⼆个顶点的领结点)
以上两张图分别为此demo⽤到的graph样式以及输出结果。第⼀个1为ret的输出，即成功分图，分图结果如下所⽰
part1: 0 1 3
part2: 2 4 5
总结
本blog介绍了METIS库从安装到使⽤的全过程，我也会持续更新⼀些图的切分算法以及实现⼀些⼩的算法⽐如CSR格式转换，DFS有向图的环等。希望对⼤家有所帮助。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。