并行 Boost 图库

概述

并行 Boost 图库 (Parallel Boost Graph Library) 是 Boost 图库 (BGL) 在并行和分布式计算方面的扩展。它提供了分布式图和图算法，用于利用粗粒度并行性，以及利用细粒度并行的并行算法，同时保留了（顺序）BGL 的接口。使用顺序 BGL 编写的代码应该可以轻松地使用并行 BGL 进行并行化。对于不熟悉并行 Boost 图库的新用户，建议阅读我们的 架构概述。

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 等人的 Dijkstra 最短路径
    • Delta-Stepping 最短路径
  • 深度优先搜索
  • 最小生成树
    • Boruvka 最小生成树
    • 合并局部最小生成森林
    • Boruvka-then-merge (Boruvka 后合并)
    • Boruvka-mixed-merge (Boruvka 混合合并)
  • 连通分量
    • 连通分量
    • 连通分量并行搜索
    • 强连通分量
  • PageRank
  • Boman 等人的图着色
  • Fruchterman Reingold 力导向布局
  • s-t 连通性
  • 介数中心性
  • 非分布式介数中心性

Copyright (C) 2005-2009 The Trustees of Indiana University.

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