Parallel Boost Graph Library

The Parallel Boost Graph Library is an extension to the Boost Graph Library (BGL) for parallel and distributed computing. It offers distributed graphs and graph algorithms to exploit coarse-grained parallelism along with parallel algorithms that exploit fine-grained parallelism, while retaining the same interfaces as the (sequential) BGL. Code written using the sequential BGL should be easy to parallelize with the parallel BGL.

1. Auxiliary data structures

• Distributed queue
• Distributed property map

3. Distributed graph concepts

• Distributed Graph
• Distributed Vertex List Graph
• Distributed Edge List Graph
• Global Descriptor

2. Graph data structures

• Distributed adjacency list

3. Graph adaptors

• Local subgraph adaptor
• Vertex list graph adaptor

4. Algorithms

• Distributed algorithms
  • Breadth-first search
  • Dijkstra's single-source shortest paths
    • Eager Dijkstra shortest paths
    • Crauser et al. Dijkstra shortest paths
  • Depth-first search
  • Minimum spanning tree
    • Boruvka's minimum spanning tree
    • Merging local minimum spanning forests
    • Boruvka-then-merge
    • Boruvka-mixed-merge
  • Connected components
    • Connected components
    • Strongly-connected components
  • PageRank
  • Boman et al. Graph coloring
• Parallel algorithms (undocumented, experimental)
  • Breadth-first search
  • Brandes' Betweenness Centrality algorithm

5. Parallel programming library

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine