| .. Copyright (C) 2004-2009 The Trustees of Indiana University. |
| Use, modification and distribution is subject to the Boost Software |
| License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| |
| =================================== |
| |Logo| 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 |
| |
| .. |Logo| image:: pbgl-logo.png |
| :align: middle |
| :alt: Parallel BGL |
| :target: http://www.osl.iu.edu/research/pbgl |
| |
| .. _Parallel Dijkstra example: dijkstra_example.html |
| .. _Boost Graph Library: http://www.boost.org/libs/graph/doc |
| .. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html |
| .. _local subgraph adaptor: local_subgraph.html |
| .. _vertex list graph adaptor: vertex_list_adaptor.html |
| .. _MPI: http://www-unix.mcs.anl.gov/mpi/ |
| .. _generic programming: http://www.cs.rpi.edu/~musser/gp/ |
| .. _development page: design/index.html |
| .. _process groups: process_group.html |
| .. _MPI process group: process_group.html |
| .. _Simple trigger interface: simple_trigger.html |
| .. _Open Systems Laboratory: http://www.osl.iu.edu |
| .. _Indiana University: http://www.indiana.edu |
| .. _Distributed adjacency list: distributed_adjacency_list.html |
| .. _Distributed queue: distributed_queue.html |
| .. _Distributed property map: distributed_property_map.html |
| .. _R-MAT generator: rmat_generator.html |
| .. _Sorted R-MAT generator: sorted_rmat_generator.html |
| .. _Sorted Unique R-MAT generator: sorted_unique_rmat_generator.html |
| .. _Unique R-MAT generator: unique_rmat_generator.html |
| .. _Scalable R-MAT generator: scalable_rmat_generator.html |
| .. _Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/erdos_renyi_generator.html |
| .. _Sorted Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html |
| .. _Small world generator: http://www.boost.org/libs/graph/doc/small_world_generator.html |
| .. _SSCA generator: ssca_generator.html |
| .. _Mesh generator: mesh_generator.html |
| .. _Breadth-first search: breadth_first_search.html |
| .. _Depth-first search: tsin_depth_first_visit.html |
| .. _Dijkstra's single-source shortest paths: dijkstra_shortest_paths.html |
| .. _Eager Dijkstra shortest paths: dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm |
| .. _Crauser et al. Dijkstra shortest paths: dijkstra_shortest_paths.html#crauser-et-al-s-algorithm |
| .. _Delta-Stepping shortest paths: dijkstra_shortest_paths.html#delta-stepping-algorithm |
| .. _Minimum spanning tree: dehne_gotz_min_spanning_tree.html |
| .. _Boruvka's minimum spanning tree: dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree |
| .. _Merging local minimum spanning forests: dehne_gotz_min_spanning_tree.html#merge-local-minimum-spanning-trees |
| .. _Boruvka-then-merge: dehne_gotz_min_spanning_tree.html#boruvka-then-merge |
| .. _Boruvka-mixed-merge: dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge |
| .. _PageRank: page_rank.html |
| .. _Boman et al. Graph coloring: boman_et_al_graph_coloring.html |
| .. _Connected components: connected_components.html |
| .. _Connected components parallel search: connected_components_parallel_search.html |
| .. _Strongly-connected components: strong_components.html |
| .. _Distributed Graph: DistributedGraph.html |
| .. _Distributed Vertex List Graph: DistributedVertexListGraph.html |
| .. _Distributed Edge List Graph: DistributedEdgeListGraph.html |
| .. _Global Descriptor: GlobalDescriptor.html |
| .. _METIS Input: metis.html |
| .. _architectural overview: overview.html |
| .. _Fruchterman Reingold force-directed layout: fruchterman_reingold.html |
| .. _s-t connectivity: st_connected.html |
| .. _Betweenness centrality: betweenness_centrality.html |
| .. _Non-distributed betweenness centrality: non_distributed_betweenness_centrality.html |