Parallel Boost Graph Library

Overview

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. Visitors new to the Parallel BGL should read our architectural overview.

1. Process groups

• MPI process group
• Simple trigger interface

2. Auxiliary data structures

• Distributed queue
• Distributed property map

3. Distributed graph concepts

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

4. Graph data structures

• Distributed adjacency list

5. Graph adaptors

• Local subgraph adaptor
• Vertex list graph adaptor

6. Graph input/output

• Graphviz output
• METIS input

7. Synthetic data generators

• R-MAT generator
• Sorted R-MAT generator
• Sorted unique R-MAT generator
• Unique R-MAT generator
• Scalable R-MAT generator
• Erdos-Renyi generator
• Sorted Erdos-Renyi generator
• Small world generator
• SSCA generator
• Mesh generator

8. Algorithms

• Distributed algorithms
  • Breadth-first search
  • Dijkstra's single-source shortest paths
    • Eager Dijkstra shortest paths
    • Crauser et al. Dijkstra shortest paths
    • Delta-Stepping 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
    • Connected components parallel search
    • Strongly-connected components
  • PageRank
  • Boman et al. Graph coloring
  • Fruchterman Reingold force-directed layout
  • s-t connectivity
  • Betweenness centrality
  • Non-distributed betweenness centrality

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

Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine