这篇博客简要总结了我的 GSoC 2018 项目（并行图开发）以及取得的结果。有关详细说明，请参阅我的 GSoC 博客。

该项目分布在 LightGraphs 代码库中。它涉及

1. 生成关键图算法的并行实现。

2. 改进 LightGraphs 中关键图算法的顺序实现。

3. 实施启发式方法以获得关键 NP-Hard 图问题的良好解决方案。

基准测试是在使用 4 个内核的 64 位 Linux 机器上进行的。

基准图数据集

编号	图	顶点	边
1	推特社交圈	81,306	1,342,310
2	天体物理合作	17,903	197,031
3	Facebook 社交圈	4,039	88,234

这些图来自 SNAPDatasets 仓库。

使用 4 个内核的并行化加速

算法	推特	天体物理	Facebook
广度优先搜索	1.92	2.59	1.54
PageRank	1.77	1.54	1.65
Bellman Ford 单源最短路径	-	-	1.88
Floyd Warshall 全对最短路径	-	-	1.27
Johnson 全对最短路径	-	-	2.10
随机启发式	1.88	1.70	1.66
介数中心性	-	-	1.96
接近中心性	-	-	2.17
压力中心性	-	-	1.66

顺序优化加速

算法	推特	天体物理	Facebook
PageRank	3.05	3.37	3.17
Dijkstra 单源最短路径	2.80	2.10	1.68
Prim 最小生成树	7.65	4.25	4.05
Kruskal 最小生成树	7.70	3.37	2.80

广度优先搜索的绝对运行时间（毫秒）

算法	推特	天体物理	Facebook
并行	7.07	1.20	0.26
顺序	13.63	3.11	0.41

获取代码

本节列出了已实现的功能以及指向我 克隆的 LightGraphs 仓库 中相应分支的链接。

已完成并合并

以下分支已合并到 LightGraphs master 中

• 并行广度优先搜索

• Kruskal 最小生成树

• 顺序/并行 Johnson 全对最短路径

• 并行 Floyd Warshall 全对最短路径

• 并行 Bellman Ford 单源最短路径

• 并行 PageRank

• PageRank

• 负载均衡分区

• Prim 最小生成树

• Dijkstra 单源最短路径 I

• Dijkstra 单源最短路径 II

• 贪婪启发式

  1. 最小顶点覆盖

  2. 最小支配集

  3. 最大独立集

  4. 顶点连通性

• 并行随机启发式

• Karger 最小割

• 多线程中心性度量

  1. 介数中心性

  2. 接近中心性

  3. 压力中心性

已完成但不可用

以下分支未合并到 LightGraphs master 中，因为该功能不适合 LightGraphs

• 最小 Steiner 树

• 度量旅行商问题

需要改进

以下分支未合并到 LightGraphs 中，因为并行实现比顺序实现慢

• 并行 Kruskal 最小生成树

• 并行 Prim 最小生成树

• 并行 Dijkstra 单源最短路径

致谢

我要感谢我的导师 Divyansh Srivastava 和 LightGraphs 共同所有者 Seth Bromberger 在夏季审查我的代码并提供宝贵的建议。我还感谢 Julia 项目 和 NUMFocus 赞助我参加 JuliaCon 2018。