]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
10 | Overview | |
11 | -------- | |
12 | ||
13 | The Parallel Boost Graph Library is an extension to the `Boost Graph | |
14 | Library`_ (BGL) for parallel and distributed computing. It offers | |
15 | distributed graphs and graph algorithms to exploit coarse-grained | |
16 | parallelism along with parallel algorithms that exploit fine-grained | |
17 | parallelism, while retaining the same interfaces as the (sequential) | |
18 | BGL. Code written using the sequential BGL should be easy to | |
19 | parallelize with the parallel BGL. Visitors new to the Parallel BGL | |
20 | should read our `architectural overview`_. | |
21 | ||
22 | 1. `Process groups`_ | |
23 | ||
24 | - `MPI process group`_ | |
25 | - `Simple trigger interface`_ | |
26 | ||
27 | 2. Auxiliary data structures | |
28 | ||
29 | - `Distributed queue`_ | |
30 | - `Distributed property map`_ | |
31 | ||
32 | 3. Distributed graph concepts | |
33 | ||
34 | - `Distributed Graph`_ | |
35 | - `Distributed Vertex List Graph`_ | |
36 | - `Distributed Edge List Graph`_ | |
37 | - `Global Descriptor`_ | |
38 | ||
39 | 4. Graph data structures | |
40 | ||
41 | - `Distributed adjacency list`_ | |
42 | ||
43 | 5. Graph adaptors | |
44 | ||
45 | - `Local subgraph adaptor`_ | |
46 | - `Vertex list graph adaptor`_ | |
47 | ||
48 | 6. Graph input/output | |
49 | ||
50 | - Graphviz output | |
51 | - `METIS input`_ | |
52 | ||
53 | 7. 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 | ||
66 | 8. 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 | ||
100 | Copyright (C) 2005-2009 The Trustees of Indiana University. | |
101 | ||
102 | Authors: 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 |