Parallel Boost Graph Library

概述

Parallel Boost Graph Library 是 Boost Graph Library (BGL) 的扩展，用于并行和分布式计算。它提供分布式图和图算法来利用粗粒度并行性，以及利用细粒度并行性的并行算法，同时保留与（顺序）BGL 相同的接口。使用顺序 BGL 编写的代码应该很容易使用并行 BGL 进行并行化。首次接触 Parallel 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 单源最短路径
    • Eager Dijkstra 最短路径
    • Crauser et al. Dijkstra 最短路径
    • Delta-Stepping 最短路径
  • 深度优先搜索
  • 最小生成树
    • Boruvka 最小生成树
    • 合并本地最小生成森林
    • Boruvka-then-merge
    • Boruvka-mixed-merge
  • 连通分量
    • 连通分量
    • 连通分量并行搜索
    • 强连通分量
  • PageRank
  • Boman et al. 图着色
  • Fruchterman Reingold 力导向布局
  • s-t 连通性
  • 介数中心性
  • 非分布式介数中心性

版权 (C) 2005-2009 Indiana University 理事会。

作者：Nick Edmonds, Douglas Gregor, 和 Andrew Lumsdaine