ceph/src/boost/libs/graph_parallel/doc/index.rst

   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