Boost 图形库和 LEMON

正如 Daniel 在他的综合回答中提到的那样，功能最全的通用 C++ 库是Boost Graph Library。有一个新的分布式内存扩展能够执行一些基本算法，例如广度优先和深度优先搜索、最小生成树和连接组件搜索，但我对新项目不是很熟悉。Boost Graph Library 本身享有盛誉，并在世界各地的许多项目中使用。

如果您正在做基本的 HPC 图工作，您可能希望从 Boost Graph Library 开始，但请注意，许多 HPC C++ 编译器在使用 Boost 时会遇到困难（尽管它相当严格地遵守 C++ 标准），您可能需要使用旧版本的 Boost 或非供应商编译器（如 GCC）使其在 HPC 系统上运行。

快速浏览 LEMON 的存储库表明 IBM BlueGene 超级计算团队参与其中，但我没有看到 MPI 的任何依赖项或配置，因此目前这可能只是一个串行图形库。

负载平衡和动态图（重新）分区

如果您对负载平衡和动态图分区感兴趣，您还有更多选择。也许最著名的库是ParMETIS，它去年更新到第 4 版。ParMETIS 具有基于顶点的权重，这对于多物理场仿真很重要。

ParMETIS 的欧洲竞争对手是PT-Scotch，它在某些类型的问题上具有更好的性能，但与 ParMETIS 类似，不经常更新。

您可能还对Zoltan感兴趣，它是用于 C++ 科学计算的桑迪亚国家实验室 Trilinos 元数据包的一部分。Zoltan 具有自己的分层分区器和与 ParMETIS 和 PT-Scotch 的接口。

Graph500

如果您正在研究并发搜索、优化（单源最短路径）和面向边缘（最大独立集）的前沿，您也会对免费提供的 Graph500 基准测试感兴趣。

也许，Boost Graph Library就是您正在寻找的。它有一个解析器来读取以 GraphViz 的 DOT 格式指定的图形。虽然我并不真正了解内存开销，但它确实提供了并行化的变体。

另一个图形库是LEMON，但我并不真正了解它，如果它支持并行化，它不会被宣传。它的网站给人留下了很好的印象；）

我还想提一下STINGER，一种为并行性设计的动态图数据结构。根据该网站，它旨在实现以下目标：

可移植性：为 STINGER 编写的算法可以很容易地在多种语言和框架之间进行翻译/移植

生产力：STINGER 应该提供一个通用的抽象数据结构，以便大型图社区可以快速利用彼此的研究进展。这在哲学上类似于数值算法社区隐式使用稀疏和密集矩阵。

性能：众所周知，没有一种数据结构对每个图算法都是最优的。STINGER 的目标是配置一个可以很好地运行大多数算法的合理数据结构。与跨广泛的典型图算法集的另一种通用数据结构相比，使用 STINGER 应该不会显着降低性能。STINGER 应假定共享内存地址空间，并允许顺序或并行算法。数据结构应该允许并行算法在可能的情况下利用并发性。

它不像 LEMON 或 Boost Graph Library 那样通用，并且处于开发的早期阶段。如果你检查出来，我会对你的评论感兴趣。