首页天道酬勤p图软件有哪些,metis库

p图软件有哪些,metis库

张世龙 05-13 09:07 21次浏览

Metis是由Karypis Lab开发的强大的图表细分包,可用于计算不规则图表(graph )、网格(mesh )和稀疏矩阵(Fill-Reducing Orderings )。 提供一组可以独立运行的命令行程序,并提供API以方便地集成到C/C或Fortran程序中。

由于图形分割问题np-hard的性质带来的难以解决,Metis的更新并不频繁(从1997年开始发表,最近的更新是在2013年3月,已经是良心的),其核心算法也不是现在最好的,但是经典稳定的第三方直播

我目前研究课题的一个子问题涉及图的划分,利用Metis的C/C接口成功解决了这个问题。 本文主要记录Metis软件包的简单使用过程,更多内容请访问Karypis Lab官网。

0 .准备条件VS2017 / VS2019

CMake 3.18

1 .有关下载安装,请参阅浏览windows10vs安装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在文章整理vs2017中的使用。建议:在新项目中创建Lib/目录,并将所有要使用的第三方库文件复制到此目录中。 如上图所示,使用相对路径配置添加包含/库目录以避免使用绝对路径,从而简化了项目在不同计算机之间的迁移和协作开发成本。 如下图所示。

3 .在metis’API中,安装metis后,可以在manual/目录中找到手册manual.pdf。 本节介绍如何使用命令行程序(Programs )和API。 本节简要介绍了用于拆分图的两个接口METIS_PartGraphRecursive和METIS_PartGraphKway。

Metis基于多级别恢复业务分区和多级别k向分区的实现,提供了两种分类方法:恢复和网关。 这里我不关心核心算法的想法,只关注具体的使用场景。 以下词语摘自官方网站的Discussions。

this function (metis _ partgraphkway ) shouldbeusedtopartitionagraphintoalargenumberofpartitions ) greater than8. ifasmalal the metis _ partgraphrecursiveshouldbeusedinstead,asitproducessomewhatbetterpartition

即,在分割图的数量多的情况下(公式中推荐8个以上的分割图),使用METIS_PartGraphKway,在小规模的分割中使用METIS_PartGraphRecursive可以得到更好的解,但是

此外,重点关注以下参数: 有关详细参数信息,请参阅手册manual.pdf。

nvtxs:节点数。

ncon:节点权重维,默认值1。

xadj,adjncy:Metis使用压缩图(CSR )表示图的相邻关系。 有关详细信息,请参阅文档Metis' API/Graph data structure一节。

vwgt:节点权重列表,如果设置为NULL,则表示节点没有权重,或者所有节点权重相同,相当于从子图中的节点数进行均衡分割。

adjwgt:边缘权重列表。 缺省优化目标是切割边权重之和最小,如果设置为NULL,则以切边数最小分割。

nparts:要分割的子图的数量。

o

bjval: 目标函数值。

part: 保存划分结果。

4. Demo

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

算例图示及文件格式代码 #include <metis.h>#include <vector>#include <iostream>#include <fstream>#include <string>#include <sstream>using namespace std;vector<idx_t> func(vector<idx_t> &xadj, vector<idx_t> &adjncy, vector<idx_t> &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<idx_t> 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<idx_t> xadj(0); vector<idx_t> adjncy(0); // 压缩图表示 vector<idx_t> 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<idx_t> part = func(xadj, adjncy, adjwgt, METIS_PartGraphRecursive); //vector<idx_t> 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/vs2019上测试,并上传至GitHub,将LearnMetis设为启动项目即可复现实验结果。

Reference

Win10 VS安装METIS

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

使用METIS软件包进行图划分

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

小切分节奏图示,五线谱大切分节奏求图 metis创始人,路由器安装教程