简介

一种大规模图的融合算法，即：将一个大图融合成一个便于处理的小图。论文地址：http://glaros.dtc.umn.edu/gkhome/node/1186 ，使用python和graph-tool复现了论文的第四章算法。

和我可爱且聪明的师姐一起开发的(其余工作正在进行中，原仓库目前不便开源，所以这里没有显示她是贡献者)。她在双胞胎处理、亲戚节点处理、图融合上提出了关键性想法，使得程序圆满开发成功。

代码在Algorithm文件夹下，数据请自己下载并放到对应位置，太大了我就不传上来了。compare文件夹是和目前的第三方库进行的对比。

依赖

能将上万节点的图处理成如下所示的模样：

融合到100个节点：

融合到7个节点：

每一步融合都能打印点平衡率和边割率：

注：我们算法的目的是实现图融合，并打印点平衡率与边割率。而metis和pymetis的目的都是图划分，有一些差距在。

目前性能超过当前pip install metis后得到的第三方库的性能，对比详见：https://muyuuuu.github.io/2020/11/20/Metis/

与pip install pymetis后得到的第三方库性能还有一些差距，前路漫漫，还需努力。

开发详细流程、思想、数据结构的使用都放到博客里面了。开发程序的过程中，使用了大量数据结构的使用和程序的设计技巧，如桶排序、哈系、队列、列表、字典的花式操作来降低算法时间和空间复杂度。如果不是非要用Metis算法和抱着必死的决心一定要读懂代码，请谨慎观看博客和代码，直接调用即可。