并行 Boost 图形库

概述

并行 Boost 图形库是 Boost 图形库 (BGL) 的扩展，用于并行和分布式计算。它提供分布式图和图算法来利用粗粒度并行性，以及利用细粒度并行性的并行算法，同时保留与（顺序）BGL 相同的接口。使用顺序 BGL 编写的代码应该很容易使用并行 BGL 进行并行化。初次接触并行 BGL 的访问者应该阅读我们的架构概述。

1. 进程组

• MPI 进程组
• 简单触发器接口

2. 辅助数据结构

• 分布式队列
• 分布式属性映射

3. 分布式图概念

• 分布式图
• 分布式顶点列表图
• 分布式边列表图
• 全局描述符

4. 图数据结构

• 分布式邻接列表

5. 图适配器

• 局部子图适配器
• 顶点列表图适配器

6. 图输入/输出

• Graphviz 输出
• METIS 输入

7. 合成数据生成器

• R-MAT 生成器
• 排序的 R-MAT 生成器
• 排序的唯一 R-MAT 生成器
• 唯一 R-MAT 生成器
• 可扩展 R-MAT 生成器
• Erdos-Renyi 生成器
• 排序的 Erdos-Renyi 生成器
• 小世界生成器
• SSCA 生成器
• 网格生成器

8. 算法

• 分布式算法
  • 广度优先搜索
  • Dijkstra 的单源最短路径
    • 急切的 Dijkstra 最短路径
    • Crauser 等人的 Dijkstra 最短路径
    • Delta-Stepping 最短路径
  • 深度优先搜索
  • 最小生成树
    • Boruvka 的最小生成树
    • 合并局部最小生成森林
    • Boruvka-然后-合并
    • Boruvka-混合-合并
  • 连通分量
    • 连通分量
    • 连通分量并行搜索
    • 强连通分量
  • PageRank
  • Boman 等人的图着色
  • Fruchterman Reingold 力导向布局
  • s-t 连通性
  • 介数中心性
  • 非分布式介数中心性

版权所有 (C) 2005-2009 印第安纳大学托管委员会。

作者：Nick Edmonds、Douglas Gregor 和 Andrew Lumsdaine