1.. Copyright (C) 2004-2009 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6=================================== 7|Logo| Parallel Boost Graph Library 8=================================== 9 10Overview 11-------- 12 13The Parallel Boost Graph Library is an extension to the `Boost Graph 14Library`_ (BGL) for parallel and distributed computing. It offers 15distributed graphs and graph algorithms to exploit coarse-grained 16parallelism along with parallel algorithms that exploit fine-grained 17parallelism, while retaining the same interfaces as the (sequential) 18BGL. Code written using the sequential BGL should be easy to 19parallelize with the parallel BGL. Visitors new to the Parallel BGL 20should read our `architectural overview`_. 21 221. `Process groups`_ 23 24 - `MPI process group`_ 25 - `Simple trigger interface`_ 26 272. Auxiliary data structures 28 29 - `Distributed queue`_ 30 - `Distributed property map`_ 31 323. Distributed graph concepts 33 34 - `Distributed Graph`_ 35 - `Distributed Vertex List Graph`_ 36 - `Distributed Edge List Graph`_ 37 - `Global Descriptor`_ 38 394. Graph data structures 40 41 - `Distributed adjacency list`_ 42 435. Graph adaptors 44 45 - `Local subgraph adaptor`_ 46 - `Vertex list graph adaptor`_ 47 486. Graph input/output 49 50 - Graphviz output 51 - `METIS input`_ 52 537. Synthetic data generators 54 55 - `R-MAT generator`_ 56 - `Sorted R-MAT generator`_ 57 - `Sorted unique R-MAT generator`_ 58 - `Unique R-MAT generator`_ 59 - `Scalable R-MAT generator`_ 60 - `Erdos-Renyi generator`_ 61 - `Sorted Erdos-Renyi generator`_ 62 - `Small world generator`_ 63 - `SSCA generator`_ 64 - `Mesh generator`_ 65 668. Algorithms 67 68 - Distributed algorithms 69 70 - `Breadth-first search`_ 71 - `Dijkstra's single-source shortest paths`_ 72 73 - `Eager Dijkstra shortest paths`_ 74 - `Crauser et al. Dijkstra shortest paths`_ 75 - `Delta-Stepping shortest paths`_ 76 77 - `Depth-first search`_ 78 - `Minimum spanning tree`_ 79 80 - `Boruvka's minimum spanning tree`_ 81 - `Merging local minimum spanning forests`_ 82 - `Boruvka-then-merge`_ 83 - `Boruvka-mixed-merge`_ 84 85 - Connected components 86 87 - `Connected components`_ 88 - `Connected components parallel search`_ 89 - `Strongly-connected components`_ 90 91 - PageRank_ 92 - `Boman et al. Graph coloring`_ 93 - `Fruchterman Reingold force-directed layout`_ 94 - `s-t connectivity`_ 95 - `Betweenness centrality`_ 96 - `Non-distributed betweenness centrality`_ 97 98---------------------------------------------------------------------------- 99 100Copyright (C) 2005-2009 The Trustees of Indiana University. 101 102Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine 103 104.. |Logo| image:: pbgl-logo.png 105 :align: middle 106 :alt: Parallel BGL 107 :target: http://www.osl.iu.edu/research/pbgl 108 109.. _Parallel Dijkstra example: dijkstra_example.html 110.. _Boost Graph Library: http://www.boost.org/libs/graph/doc 111.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html 112.. _local subgraph adaptor: local_subgraph.html 113.. _vertex list graph adaptor: vertex_list_adaptor.html 114.. _MPI: http://www-unix.mcs.anl.gov/mpi/ 115.. _generic programming: http://www.cs.rpi.edu/~musser/gp/ 116.. _development page: design/index.html 117.. _process groups: process_group.html 118.. _MPI process group: process_group.html 119.. _Simple trigger interface: simple_trigger.html 120.. _Open Systems Laboratory: http://www.osl.iu.edu 121.. _Indiana University: http://www.indiana.edu 122.. _Distributed adjacency list: distributed_adjacency_list.html 123.. _Distributed queue: distributed_queue.html 124.. _Distributed property map: distributed_property_map.html 125.. _R-MAT generator: rmat_generator.html 126.. _Sorted R-MAT generator: sorted_rmat_generator.html 127.. _Sorted Unique R-MAT generator: sorted_unique_rmat_generator.html 128.. _Unique R-MAT generator: unique_rmat_generator.html 129.. _Scalable R-MAT generator: scalable_rmat_generator.html 130.. _Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/erdos_renyi_generator.html 131.. _Sorted Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html 132.. _Small world generator: http://www.boost.org/libs/graph/doc/small_world_generator.html 133.. _SSCA generator: ssca_generator.html 134.. _Mesh generator: mesh_generator.html 135.. _Breadth-first search: breadth_first_search.html 136.. _Depth-first search: tsin_depth_first_visit.html 137.. _Dijkstra's single-source shortest paths: dijkstra_shortest_paths.html 138.. _Eager Dijkstra shortest paths: dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm 139.. _Crauser et al. Dijkstra shortest paths: dijkstra_shortest_paths.html#crauser-et-al-s-algorithm 140.. _Delta-Stepping shortest paths: dijkstra_shortest_paths.html#delta-stepping-algorithm 141.. _Minimum spanning tree: dehne_gotz_min_spanning_tree.html 142.. _Boruvka's minimum spanning tree: dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree 143.. _Merging local minimum spanning forests: dehne_gotz_min_spanning_tree.html#merge-local-minimum-spanning-trees 144.. _Boruvka-then-merge: dehne_gotz_min_spanning_tree.html#boruvka-then-merge 145.. _Boruvka-mixed-merge: dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge 146.. _PageRank: page_rank.html 147.. _Boman et al. Graph coloring: boman_et_al_graph_coloring.html 148.. _Connected components: connected_components.html 149.. _Connected components parallel search: connected_components_parallel_search.html 150.. _Strongly-connected components: strong_components.html 151.. _Distributed Graph: DistributedGraph.html 152.. _Distributed Vertex List Graph: DistributedVertexListGraph.html 153.. _Distributed Edge List Graph: DistributedEdgeListGraph.html 154.. _Global Descriptor: GlobalDescriptor.html 155.. _METIS Input: metis.html 156.. _architectural overview: overview.html 157.. _Fruchterman Reingold force-directed layout: fruchterman_reingold.html 158.. _s-t connectivity: st_connected.html 159.. _Betweenness centrality: betweenness_centrality.html 160.. _Non-distributed betweenness centrality: non_distributed_betweenness_centrality.html 161