[boost-doc-zh] r350 committed - 升级至1.41.0,第二批,libs/目录下g-l子目录

  • From: boost-doc-zh@xxxxxxxxxxxxxx
  • To: boost-doc-zh-notify@xxxxxxxxxxxxx
  • Date: Sat, 28 Nov 2009 16:01:08 +0000

Revision: 350
Author: alai04
Date: Sat Nov 28 08:00:21 2009
Log: 升级至1.41.0,第二批,libs/目录下g-l子目录
http://code.google.com/p/boost-doc-zh/source/detail?r=350

Added:
 /trunk/libs/graph/doc/figs/grid_graph_indexed.png
 /trunk/libs/graph/doc/figs/grid_graph_unwrapped.png
 /trunk/libs/graph/doc/figs/grid_graph_wrapped.png
 /trunk/libs/graph/doc/grid_graph.html
 /trunk/libs/graph/example/grid_graph_example.cpp
 /trunk/libs/graph_parallel
 /trunk/libs/graph_parallel/doc
 /trunk/libs/graph_parallel/doc/architecture.png
 /trunk/libs/graph_parallel/doc/dijkstra_dist3_graph.png
 /trunk/libs/graph_parallel/doc/dijkstra_seq_graph.png
 /trunk/libs/graph_parallel/doc/dist-adjlist.png
 /trunk/libs/graph_parallel/doc/dist-pmap.png
 /trunk/libs/graph_parallel/doc/distributed-graph.png
 /trunk/libs/graph_parallel/doc/graph.png
 /trunk/libs/graph_parallel/doc/html
 /trunk/libs/graph_parallel/doc/html/DistributedEdgeListGraph.html
 /trunk/libs/graph_parallel/doc/html/DistributedGraph.html
 /trunk/libs/graph_parallel/doc/html/DistributedVertexListGraph.html
 /trunk/libs/graph_parallel/doc/html/GlobalDescriptor.html
 /trunk/libs/graph_parallel/doc/html/betweenness_centrality.html
 /trunk/libs/graph_parallel/doc/html/boman_et_al_graph_coloring.html
 /trunk/libs/graph_parallel/doc/html/breadth_first_search.html
/trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_9.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_9_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8_speedup_1.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8.png /trunk/libs/graph_parallel/doc/html/chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png
 /trunk/libs/graph_parallel/doc/html/connected_components.html
/trunk/libs/graph_parallel/doc/html/connected_components_parallel_search.html
 /trunk/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html
 /trunk/libs/graph_parallel/doc/html/dijkstra_example.html
 /trunk/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html
 /trunk/libs/graph_parallel/doc/html/distributedS.html
 /trunk/libs/graph_parallel/doc/html/distributed_adjacency_list.html
 /trunk/libs/graph_parallel/doc/html/distributed_property_map.html
 /trunk/libs/graph_parallel/doc/html/distributed_queue.html
 /trunk/libs/graph_parallel/doc/html/fruchterman_reingold.html
 /trunk/libs/graph_parallel/doc/html/index.html
 /trunk/libs/graph_parallel/doc/html/local_subgraph.html
 /trunk/libs/graph_parallel/doc/html/mesh_generator.html
 /trunk/libs/graph_parallel/doc/html/metis.html
 /trunk/libs/graph_parallel/doc/html/mpi_bsp_process_group.html
/trunk/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html
 /trunk/libs/graph_parallel/doc/html/overview.html
 /trunk/libs/graph_parallel/doc/html/page_rank.html
 /trunk/libs/graph_parallel/doc/html/pbgl-logo.png
 /trunk/libs/graph_parallel/doc/html/process_group.html
 /trunk/libs/graph_parallel/doc/html/rmat_generator.html
 /trunk/libs/graph_parallel/doc/html/scalable_rmat_generator.html
 /trunk/libs/graph_parallel/doc/html/simple_trigger.html
 /trunk/libs/graph_parallel/doc/html/sorted_rmat_generator.html
 /trunk/libs/graph_parallel/doc/html/sorted_unique_rmat_generator.html
 /trunk/libs/graph_parallel/doc/html/ssca_generator.html
 /trunk/libs/graph_parallel/doc/html/st_connected.html
 /trunk/libs/graph_parallel/doc/html/strong_components.html
 /trunk/libs/graph_parallel/doc/html/tsin_depth_first_visit.html
 /trunk/libs/graph_parallel/doc/html/unique_rmat_generator.html
 /trunk/libs/graph_parallel/doc/html/vertex_list_adaptor.html
 /trunk/libs/graph_parallel/doc/small_world_1_70_6_0p02.png
 /trunk/libs/graph_parallel/doc/vertex_coloring.png
 /trunk/libs/graph_parallel/index.html
 /trunk/libs/iostreams/doc/classes/grep_filter.html
Modified:
 /trunk/libs/graph/doc/IncidenceGraph.html
 /trunk/libs/graph/doc/compressed_sparse_row.html
 /trunk/libs/graph/doc/incremental_components.html
 /trunk/libs/graph/doc/quick_tour.html
 /trunk/libs/graph/doc/table_of_contents.html
 /trunk/libs/graph/example/Jamfile.v2
 /trunk/libs/graph/example/incremental-components-eg.cpp
 /trunk/libs/graph/example/incremental_components.cpp
 /trunk/libs/graph/example/incremental_components.expected
 /trunk/libs/graph/example/quick_tour.cpp
 /trunk/libs/iostreams/doc/bibliography.html
 /trunk/libs/iostreams/doc/classes/bzip2.html
 /trunk/libs/iostreams/doc/classes/regex_filter.html
 /trunk/libs/iostreams/doc/menu.html
 /trunk/libs/iostreams/doc/quick_reference.html

=======================================
--- /dev/null   
+++ /trunk/libs/graph/doc/figs/grid_graph_indexed.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph/doc/figs/grid_graph_unwrapped.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph/doc/figs/grid_graph_wrapped.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null
+++ /trunk/libs/graph/doc/grid_graph.html       Sat Nov 28 08:00:21 2009
@@ -0,0 +1,304 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
+<!--
+   Copyright &copy; 2009 Trustees of Indiana University
+
+   Distributed under 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)
+-->
+<html>
+  <head>
+    <title>Boost Graph Library: Grid Graph</title>
+    <style type="text/css">
+    <!--
+       body {
+        color: black;
+        background-color: white;
+      }
+
+      a {
+        color: blue;
+      }
+
+      a:visited {
+        color: #551A8B;
+      }
+
+      .code
+      {
+        border-left-style: groove;
+        border-left-width: 1px;
+        padding-left: 2em;
+      }
+
+    -->
+    </style>
+  </head>
+  <body>
+ <img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
+    <br />
+    <h1>
+      <tt>grid_graph</tt>
+    </h1>
+
+    <ul>
+      <li><a href="#overview">Overview</a></li>
+      <li><a href="#creating">Creating a Grid Graph</a></li>
+      <li><a href="#indexing">Indexing</a></li>
+      <li><a href="#member">Grid Graph Member Functions</a></li>
+    </ul>
+
+    <h3 id="overview">Overview</h3>
+    <p>
+      A <tt>grid_graph</tt> represents a multi-dimensional,
+      rectangular grid of vertices with user-defined dimension lengths
+      and wrapping.
+
+    </p>
+    <p>
+      <tt>grid_graph</tt> models:
+      <ul>
+        <li><a href="IncidenceGraph.html">Incidence Graph</a></li>
+        <li><a href="AdjacencyGraph.html">Adjacency Graph</a></li>
+        <li><a href="VertexListGraph.html">Vertex List Graph</a></li>
+        <li><a href="EdgeListGraph.html">Edge List Graph</a></li>
+        <li><a href="BidirectionalGraph.html">Bidirectional Graph</a></li>
+        <li><a href="AdjacencyMatrix.html">Adjacency Matrix</a></li>
+      </ul>
+    </p>
+    <p>
+      Defined in
+ <a href="../../../boost/graph/grid_graph.hpp"><tt>boost/graph/grid_graph.hpp</tt></a> + with all functions in the <tt>boost</tt> namespace. All examples are available in a single program file in <a href="../../../libs/graph/example/grid_graph_example.cpp"><tt>libs/graph/example/grid_graph_example.cpp</tt></a>
+    </p>
+
+    <h4>Template Parameters</h4>
+    <pre class="code">
+<span class="keyword">template</span> &lt;<span class="keyword">typename</span> <span class="name">std</span>::<span class="type">size_t</span> <span class="name">Dimensions</span>, + <span class="keyword">typename</span> <span class="name">VertexIndex</span> = <span class="name">std</span>::<span class="type">size_t</span>, + <span class="keyword">typename</span> <span class="name">EdgeIndex</span> = <span class="name">VertexIndex</span>&gt;
+  <span class="keyword">class</span> grid_graph;
+    </pre>
+    <ul>
+      <li>
+ <tt>Dimensions</tt> - Number of dimensions in the graph, <b>must be greater than 2</b>
+      </li>
+      <li>
+ <tt>VertexIndex</tt> - Type used for vertex indices, defaults to std::size_t
+      </li>
+      <li>
+ <tt>EdgeIndex</tt> - Type used for edge indices, defaults to the same type as VertexIndex
+      </li>
+    </ul>
+
+    <h3 id="creating">Creating a Grid Graph</h3>
+    <p>
+ The constructor to <tt>grid_graph</tt> has several overloads to aid in configuring each dimension:
+    </p>
+    <pre class="code">
+<span class="comment">// Defines a grid_graph that does not wrap.</span>
+<span class="type">grid_graph</span>&lt;...&gt;(<span class="name">boost</span>:<span class="type">array</span>&lt;<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>&gt; dimension_lengths);
+
+<span class="comment">// Defines a grid_graph where all dimensions are either wrapped or unwrapped.</span> +<span class="type">grid_graph</span>&lt;...&gt;(<span class="name">boost</span>:<span class="type">array</span>&lt;<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>&gt; dimension_lengths,
+                <span class="keyword">bool</span> wrap_all_dimensions);
+
+<span class="comment">// Defines a grid_graph where the wrapping for each dimension is specified individually.</span> +<span class="type">grid_graph</span>&lt;...&gt;(<span class="name">boost</span>:<span class="type">array</span>&lt;<span class="name">VertexIndex</span>, <span class="name">Dimensions</span>&gt; dimension_lengths, + <span class="name">boost</span>:<span class="type">array</span>&lt;<span class="keyword">bool</span>, <span class="name">Dimensions</span>&gt; wrap_dimension);
+    </pre>
+
+    <h4>Example</h4>
+    <pre class="code">
+<span class="comment">// Define dimension lengths, a 3x3 in this case</span> +<span class="name">boost</span>::<span class="type">array</span>&lt;<span class="keyword">int</span>, <span class="literal">2</span>&gt; lengths = { { <span class="literal">3</span>, <span class="literal">3</span> } };
+
+<span class="comment">// Create a 3x3 two-dimensional, unwrapped grid graph (Figure 1)</span> +<span class="type">grid_graph</span>&lt;<span class="literal">2</span>&gt; graph(lengths);
+
+<span class="comment">// Create a 3x3 two-dimensional, wrapped grid graph (Figure 2)</span> +<span class="type">grid_graph</span>&lt;<span class="literal">2</span>&gt; graph(lengths, <span class="keyword">true</span>);
+
+    </pre>
+    <p style="margin-left: 10px;">
+      <img src="figs/grid_graph_unwrapped.png" />
+      <br />
+ <em style="font-size: 0.8em"><b>Figure 1:</b> A 3x3 two-dimensional, unwrapped grid graph</em>
+    </p>
+    <br />
+    <p style="margin-left: 10px;">
+      <img src="figs/grid_graph_wrapped.png" />
+      <br />
+ <em style="font-size: 0.8em"><b>Figure 2:</b> A 3x3 two-dimensional, wrapped grid graph</em>
+    </p>
+    <br />
+
+    <h3 id="indexing">Indexing</h3>
+    <p>
+      The <tt>grid_graph</tt> supports addressing vertices and edges
+      by index. The following functions allow you to convert between
+      vertices, edges, and their associated indices:
+    </p>
+
+    <pre class="code">
+<span class="keyword">typedef</span> <span class="type">grid_graph</span>&lt;...&gt; <span class="name">Graph</span>; +<span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <span class="name">Traits</span>;
+
+<span class="comment">// Get the vertex associated with vertex_index</span>
+<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> +vertex(<span class="name">Traits</span>::<span class="type">vertices_size_type</span> vertex_index, + <span class="keyword">const</span> <span class="name">Graph&amp;</span> graph);
+
+<span class="comment">// Get the index associated with vertex</span>
+<span class="name">Traits</span>::<span class="type">vertices_size_type</span> +get(<span class="name">boost</span>::<span class="type">vertex_index_t</span>, + <span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, + <span class="keyword">const</span> <span class="name">Graph&amp;</span> graph);
+
+<span class="comment">// Get the edge associated with edge_index</span>
+<span class="name">Traits</span>::<span class="type">edge_descriptor</span>
+edge_at(<span class="name">Traits</span>::<span class="type">edges_size_type</span> edge_index, + <span class="keyword">const</span> <span class="name">Graph&amp;</span> graph);
+
+<span class="comment">// Get the index associated with edge</span>
+<span class="name">Traits</span>::<span class="type">edges_size_type</span>
+get(<span class="name">boost</span>::<span class="type">edge_index_t</span>, + <span class="name">Traits</span>::<span class="type">edge_descriptor</span> edge, + <span class="keyword">const</span> <span class="name">Graph&amp;</span> graph);
+
+<span class="comment">// Get the out-edge associated with vertex and out_edge_index</span>
+<span class="name">Traits</span>::<span class="type">edge_descriptor</span>
+out_edge_at(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, + <span class="name">Traits</span>::<span class="type">degree_size_type</span> out_edge_index, + <span class="keyword">const</span> <span class="name">Graph&amp;</span> graph);
+
+<span class="comment">// Get the out-edge associated with vertex and in_edge_index</span>
+<span class="name">Traits</span>::<span class="type">edge_descriptor</span>
+in_edge_at(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, + <span class="name">Traits</span>::<span class="type">degree_size_type</span> in_edge_index, + <span class="keyword">const</span> <span class="name">Graph&amp;</span> graph);
+    </pre>
+
+    <h4>Example</h4>
+    <pre class="code">
+<span class="keyword">typedef</span> <span class="type">grid_graph</span>&lt;2&gt; <span class="name">Graph</span>; +<span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <span class="name">Traits</span>;
+
+<span class="comment">// Create a 3x3, unwrapped grid_graph (Figure 3)</span> +<span class="name">boost</span>::<span class="type">array</span>&lt;<span class="keyword">int</span>, <span class="literal">2</span>&gt; lengths = { { <span class="literal">3</span>, <span class="literal">3</span> } };
+<span class="name">Graph</span> graph(lengths);
+
+<span class="comment">// Do a round-trip test of the vertex index functions</span> +<span class="keyword">for</span> (<span class="name">Traits</span>::<span class="type">vertices_size_type</span> v_index = <span class="literal">0</span>;
+     v_index < num_vertices(graph); ++v_index) {
+
+  <span class="comment">// The two indices should always be equal</span>
+ <span class="name">std</span>::cout &lt;&lt; <span class="literal">&quot;Index of vertex &quot;</span> &lt;&lt; v_index &lt;&lt; <span class="literal">&quot; is &quot;</span> &lt;&lt; + get(<span class="name">boost</span>::vertex_index, graph, vertex(v_index, graph)) &lt;&lt; <span class="name">std</span>::endl;
+
+}
+
+<span class="comment">// Do a round-trip test of the edge index functions</span> +<span class="keyword">for</span> (<span class="name">Traits</span>::<span class="type">edges_size_type</span> e_index = <span class="literal">0</span>;
+     e_index < num_edges(graph); ++e_index) {
+
+  <span class="comment">// The two indices should always be equal</span>
+ <span class="name">std</span>::cout &lt;&lt; <span class="literal">&quot;Index of edge &quot;</span> &lt;&lt; e_index &lt;&lt; <span class="literal">&quot; is &quot;</span> &lt;&lt; + get(<span class="name">boost</span>::edge_index, graph, edge_at(e_index, graph)) &lt;&lt; <span class="name">std</span>::endl;
+
+}
+    </pre>
+
+    <p style="margin-left: 10px;">
+      <img src="figs/grid_graph_indexed.png" />
+      <br />
+ <em style="font-size: 0.8em"><b>Figure 3:</b> 3x3 unwrapped grid_graph with vertex and edge indices shown.</em>
+    </p>
+    <br />
+
+    <h3 id="member">Member Functions</h3>
+    <p>
+ There are several <tt>grid_graph</tt> specific member functions available:
+    </p>
+    <pre class="code">
+<span class="keyword">typedef</span> <span class="type">grid_graph</span>&lt;...&gt; <span class="name">Graph</span>; +<span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <span class="name">Traits</span>;
+
+<span class="comment">// Returns the number of dimensions</span>
+<span class="name">std</span>::<span class="type">size_t</span> dimensions();
+
+<span class="comment">// Returns the length of a dimension</span>
+<span class="name">Traits</span>::<span class="type">vertices_size_type</span> length(<span class="name">std</span>::<span class="type">size_t</span> dimension);
+
+<span class="comment">// Returns true if the dimension wraps, false if not</span> +<span class="keyword">bool</span> wrapped(<span class="name">std</span>::<span class="type">size_t</span> dimension);
+
+<span class="comment">// Returns the &quot;next&quot; vertex in a dimension at a given distance. If the dimension
+// is unwrapped, next will stop at the last vertex in the dimension.
+</span><span class="name">Traits</span>::<span class="type">vertex_descriptor</span> next(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, + <span class="name">std</span>::<span class="type">size_t</span> dimension, + <span class="name">Traits</span>::<span class="type">vertices_size_type</span> distance = <span class="literal">1</span>);
+
+<span class="comment">// Returns the &quot;previous&quot; vertex in a dimension at a given distance. If the +// dimension is unwrapped, previous will stop at the beginning vertex in the dimension. +</span><span class="name">Traits</span>::<span class="type">vertex_descriptor</span> previous(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex, + <span class="name">std</span>::<span class="type">size_t</span> dimension, + <span class="name">Traits</span>::<span class="type">vertices_size_type</span> distance = <span class="literal">1</span>);
+    </pre>
+
+    <h4>Example</h4>
+    <pre class="code">
+<span class="keyword">typedef</span> <span class="type">grid_graph</span>&lt;<span class="literal">3</span>&gt; <span class="name">Graph</span>; +<span class="keyword">typedef</span> <span class="type">graph_traits</span>&lt;<span class="name">Graph</span>&gt; <span class="name">Traits</span>;
+
+<span class="comment">// Define a 3x5x7 grid_graph where the second dimension doesn&apos;t wrap</span> +<span class="name">boost</span>::<span class="type">array</span>&lt;<span class="name">std</span>::<span class="type">size_t</span>, <span class="literal">3</span>&gt; lengths = { { <span class="literal">3</span>, <span class="literal">5</span>, <span class="literal">7</span> } }; +<span class="name">boost</span>::<span class="type">array</span>&lt;<span class="keyword">bool</span>, <span class="literal">3</span>&gt; wrapped = { { <span class="keyword">true</span>, <span class="keyword">false</span>, <span class="keyword">true</span> } };
+<span class="name">Graph</span> graph(lengths, wrapped);
+
+<span class="comment">// Print number of dimensions</span>
+<span class="name">std</span>::cout &lt;&lt; graph.dimensions() &lt;&lt; <span class="name">std</span>::endl; <span class="comment">// prints &quot;3&quot;</span>
+
+<span class="comment">// Print dimension lengths (same order as in the lengths array)</span> +<span class="name">std</span>::cout &lt;&lt; graph.length(<span class="literal">0</span>) &lt;&lt; <span class="literal">&quot;x&quot;</span> &lt;&lt; graph.length(<span class="literal">1</span>) << + <span class="literal">&quot;x&quot;</span> &lt;&lt; graph.length(<span class="literal">2</span>) &lt;&lt; <span class="name">std</span>::endl; <span class="comment">// prints &quot;3x5x7&quot;</span>
+
+<span class="comment">// Print dimension wrapping (W = wrapped, U = unwrapped)</span> +<span class="name">std</span>::cout &lt;&lt; graph.wrapped(<span class="literal">0</span>) ? <span class="literal">&quot;W&quot;</span> : <span class="literal">&quot;U&quot;</span> &lt;&lt; <span class="literal">&quot;, &quot;</span> << + graph.wrapped(<span class="literal">1</span>) ? <span class="literal">&quot;W&quot;</span> : <span class="literal">&quot;U&quot;</span> &lt;&lt; <span class="literal">&quot;, &quot;</span> << + graph.wrapped(<span class="literal">2</span>) ? <span class="literal">&quot;W&quot;</span> : <span class="literal">&quot;U&quot;</span> &lt;&lt; <span class="name">std</span>::endl; <span class="comment">// prints &quot;W, U, W&quot;</span>
+
+<span class="comment">// Define a simple function to print vertices</span>
+<span class="keyword">void</span> print_vertex(<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> vertex_to_print) { + <span class="name">std</span>::cout &lt;&lt; <span class="literal">&quot;(&quot;</span> &lt;&lt; vertex_to_print[<span class="literal">0</span>] &lt;&lt; <span class="literal">&quot;, &quot;</span> &lt;&lt; vertex_to_print[<span class="literal">1</span>] << + <span class="literal">&quot;, &quot;</span> &lt;&lt; vertex_to_print[<span class="literal">2</span>] &lt;&lt; <span class="literal">&quot;)&quot;</span> &lt;&lt; <span class="name">std</span>::endl;
+}
+
+<span class="comment">// Start with the first vertex in the graph</span>
+<span class="name">Traits</span>::<span class="type">vertex_descriptor</span> first_vertex = vertex(<span class="literal">0</span>, graph); +print_vertex(first_vertex); <span class="comment">// prints &quot;(0, 0, 0)&quot;</span>
+
+<span class="comment">// Print the next vertex in dimension 0</span>
+print_vertex(graph.next(first_vertex, <span class="literal">0</span>)); <span class="comment">// prints &quot;(1, 0, 0)&quot;</span>
+
+<span class="comment">// Print the next vertex in dimension 1</span>
+print_vertex(graph.next(first_vertex, <span class="literal">1</span>)); <span class="comment">// prints &quot;(0, 1, 0)&quot;</span>
+
+<span class="comment">// Print the 5th next vertex in dimension 2</span>
+print_vertex(graph.next(first_vertex, <span class="literal">2</span>, <span class="literal">5</span>)); <span class="comment">// prints &quot;(0, 0, 5)&quot;</span>
+
+<span class="comment">// Print the previous vertex in dimension 0 (wraps)</span> +print_vertex(graph.previous(first_vertex, <span class="literal">0</span>)); <span class="comment">// prints &quot;(2, 0, 0)&quot;</span>
+
+<span class="comment">// Print the previous vertex in dimension 1 (doesn&apos;t wrap, so it&apos;s the same)</span> +print_vertex(graph.previous(first_vertex, <span class="literal">1</span>)); <span class="comment">// prints &quot;(0, 0, 0)&quot;</span>
+
+<span class="comment">// Print the 20th previous vertex in dimension 2 (wraps around twice)</span> +print_vertex(graph.previous(first_vertex, <span class="literal">2</span>, <span class="literal">20</span>)); <span class="comment">// prints &quot;(0, 0, 1)&quot;</span>
+    </pre>
+
+    <hr />
+    Copyright &copy; 2009 Trustees of Indiana University
+
+  </body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph/example/grid_graph_example.cpp Sat Nov 28 08:00:21 2009
@@ -0,0 +1,86 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen, Andrew Lumsdaine
+//
+// Distributed under 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)
+//=======================================================================
+
+#include <iostream>
+#include <boost/array.hpp>
+#include <boost/graph/grid_graph.hpp>
+
+#define DIMENSIONS 3
+using namespace boost;
+
+typedef grid_graph<DIMENSIONS> Graph;
+typedef graph_traits<Graph> Traits;
+
+// Define a simple function to print vertices
+void print_vertex(Traits::vertex_descriptor vertex_to_print) {
+  std::cout << "(" << vertex_to_print[0] << ", " << vertex_to_print[1] <<
+    ", " << vertex_to_print[2] << ")" << std::endl;
+}
+
+int main(int argc, char* argv[]) {
+
+  // Define a 3x5x7 grid_graph where the second dimension doesn't wrap
+  boost::array<std::size_t, 3> lengths = { { 3, 5, 7 } };
+  boost::array<bool, 3> wrapped = { { true, false, true } };
+  Graph graph(lengths, wrapped);
+
+  // Do a round-trip test of the vertex index functions
+  for (Traits::vertices_size_type v_index = 0;
+       v_index < num_vertices(graph); ++v_index) {
+
+    // The two indicies should always be equal
+    std::cout << "Index of vertex " << v_index << " is " <<
+      get(boost::vertex_index, graph, vertex(v_index, graph)) << std::endl;
+
+  }
+
+  // Do a round-trip test of the edge index functions
+  for (Traits::edges_size_type e_index = 0;
+       e_index < num_edges(graph); ++e_index) {
+
+    // The two indicies should always be equal
+    std::cout << "Index of edge " << e_index << " is " <<
+      get(boost::edge_index, graph, edge_at(e_index, graph)) << std::endl;
+
+  }
+
+  // Print number of dimensions
+  std::cout << graph.dimensions() << std::endl; // prints "3"
+
+  // Print dimension lengths (same order as in the lengths array)
+  std::cout << graph.length(0) << "x" << graph.length(1) <<
+    "x" << graph.length(2) << std::endl; // prints "3x5x7"
+
+  // Print dimension wrapping (W = wrapped, U = unwrapped)
+  std::cout << (graph.wrapped(0) ? "W" : "U") << ", " <<
+    (graph.wrapped(1) ? "W" : "U") << ", " <<
+    (graph.wrapped(2) ? "W" : "U") << std::endl; // prints "W, U, W"
+
+  // Start with the first vertex in the graph
+  Traits::vertex_descriptor first_vertex = vertex(0, graph);
+  print_vertex(first_vertex); // prints "(0, 0, 0)"
+
+  // Print the next vertex in dimension 0
+  print_vertex(graph.next(first_vertex, 0)); // prints "(1, 0, 0)"
+
+  // Print the next vertex in dimension 1
+  print_vertex(graph.next(first_vertex, 1)); // prints "(0, 1, 0)"
+
+  // Print the 5th next vertex in dimension 2
+  print_vertex(graph.next(first_vertex, 2, 5)); // prints "(0, 0, 4)"
+
+  // Print the previous vertex in dimension 0 (wraps)
+  print_vertex(graph.previous(first_vertex, 0)); // prints "(2, 0, 0)"
+
+ // Print the previous vertex in dimension 1 (doesn't wrap, so it's the same)
+  print_vertex(graph.previous(first_vertex, 1)); // prints "(0, 0, 0)"
+
+  // Print the 20th previous vertex in dimension 2 (wraps around twice)
+  print_vertex(graph.previous(first_vertex, 2, 20)); // prints "(0, 0, ?)"
+}
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/architecture.png     Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/dijkstra_dist3_graph.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/dijkstra_seq_graph.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/dist-adjlist.png     Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/dist-pmap.png        Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/distributed-graph.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/graph.png    Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/DistributedEdgeListGraph.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,141 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Concept Distributed Edge List Graph</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-concept-distributed-edge-list-graph">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Concept Distributed Edge List Graph</h1>
+
+<!-- Copyright (C) 2004-2008 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) -->
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#description" id="id1">Description</a></li> +<li><a class="reference internal" href="#notation" id="id2">Notation</a></li> +<li><a class="reference internal" href="#refinement-of" id="id3">Refinement of</a></li> +<li><a class="reference internal" href="#associated-types" id="id4">Associated types</a></li> +<li><a class="reference internal" href="#valid-expressions" id="id5">Valid Expressions</a></li>
+<li><a class="reference internal" href="#models" id="id6">Models</a></li>
+</ul>
+</div>
+<div class="section" id="description">
+<h1><a class="toc-backref" href="#id1">Description</a></h1>
+<p>A Distributed Edge List Graph is a graph whose vertices are
+distributed across multiple processes or address spaces. The
+<tt class="docutils literal"><span class="pre">vertices</span></tt> and <tt class="docutils literal"><span class="pre">num_vertices</span></tt> functions retain the same +signatures as in the <a class="reference external" href="http://www.boost.org/libs/graph/doc/EdgeListGraph.html";>Edge List Graph</a> concept, but return only
+the local set (and size of the local set) of vertices.</p>
+</div>
+<div class="section" id="notation">
+<h1><a class="toc-backref" href="#id2">Notation</a></h1>
+<dl class="docutils">
+<dt>G</dt>
+<dd>A type that models the Distributed Edge List Graph concept.</dd>
+<dt>g</dt>
+<dd>An object of type <tt class="docutils literal"><span class="pre">G</span></tt>.</dd>
+</dl>
+</div>
+<div class="section" id="refinement-of">
+<h1><a class="toc-backref" href="#id3">Refinement of</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="http://www.boost.org/libs/graph/doc/Graph.html";>Graph</a></li>
+</ul>
+</blockquote>
+</div>
+<div class="section" id="associated-types">
+<h1><a class="toc-backref" href="#id4">Associated types</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="18%" />
+<col width="44%" />
+<col width="38%" />
+</colgroup>
+<tbody valign="top">
+<tr><td>Edge
+descriptor type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::edge_descriptor</span></tt></td>
+<td>Must model the
+<a class="reference external" href="GlobalDescriptor.html">Global Descriptor</a> concept.</td>
+</tr>
+<tr><td>Edge iterator
+type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::edge_iterator</span></tt></td>
+<td>Iterates over edges stored
+locally. The value type must be
+<tt class="docutils literal"><span class="pre">edge_descriptor</span></tt>.</td>
+</tr>
+<tr><td>Edges size
+type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::edges_size_type</span></tt></td>
+<td>The unsigned integral type used
+to store the number of edges
+in the local subgraph.</td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="section" id="valid-expressions">
+<h1><a class="toc-backref" href="#id5">Valid Expressions</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="17%" />
+<col width="22%" />
+<col width="23%" />
+<col width="39%" />
+</colgroup>
+<thead valign="bottom">
+<tr><th class="head">Name</th>
+<th class="head">Expression</th>
+<th class="head">Type</th>
+<th class="head">Semantics</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr><td>Local edge set</td>
+<td><tt class="docutils literal"><span class="pre">edges(g)</span></tt></td> +<td><tt class="docutils literal"><span class="pre">std::pair&lt;</span></tt>
+<tt class="docutils literal"><span class="pre">edge_iterator,</span></tt>
+<tt class="docutils literal"><span class="pre">edge_iterator&gt;</span></tt></td>
+<td>Returns an iterator range
+providing access to the local
+edges in the graph.</td>
+</tr>
+<tr><td>Number of local
+edges.</td>
+<td><tt class="docutils literal"><span class="pre">num_edges(g)</span></tt></td> +<td><tt class="docutils literal"><span class="pre">edges_size_type</span></tt></td>
+<td>Returns the number of edges
+stored locally in the graph.</td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="section" id="models">
+<h1><a class="toc-backref" href="#id6">Models</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="distributed_adjacency_list.html">Distributed adjacency list</a></li>
+</ul>
+</blockquote>
+<hr class="docutils" />
+<p>Copyright (C) 2005 The Trustees of Indiana University.</p>
+<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:21 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/DistributedGraph.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,93 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Concept Distributed Graph</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-concept-distributed-graph">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Concept Distributed Graph</h1>
+
+<!-- Copyright (C) 2004-2008 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) -->
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#description" id="id1">Description</a></li> +<li><a class="reference internal" href="#notation" id="id2">Notation</a></li> +<li><a class="reference internal" href="#refinement-of" id="id3">Refinement of</a></li> +<li><a class="reference internal" href="#associated-types" id="id4">Associated types</a></li>
+<li><a class="reference internal" href="#models" id="id5">Models</a></li>
+</ul>
+</div>
+<div class="section" id="description">
+<h1><a class="toc-backref" href="#id1">Description</a></h1>
+<p>A Distributed Graph is a graph whose vertices or edges are
+distributed across multiple processes or address spaces. The
+descriptors of a Distributed Graph must model the <a class="reference external" href="GlobalDescriptor.html">Global
+Descriptor</a> concept.</p>
+</div>
+<div class="section" id="notation">
+<h1><a class="toc-backref" href="#id2">Notation</a></h1>
+<dl class="docutils">
+<dt>G</dt>
+<dd>A type that models the Distributed Graph concept.</dd>
+</dl>
+</div>
+<div class="section" id="refinement-of">
+<h1><a class="toc-backref" href="#id3">Refinement of</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="http://www.boost.org/libs/graph/doc/Graph.html";>Graph</a></li>
+</ul>
+</blockquote>
+</div>
+<div class="section" id="associated-types">
+<h1><a class="toc-backref" href="#id4">Associated types</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="18%" />
+<col width="44%" />
+<col width="38%" />
+</colgroup>
+<tbody valign="top">
+<tr><td>Vertex
+descriptor type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::vertex_descriptor</span></tt></td>
+<td>Must model the
+<a class="reference external" href="GlobalDescriptor.html">Global Descriptor</a> concept.</td>
+</tr>
+<tr><td>Edge
+descriptor type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::edge_descriptor</span></tt></td>
+<td>Must model the
+<a class="reference external" href="GlobalDescriptor.html">Global Descriptor</a> concept.</td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="section" id="models">
+<h1><a class="toc-backref" href="#id5">Models</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="distributed_adjacency_list.html">Distributed adjacency list</a></li>
+</ul>
+</blockquote>
+<hr class="docutils" />
+<p>Copyright (C) 2005 The Trustees of Indiana University.</p>
+<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:22 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/DistributedVertexListGraph.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,141 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Concept Distributed Vertex List Graph</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-concept-distributed-vertex-list-graph">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Concept Distributed Vertex List Graph</h1>
+
+<!-- Copyright (C) 2004-2008 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) -->
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#description" id="id1">Description</a></li> +<li><a class="reference internal" href="#notation" id="id2">Notation</a></li> +<li><a class="reference internal" href="#refinement-of" id="id3">Refinement of</a></li> +<li><a class="reference internal" href="#associated-types" id="id4">Associated types</a></li> +<li><a class="reference internal" href="#valid-expressions" id="id5">Valid Expressions</a></li>
+<li><a class="reference internal" href="#models" id="id6">Models</a></li>
+</ul>
+</div>
+<div class="section" id="description">
+<h1><a class="toc-backref" href="#id1">Description</a></h1>
+<p>A Distributed Vertex List Graph is a graph whose vertices are
+distributed across multiple processes or address spaces. The
+<tt class="docutils literal"><span class="pre">vertices</span></tt> and <tt class="docutils literal"><span class="pre">num_vertices</span></tt> functions retain the same +signatures as in the <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html";>Vertex List Graph</a> concept, but return only
+the local set (and size of the local set) of vertices.</p>
+</div>
+<div class="section" id="notation">
+<h1><a class="toc-backref" href="#id2">Notation</a></h1>
+<dl class="docutils">
+<dt>G</dt>
+<dd>A type that models the Distributed Vertex List Graph concept.</dd>
+<dt>g</dt>
+<dd>An object of type <tt class="docutils literal"><span class="pre">G</span></tt>.</dd>
+</dl>
+</div>
+<div class="section" id="refinement-of">
+<h1><a class="toc-backref" href="#id3">Refinement of</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="http://www.boost.org/libs/graph/doc/Graph.html";>Graph</a></li>
+</ul>
+</blockquote>
+</div>
+<div class="section" id="associated-types">
+<h1><a class="toc-backref" href="#id4">Associated types</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="18%" />
+<col width="44%" />
+<col width="38%" />
+</colgroup>
+<tbody valign="top">
+<tr><td>Vertex
+descriptor type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::vertex_descriptor</span></tt></td>
+<td>Must model the
+<a class="reference external" href="GlobalDescriptor.html">Global Descriptor</a> concept.</td>
+</tr>
+<tr><td>Vertex iterator
+type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::vertex_iterator</span></tt></td>
+<td>Iterates over vertices stored
+locally. The value type must be
+<tt class="docutils literal"><span class="pre">vertex_descriptor</span></tt>.</td>
+</tr>
+<tr><td>Vertices size
+type</td>
+<td><tt class="docutils literal"><span class="pre">graph_traits&lt;G&gt;::vertices_size_type</span></tt></td>
+<td>The unsigned integral type used
+to store the number of vertices
+in the local subgraph.</td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="section" id="valid-expressions">
+<h1><a class="toc-backref" href="#id5">Valid Expressions</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="17%" />
+<col width="22%" />
+<col width="23%" />
+<col width="39%" />
+</colgroup>
+<thead valign="bottom">
+<tr><th class="head">Name</th>
+<th class="head">Expression</th>
+<th class="head">Type</th>
+<th class="head">Semantics</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr><td>Local vertex set</td>
+<td><tt class="docutils literal"><span class="pre">vertices(g)</span></tt></td> +<td><tt class="docutils literal"><span class="pre">std::pair&lt;</span></tt>
+<tt class="docutils literal"><span class="pre">vertex_iterator,</span></tt>
+<tt class="docutils literal"><span class="pre">vertex_iterator&gt;</span></tt></td>
+<td>Returns an iterator range
+providing access to the local
+vertices in the graph.</td>
+</tr>
+<tr><td>Number of local
+vertices.</td>
+<td><tt class="docutils literal"><span class="pre">num_vertices(g)</span></tt></td> +<td><tt class="docutils literal"><span class="pre">vertices_size_type</span></tt></td>
+<td>Returns the number of vertices
+stored locally in the graph.</td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="section" id="models">
+<h1><a class="toc-backref" href="#id6">Models</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="distributed_adjacency_list.html">Distributed adjacency list</a></li>
+</ul>
+</blockquote>
+<hr class="docutils" />
+<p>Copyright (C) 2005 The Trustees of Indiana University.</p>
+<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:21 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/GlobalDescriptor.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,123 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Concept Global Descriptor</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-concept-global-descriptor">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Concept Global Descriptor</h1>
+
+<!-- Copyright (C) 2004-2008 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) -->
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#description" id="id1">Description</a></li> +<li><a class="reference internal" href="#refinement-of" id="id2">Refinement of</a></li> +<li><a class="reference internal" href="#notation" id="id3">Notation</a></li> +<li><a class="reference internal" href="#associated-types" id="id4">Associated types</a></li> +<li><a class="reference internal" href="#valid-expressions" id="id5">Valid Expressions</a></li>
+</ul>
+</div>
+<div class="section" id="description">
+<h1><a class="toc-backref" href="#id1">Description</a></h1>
+<p>A global descriptor is an object that represents an entity that is
+owned by some process and may reside in an address space not
+accessible to the currently-executing process. The global descriptor
+consists of two parts: the <em>owner</em> of the entity, which is the
+identifier of that process in which the entity resides, and a <em>local
+descriptor</em>, that uniquely identifies the entity with the address
+space of the owner.</p>
+</div>
+<div class="section" id="refinement-of">
+<h1><a class="toc-backref" href="#id2">Refinement of</a></h1>
+<blockquote>
+<ul class="simple">
+<li><a class="reference external" href="http://www.sgi.com/tech/stl/DefaultConstructible.html";>Default Constructible</a></li> +<li><a class="reference external" href="http://www.sgi.com/tech/stl/Assignable.html";>Assignable</a></li>
+</ul>
+</blockquote>
+</div>
+<div class="section" id="notation">
+<h1><a class="toc-backref" href="#id3">Notation</a></h1>
+<dl class="docutils">
+<dt>X</dt>
+<dd>A type that models the Global Descriptor concept.</dd>
+<dt>x</dt>
+<dd>Object of type X</dd>
+</dl>
+</div>
+<div class="section" id="associated-types">
+<h1><a class="toc-backref" href="#id4">Associated types</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="23%" />
+<col width="29%" />
+<col width="48%" />
+</colgroup>
+<tbody valign="top">
+<tr><td>Process ID type</td>
+<td><tt class="docutils literal"><span class="pre">process_id_type</span></tt></td>
+<td>Determined by the process group
+associated with type X.</td>
+</tr>
+<tr><td>Local descriptor
+type</td>
+<td><tt class="docutils literal"><span class="pre">local_type</span></tt></td>
+<td>Determined by the data structure
+the descriptor accesses.
+Must model <a class="reference external" href="http://www.sgi.com/tech/stl/EqualityComparable.html";>Equality Comparable</a> +and <a class="reference external" href="http://www.sgi.com/tech/stl/CopyConstructible.html";>Copy Constructible</a>.</td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="section" id="valid-expressions">
+<h1><a class="toc-backref" href="#id5">Valid Expressions</a></h1>
+<table border="1" class="docutils">
+<colgroup>
+<col width="17%" />
+<col width="22%" />
+<col width="22%" />
+<col width="39%" />
+</colgroup>
+<thead valign="bottom">
+<tr><th class="head">Name</th>
+<th class="head">Expression</th>
+<th class="head">Type</th>
+<th class="head">Semantics</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr><td>Owner</td>
+<td><tt class="docutils literal"><span class="pre">owner(x)</span></tt></td> +<td><tt class="docutils literal"><span class="pre">process_id_type</span></tt></td> +<td>Returns the owner of <tt class="docutils literal"><span class="pre">x</span></tt>.</td>
+</tr>
+<tr><td>Local descriptor</td>
+<td><tt class="docutils literal"><span class="pre">local(x)</span></tt></td> +<td><tt class="docutils literal"><span class="pre">local_type</span></tt></td>
+<td>Returns the local descriptor
+uniquely identifying <tt class="docutils literal"><span class="pre">x</span></tt>.</td>
+</tr>
+</tbody>
+</table>
+<hr class="docutils" />
+<p>Copyright (C) 2005 The Trustees of Indiana University.</p>
+<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:22 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/betweenness_centrality.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,248 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Betweenness Centrality</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-betweenness-centrality">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Betweenness Centrality</h1>
+
+<!-- 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) -->
+<pre class="literal-block">
+// named parameter versions
+template&lt;typename Graph, typename Param, typename Tag, typename Rest&gt;
+void
+brandes_betweenness_centrality(const Graph&amp; g,
+ const bgl_named_params&lt;Param,Tag,Rest&gt;&amp; params);
+
+template&lt;typename Graph, typename CentralityMap&gt;
+void
+brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality);
+
+template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap&gt;
+void
+brandes_betweenness_centrality(const Graph&amp; g, CentralityMap centrality,
+                               EdgeCentralityMap edge_centrality_map);
+
+// non-named parameter versions
+template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap, + typename IncomingMap, typename DistanceMap, typename DependencyMap, + typename PathCountMap, typename VertexIndexMap, typename Buffer&gt;
+void
+brandes_betweenness_centrality(const Graph&amp; g,
+                               CentralityMap centrality,
+                               EdgeCentralityMap edge_centrality_map,
+                               IncomingMap incoming,
+                               DistanceMap distance,
+                               DependencyMap dependency,
+                               PathCountMap path_count,
+                               VertexIndexMap vertex_index,
+                               Buffer sources,
+ typename property_traits&lt;DistanceMap&gt;::value_type delta);
+
+template&lt;typename Graph, typename CentralityMap, typename EdgeCentralityMap, + typename IncomingMap, typename DistanceMap, typename DependencyMap, + typename PathCountMap, typename VertexIndexMap, typename WeightMap,
+         typename Buffer&gt;
+void
+brandes_betweenness_centrality(const Graph&amp; g,
+                               CentralityMap centrality,
+                               EdgeCentralityMap edge_centrality_map,
+                               IncomingMap incoming,
+                               DistanceMap distance,
+                               DependencyMap dependency,
+                               PathCountMap path_count,
+                               VertexIndexMap vertex_index,
+                               Buffer sources,
+ typename property_traits&lt;WeightMap&gt;::value_type delta,
+                               WeightMap weight_map);
+
+// helper functions
+template&lt;typename Graph, typename CentralityMap&gt;
+typename property_traits&lt;CentralityMap&gt;::value_type
+central_point_dominance(const Graph&amp; g, CentralityMap centrality);
+</pre>
+<p>The <tt class="docutils literal"><span class="pre">brandes_betweenness_centrality()</span></tt> function computes the
+betweenness centrality of the vertices and edges in a graph.  The
+method of calculating betweenness centrality in <em>O(V)</em> space is due to +Brandes <a class="citation-reference" href="#brandes01" id="id1">[Brandes01]</a>. The algorithm itself is a modification of +Brandes algorithm by Edmonds <a class="citation-reference" href="#edmonds09" id="id2">[Edmonds09]</a>.</p>
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#where-defined" id="id3">Where Defined</a></li> +<li><a class="reference internal" href="#parameters" id="id4">Parameters</a></li> +<li><a class="reference internal" href="#complexity" id="id5">Complexity</a></li> +<li><a class="reference internal" href="#algorithm-description" id="id6">Algorithm Description</a></li> +<li><a class="reference internal" href="#bibliography" id="id7">Bibliography</a></li>
+</ul>
+</div>
+<div class="section" id="where-defined">
+<h1><a class="toc-backref" href="#id3">Where Defined</a></h1>
+<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/betweenness_centrality.hpp</span></tt>&gt;</p>
+<p>also accessible from</p>
+<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/betweenness_centrality.hpp</span></tt>&gt;</p>
+</div>
+<div class="section" id="parameters">
+<h1><a class="toc-backref" href="#id4">Parameters</a></h1>
+<dl class="docutils">
+<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt> +<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>. The graph +type must also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html";>Incidence Graph</a> concept. 0-weighted +edges in <tt class="docutils literal"><span class="pre">g</span></tt> will result in undefined behavior.</dd> +<dt>IN: <tt class="docutils literal"><span class="pre">CentralityMap</span> <span class="pre">centrality</span></tt></dt> +<dd><p class="first">A centrality map may be supplied to the algorithm, if not supplied a +<tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> will be used and no vertex centrality +information will be recorded. The <tt class="docutils literal"><span class="pre">CentralityMap</span></tt> type must be a +<a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The key type must be the graph's
+vertex descriptor type.</p>
+<p class="last"><strong>Default</strong>: A <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>.</p>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">EdgeCentralityMap</span> <span class="pre">edge_centrality_map</span></tt></dt> +<dd><p class="first">An edge centrality map may be supplied to the algorithm, if not +supplied a <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt> will be used and no edge +centrality information will be recorded. The <tt class="docutils literal"><span class="pre">EdgeCentralityMap</span></tt> +type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. The key type must be
+the graph's vertex descriptor type.</p>
+<p class="last"><strong>Default</strong>: A <tt class="docutils literal"><span class="pre">dummy_property_map</span></tt>.</p>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">IncomingMap</span> <span class="pre">incoming</span></tt></dt> +<dd><p class="first">The incoming map contains the incoming edges to a vertex that are +part of shortest paths to that vertex. The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> type +must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its key type and value type
+must both be the graph's vertex descriptor type.</p>
+<dl class="last docutils">
+<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> +<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of <tt class="docutils literal"><span class="pre">std::vector</span></tt> of the graph's vertex
+descriptor type.</dd>
+</dl>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">DistanceMap</span> <span class="pre">distance</span></tt></dt> +<dd><p class="first">The distance map records the distance to vertices during the +shortest paths portion of the algorithm. The <tt class="docutils literal"><span class="pre">DistanceMap</span></tt> type +must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its key type must be the
+graph's vertex descriptor type.</p>
+<dl class="last docutils">
+<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> +<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the value type of the <tt class="docutils literal"><span class="pre">CentralityMap</span></tt>.</dd>
+</dl>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">DependencyMap</span> <span class="pre">dependency</span></tt></dt> +<dd><p class="first">The dependency map records the dependency of each vertex during the
+centrality calculation portion of the algorithm.  The
+<tt class="docutils literal"><span class="pre">DependencyMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>. Its
+key type must be the graph's vertex descriptor type.</p>
+<dl class="last docutils">
+<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> +<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the value type of the <tt class="docutils literal"><span class="pre">CentralityMap</span></tt>.</dd>
+</dl>
+</dd>
+</dl>
+<p>IN: <tt class="docutils literal"><span class="pre">PathCountMap</span> <span class="pre">path_count</span></tt></p>
+<blockquote>
+<p>The path count map records the number of shortest paths each vertex
+is on during the centrality calculation portion of the algorithm.
+The <tt class="docutils literal"><span class="pre">PathCountMap</span></tt> type must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a>.
+Its key type must be the graph's vertex descriptor type.</p>
+<dl class="docutils">
+<dt><strong>Default</strong>: An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a</dt> +<dd><tt class="docutils literal"><span class="pre">std::vector</span></tt> of the graph's degree size type.</dd>
+</dl>
+</blockquote>
+<dl class="docutils">
+<dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">vertex_index</span></tt></dt> +<dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html";>Readable Property Map</a> whose key type is the vertex +descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt> and whose value type is an
+integral type. The property map should map from vertices to their
+(local) indices in the range <em>[0, num_vertices(g))</em>.</p>
+<p class="last"><strong>Default</strong>: <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">WeightMap</span> <span class="pre">weight_map</span></tt></dt> +<dd>A model of <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html";>Readable Property Map</a> whose key type is the edge +descriptor type of the graph <tt class="docutils literal"><span class="pre">g</span></tt>. If not supplied the betweenness
+centrality calculation will be unweighted.</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">Buffer</span> <span class="pre">sources</span></tt></dt> +<dd><p class="first">A model of <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html";>Buffer</a> containing the starting vertices for the +algorithm. If <tt class="docutils literal"><span class="pre">sources</span></tt> is empty a complete betweenness +centrality calculation using all vertices in <tt class="docutils literal"><span class="pre">g</span></tt> will be
+performed.  The value type of the Buffer must be the graph's vertex
+descriptor type.</p>
+<p class="last"><strong>Default</strong>: An empty <tt class="docutils literal"><span class="pre">boost::queue</span></tt> of int.</p>
+</dd>
+</dl>
+</div>
+<div class="section" id="complexity">
+<h1><a class="toc-backref" href="#id5">Complexity</a></h1>
+<p>Computing the shortest paths, counting them, and computing the
+contribution to the centrality map is <em>O(V log V)</em>. Calculating exact
+betweenness centrality requires counting the shortest paths from all
+vertices in <tt class="docutils literal"><span class="pre">g</span></tt>, thus exact betweenness centrality is <em>O(V^2 log
+V)</em>.</p>
+</div>
+<div class="section" id="algorithm-description">
+<h1><a class="toc-backref" href="#id6">Algorithm Description</a></h1>
+<p>For the vertices in <tt class="docutils literal"><span class="pre">sources</span></tt> (or all vertices in <tt class="docutils literal"><span class="pre">g</span></tt> when +<tt class="docutils literal"><span class="pre">sources</span></tt> is empty) the algorithm first calls a customized +implementation of <a class="reference external" href="dijkstra_shortest_paths.html">delta_stepping_shortest_paths</a> which maintains a +shortest path tree using an <tt class="docutils literal"><span class="pre">IncomingMap</span></tt>. The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt>
+contains the source of all incoming edges on shortest paths.</p>
+<p>The <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> defines the shortest path DAG at the target of the
+edges in the shortest paths tree.  In the bidirectional case edge
+flags could be used to translate the shortest paths information to the
+source of the edges.  Setting edge flags during the shortest path
+computation rather than using an <tt class="docutils literal"><span class="pre">IncomingMap</span></tt> would result in
+adding an <em>O(V)</em> factor to the inner loop of the shortest paths
+computation to account for having to clear edge flags when a new
+shortest path is found.  This would increase the complexity of the
+algorithm.  Asymptotically, the current implementation is better,
+however using edge flags in the bidirectional case would reduce the
+number of supersteps required by the depth of the shortest paths DAG
+for each vertex. Currently an <tt class="docutils literal"><span class="pre">outgoing</span></tt> map is explicitly
+constructed by simply reversing the edges in the incoming map.  Once
+the <tt class="docutils literal"><span class="pre">outgoing</span></tt> map is constructed it is traversed in dependency
+order from the source of the shortest paths calculation in order to
+compute path counts.  Once path counts are computed the shortest paths
+DAG is again traversed in dependency order from the source to
+calculate the dependency and centrality of each vertex.</p>
+<p>The algorithm is complete when the centrality has been computed from
+all vertices in <tt class="docutils literal"><span class="pre">g</span></tt>.</p>
+</div>
+<div class="section" id="bibliography">
+<h1><a class="toc-backref" href="#id7">Bibliography</a></h1>
+<table class="docutils citation" frame="void" id="brandes01" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id1">[Brandes01]</a></td><td>Ulrik Brandes. A Faster Algorithm for Betweenness
+Centrality. In the Journal of Mathematical Sociology, volume 25
+number 2, pages 163--177, 2001.</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="edmonds09" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id2">[Edmonds09]</a></td><td>Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine.
+A Space-Efficient Parallel Algorithm for Computing Betweenness
+Centrality in Sparse Networks.  Indiana University tech report.
+2009.</td></tr>
+</tbody>
+</table>
+<hr class="docutils" />
+<p>Copyright (C) 2009 The Trustees of Indiana University.</p>
+<p>Authors: Nick Edmonds and Andrew Lumsdaine</p>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:21 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/boman_et_al_graph_coloring.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,184 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Boman et al graph coloring</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-boman-et-al-graph-coloring">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Boman et al graph coloring</h1>
+
+<!-- Copyright (C) 2004-2008 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) -->
+<pre class="literal-block">
+namespace graph {
+  template&lt;typename DistributedGraph, typename ColorMap&gt;
+  typename property_traits&lt;ColorMap&gt;::value_type
+  boman_et_al_graph_coloring
+    (const DistributedGraph&amp; g,
+     ColorMap color,
+ typename graph_traits&lt;DistributedGraph&gt;::vertices_size_type s = 100);
+
+ template&lt;typename DistributedGraph, typename ColorMap, typename ChooseColor&gt;
+  typename property_traits&lt;ColorMap&gt;::value_type
+  boman_et_al_graph_coloring
+    (const DistributedGraph&amp; g,
+     ColorMap color,
+     typename graph_traits&lt;DistributedGraph&gt;::vertices_size_type s,
+     ChooseColor choose_color);
+
+ template&lt;typename DistributedGraph, typename ColorMap, typename ChooseColor,
+           typename VertexOrdering&gt;
+  typename property_traits&lt;ColorMap&gt;::value_type
+  boman_et_al_graph_coloring
+    (const DistributedGraph&amp; g, ColorMap color,
+     typename graph_traits&lt;DistributedGraph&gt;::vertices_size_type s,
+     ChooseColor choose_color, VertexOrdering ordering);
+
+ template&lt;typename DistributedGraph, typename ColorMap, typename ChooseColor,
+           typename VertexOrdering, typename VertexIndexMap&gt;
+  typename property_traits&lt;ColorMap&gt;::value_type
+  boman_et_al_graph_coloring
+    (const DistributedGraph&amp; g,
+     ColorMap color,
+     typename graph_traits&lt;DistributedGraph&gt;::vertices_size_type s,
+     ChooseColor choose_color,
+     VertexOrdering ordering, VertexIndexMap vertex_index);
+}
+</pre>
+<p>The <tt class="docutils literal"><span class="pre">boman_et_al_graph_coloring</span></tt> function colors the vertices of an
+undirected, distributed graph such that no two adjacent vertices have
+the same color. All of the vertices of a given color form an
+independent set in the graph. Graph coloring has been used to solve
+various problems, including register allocation in compilers,
+optimization problems, and scheduling problems.</p>
+<img align="right" alt="Vertex coloring example" class="align-right" src="../vertex_coloring.png" style="width: 462px; height: 269px;" />
+<p>The problem of coloring a graph with the fewest possible number of
+colors is NP-complete, so many algorithms (including the one
+implemented here) are heuristic algorithms that try to minimize the
+number of colors but are not guaranteed to provide an optimal
+solution. This algorithm <a class="citation-reference" href="#bbc05" id="id1">[BBC05]</a> is similar to the +<tt class="docutils literal"><span class="pre">sequential_vertex_coloring</span></tt> algorithm, that iterates through the
+vertices once and selects the lowest-numbered color that the current
+vertex can have. The coloring and the number of colors is therefore
+related to the ordering of the vertices in the sequential case.</p>
+<p>The distributed <tt class="docutils literal"><span class="pre">boman_et_al_graph_coloring</span></tt> algorithm will produce
+different colorings depending on the ordering and distribution of the
+vertices and the number of parallel processes cooperating to perform
+the coloring.</p>
+<p>The algorithm returns the number of colors <tt class="docutils literal"><span class="pre">num_colors</span></tt> used to
+color the graph.</p>
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#where-defined" id="id2">Where Defined</a></li> +<li><a class="reference internal" href="#parameters" id="id3">Parameters</a></li> +<li><a class="reference internal" href="#complexity" id="id4">Complexity</a></li> +<li><a class="reference internal" href="#performance" id="id5">Performance</a></li>
+</ul>
+</div>
+<div class="section" id="where-defined">
+<h1><a class="toc-backref" href="#id2">Where Defined</a></h1>
+<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/distributed/boman_et_al_graph_coloring.hpp</span></tt>&gt;</p>
+</div>
+<div class="section" id="parameters">
+<h1><a class="toc-backref" href="#id3">Parameters</a></h1>
+<dl class="docutils">
+<dt>IN: <tt class="docutils literal"><span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt> +<dd>The graph type must be a model of <a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List Graph</a> and +<a class="reference external" href="DistributedEdgeListGraph.html">Distributed Edge List Graph</a>.</dd> +<dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">ColorMap</span> <span class="pre">color</span></tt></dt>
+<dd>Stores the color of each vertex, which will be a value in the range
+[0, <tt class="docutils literal"><span class="pre">num_colors</span></tt>). The type <tt class="docutils literal"><span class="pre">ColorMap</span></tt> must model the +<a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html";>Read/Write Property Map</a> concept and must be a <a class="reference external" href="distributed_property_map.html">distributed
+property map</a>.</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">vertices_size_type</span> <span class="pre">s</span></tt></dt> +<dd><p class="first">The number of vertices to color within each superstep. After +<tt class="docutils literal"><span class="pre">s</span></tt> vertices have been colored, the colors of boundary vertices
+will be sent to their out-of-process neighbors. Smaller values
+communicate more often but may reduce the risk of conflicts,
+whereas larger values do more work in between communication steps
+but may create many conflicts.</p>
+<p class="last"><strong>Default</strong>: 100</p>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">ChooseColor</span> <span class="pre">choose_color</span></tt></dt> +<dd><p class="first">A function object that chooses the color for a vertex given the
+colors of its neighbors. The function object will be passed a vector
+of values (<tt class="docutils literal"><span class="pre">marked</span></tt>) and a <tt class="docutils literal"><span class="pre">marked_true</span></tt> value, and should +return a <tt class="docutils literal"><span class="pre">color</span></tt> value such that <tt class="docutils literal"><span class="pre">color</span> <span class="pre">&gt;=</span> <span class="pre">marked.size()</span></tt> or +<tt class="docutils literal"><span class="pre">marked[color]</span> <span class="pre">!=</span> <span class="pre">marked_true</span></tt>.</p>
+<p class="last"><strong>Default</strong>:
+<tt class="docutils literal"><span class="pre">boost::graph::distributed::first_fit_color&lt;color_type&gt;()</span></tt>, where +<tt class="docutils literal"><span class="pre">color_type</span></tt> is the value type of the <tt class="docutils literal"><span class="pre">ColorMap</span></tt> property map.</p>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">VertexOrdering</span> <span class="pre">ordering</span></tt></dt> +<dd><p class="first">A binary predicate function object that provides total ordering on
+the vertices in the graph. Whenever a conflict arises, only one of
+the processes involved will recolor the vertex in the next round,
+and this ordering determines which vertex should be considered
+conflicting (its owning process will then handle the
+conflict). Ideally, this predicate should order vertices so that
+conflicting vertices will be spread uniformly across
+processes. However, this predicate <em>must</em> resolve the same way on
+both processors.</p>
+<p class="last"><strong>Default</strong>: <em>unspecified</em></p>
+</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">index</span></tt></dt> +<dd><p class="first">A mapping from vertex descriptors to indices in the range <em>[0, +num_vertices(g))</em>. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html";>Readable Property Map</a> whose
+key type is a vertex descriptor and whose value type is an integral
+type, typically the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph.</p> +<p class="last"><strong>Default:</strong> <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p>
+</dd>
+</dl>
+</div>
+<div class="section" id="complexity">
+<h1><a class="toc-backref" href="#id4">Complexity</a></h1>
+<p>The complexity of this algorithm is hard to characterize,
+because it depends greatly on the number of <em>conflicts</em> that occur
+during the algorithm. A conflict occurs when a <em>boundary vertex</em>
+(i.e., a vertex that is adjacent to a vertex stored on a different
+processor) is given the same color is a boundary vertex adjacency to
+it (but on another processor). Conflicting vertices must be assigned
+new colors, requiring additional work and communication. The work
+involved in reassigning a color for a conflicting vertex is <em>O(d)</em>,
+where <em>d</em> is the degree of the vertex and <em>O(1)</em> messages of <em>O(1)</em>
+size are needed to resolve the conflict. Note that the number of
+conflicts grows with (1) the number of processes and (2) the number
+of inter-process edges.</p>
+</div>
+<div class="section" id="performance">
+<h1><a class="toc-backref" href="#id5">Performance</a></h1>
+<p>The performance of this implementation of Bomen et al's graph coloring
+algorithm is illustrated by the following charts. Scaling and
+performance is reasonable for all of the graphs we have tried.</p>
+<img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11.png" /> +<img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11_speedup_1.png" /> +<img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11.png" /> +<img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11_speedup_1.png" />
+<hr class="docutils" />
+<p>Copyright (C) 2005 The Trustees of Indiana University.</p>
+<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
+<table class="docutils citation" frame="void" id="bbc05" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id1">[BBC05]</a></td><td>Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw
+H. Gebremedhin, and Fredrik Manne. A Scalable Parallel Graph Coloring
+Algorithm for Distributed Memory Computers. [preprint]</td></tr>
+</tbody>
+</table>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:21 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null
+++ /trunk/libs/graph_parallel/doc/html/breadth_first_search.html Sat Nov 28 08:00:21 2009
@@ -0,0 +1,269 @@
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";>
+<html xmlns="http://www.w3.org/1999/xhtml"; xml:lang="en" lang="en">
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/"; />
+<title>Parallel BGL Breadth-First Search</title>
+<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+</head>
+<body>
+<div class="document" id="logo-breadth-first-search">
+<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl";><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Breadth-First Search</h1>
+
+<!-- Copyright (C) 2004-2008 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) -->
+<pre class="literal-block">
+// named parameter version
+template &lt;class Graph, class P, class T, class R&gt;
+void breadth_first_search(Graph&amp; G,
+  typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
+  const bgl_named_params&lt;P, T, R&gt;&amp; params);
+
+// non-named parameter version
+template &lt;class Graph, class Buffer, class BFSVisitor,
+          class ColorMap&gt;
+void breadth_first_search(const Graph&amp; g,
+   typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
+   Buffer&amp; Q, BFSVisitor vis, ColorMap color);
+</pre>
+<p>The <tt class="docutils literal"><span class="pre">breadth_first_search()</span></tt> function performs a distributed breadth-first
+traversal of a directed or undirected graph. The distributed BFS is
+syntactically equivalent to its <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html";>sequential counterpart</a>, which
+provides additional background and discussion. Differences in
+semantics are highlighted here, and we refer the reader to the
+documentation of the <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html";>sequential breadth-first search</a> for the
+remainder of the details.</p>
+<p>This distributed breadth-first search algorithm implements a
+<em>level-synchronized</em> breadth-first search, meaning that all vertices
+in a given level of the BFS tree will be processed (potentially in
+parallel) before any vertices from a successive level in the tree are
+processed. Distributed breadth-first search visitors should account
+for this behavior, a topic discussed further in <a class="reference internal" href="#visitor-event-points">Visitor Event
+Points</a>.</p>
+<div class="contents topic" id="contents">
+<p class="topic-title first">Contents</p>
+<ul class="simple">
+<li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li> +<li><a class="reference internal" href="#parameter-defaults" id="id2">Parameter Defaults</a></li> +<li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li> +<li><a class="reference internal" href="#visitor-event-points" id="id4">Visitor Event Points</a><ul> +<li><a class="reference internal" href="#making-visitors-safe-for-distributed-bfs" id="id5">Making Visitors Safe for Distributed BFS</a></li> +<li><a class="reference internal" href="#distributed-bfs-visitor-example" id="id6">Distributed BFS Visitor Example</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#performance" id="id7">Performance</a></li>
+</ul>
+</div>
+<div class="section" id="where-defined">
+<h1><a class="toc-backref" href="#id1">Where Defined</a></h1>
+<p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/breadth_first_search.hpp</span></tt>&gt;</p>
+</div>
+<div class="section" id="parameter-defaults">
+<h1><a class="toc-backref" href="#id2">Parameter Defaults</a></h1>
+<p>All parameters of the <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html";>sequential breadth-first search</a> are supported
+and have essentially the same meaning. Only differences are documented
+here.</p>
+<dl class="docutils">
+<dt>IN: <tt class="docutils literal"><span class="pre">Graph&amp;</span> <span class="pre">g</span></tt></dt> +<dd>The graph type must be a model of <a class="reference external" href="DistributedGraph.html">Distributed Graph</a>.</dd> +<dt>IN: <tt class="docutils literal"><span class="pre">vertex_descriptor</span> <span class="pre">s</span></tt></dt>
+<dd>The start vertex must be the same in every process.</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">visitor(BFSVisitor</span> <span class="pre">vis)</span></tt></dt>
+<dd>The visitor must be a distributed BFS visitor. The suble differences
+between sequential and distributed BFS visitors are discussed in the
+section <a class="reference internal" href="#visitor-event-points">Visitor Event Points</a>.</dd> +<dt>UTIL/OUT: <tt class="docutils literal"><span class="pre">color_map(ColorMap</span> <span class="pre">color)</span></tt></dt> +<dd>The color map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> with the same +process group as the graph <tt class="docutils literal"><span class="pre">g</span></tt> whose colors must monotonically
+darken (white -&gt; gray -&gt; black). The default value is a distributed
+<tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> created from a <tt class="docutils literal"><span class="pre">std::vector</span></tt> of +<tt class="docutils literal"><span class="pre">default_color_type</span></tt>.</dd> +<dt>UTIL: <tt class="docutils literal"><span class="pre">buffer(Buffer&amp;</span> <span class="pre">Q)</span></tt></dt> +<dd><p class="first">The queue must be a distributed queue that passes vertices to their
+owning process. If already-visited vertices should not be visited
+again (as is typical for BFS), the queue must filter duplicates
+itself. The queue controls synchronization within the algorithm: its
+<tt class="docutils literal"><span class="pre">empty()</span></tt> method must not return <tt class="docutils literal"><span class="pre">true</span></tt> until all local queues
+are empty.</p>
+<dl class="last docutils">
+<dt><strong>Default:</strong> A <tt class="docutils literal"><span class="pre">distributed_queue</span></tt> of a <tt class="docutils literal"><span class="pre">filtered_queue</span></tt> over a</dt> +<dd>standard <tt class="docutils literal"><span class="pre">boost::queue</span></tt>. This queue filters out duplicate
+vertices and distributes vertices appropriately.</dd>
+</dl>
+</dd>
+</dl>
+</div>
+<div class="section" id="complexity">
+<h1><a class="toc-backref" href="#id3">Complexity</a></h1>
+<p>This algorithm performs <em>O(V + E)</em> work in <em>d + 1</em> BSP supersteps,
+where <em>d</em> is the diameter of the connected component being
+searched. Over all supersteps, <em>O(E)</em> messages of constant size will
+be transmitted.</p>
+</div>
+<div class="section" id="visitor-event-points">
+<h1><a class="toc-backref" href="#id4">Visitor Event Points</a></h1>
+<p>The <a class="reference external" href="http://www.boost.org/libs/graph/doc/BFSVisitor.html";>BFS Visitor</a> concept defines 9 event points that will be +triggered by the <a class="reference external" href="http://www.boost.org/libs/graph/doc/breadth_first_search.html";>sequential breadth-first search</a>. The distributed
+BFS retains these nine event points, but the sequence of events
+triggered and the process in which each event occurs will change
+depending on the distribution of the graph.</p>
+<dl class="docutils">
+<dt><tt class="docutils literal"><span class="pre">initialize_vertex(s,</span> <span class="pre">g)</span></tt></dt>
+<dd>This will be invoked by every process for each local vertex.</dd>
+<dt><tt class="docutils literal"><span class="pre">discover_vertex(u,</span> <span class="pre">g)</span></tt></dt>
+<dd>This will be invoked each time a process discovers a new vertex
+<tt class="docutils literal"><span class="pre">u</span></tt>. Due to incomplete information in distributed property maps, +this event may be triggered many times for the same vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd> +<dt><tt class="docutils literal"><span class="pre">examine_vertex(u,</span> <span class="pre">g)</span></tt></dt> +<dd>This will be invoked by the process owning the vertex <tt class="docutils literal"><span class="pre">u</span></tt>. If the
+distributed queue prevents duplicates, it will be invoked only
+once for a particular vertex <tt class="docutils literal"><span class="pre">u</span></tt>.</dd> +<dt><tt class="docutils literal"><span class="pre">examine_edge(e,</span> <span class="pre">g)</span></tt></dt>
+<dd>This will be invoked by the process owning the source vertex of
+<tt class="docutils literal"><span class="pre">e</span></tt>. If the distributed queue prevents duplicates, it will be +invoked only once for a particular edge <tt class="docutils literal"><span class="pre">e</span></tt>.</dd> +<dt><tt class="docutils literal"><span class="pre">tree_edge(e,</span> <span class="pre">g)</span></tt></dt> +<dd>Similar to <tt class="docutils literal"><span class="pre">examine_edge</span></tt>, this will be invoked by the process
+owning the source vertex and may be invoked only once. Unlike the
+sequential BFS, this event may be triggered even when the target has
+already been discovered (but by a different process). Thus, some
+<tt class="docutils literal"><span class="pre">non_tree_edge</span></tt> events in a sequential BFS may become +<tt class="docutils literal"><span class="pre">tree_edge</span></tt> in a distributed BFS.</dd> +<dt><tt class="docutils literal"><span class="pre">non_tree_edge(e,</span> <span class="pre">g)</span></tt></dt> +<dd>Some <tt class="docutils literal"><span class="pre">non_tree_edge</span></tt> events in a sequential BFS may become +<tt class="docutils literal"><span class="pre">tree_edge</span></tt> events in a distributed BFS. See the description of +<tt class="docutils literal"><span class="pre">tree_edge</span></tt> for additional details.</dd> +<dt><tt class="docutils literal"><span class="pre">gray_target(e,</span> <span class="pre">g)</span></tt></dt> +<dd>As with <tt class="docutils literal"><span class="pre">tree_edge</span></tt> not knowing when another process has already +discovered a vertex, <tt class="docutils literal"><span class="pre">gray_target</span></tt> events may occur in a +distributed BFS when <tt class="docutils literal"><span class="pre">black_target</span></tt> events may occur in a
+sequential BFS, due to a lack of information on a given
+processor. The source of edge <tt class="docutils literal"><span class="pre">e</span></tt> will be local to the process
+executing this event.</dd>
+<dt><tt class="docutils literal"><span class="pre">black_target(e,</span> <span class="pre">g)</span></tt></dt> +<dd>See documentation for <tt class="docutils literal"><span class="pre">gray_target</span></tt></dd> +<dt><tt class="docutils literal"><span class="pre">finish_vertex(e,</span> <span class="pre">g)</span></tt></dt> +<dd>See documentation for <tt class="docutils literal"><span class="pre">examine_vertex</span></tt>.</dd>
+</dl>
+<div class="section" id="making-visitors-safe-for-distributed-bfs">
+<h2><a class="toc-backref" href="#id5">Making Visitors Safe for Distributed BFS</a></h2>
+<p>The three most important things to remember when updating an existing
+BFS visitor for distributed BFS or writing a new distributed BFS
+visitor are:</p>
+<ol class="arabic simple">
+<li>Be sure that all state is either entirely local or in a
+distributed data structure (most likely a property map!) using
+the same process group as the graph.</li>
+<li>Be sure that the visitor doesn't require precise event sequences
+that cannot be guaranteed by distributed BFS, e.g., requiring
+<tt class="docutils literal"><span class="pre">tree_edge</span></tt> and <tt class="docutils literal"><span class="pre">non_tree_edge</span></tt> events to be completely
+distinct.</li>
+<li>Be sure that the visitor can operate on incomplete
+information. This often includes using an appropriate reduction
+operation in a <a class="reference external" href="distributed_property_map.html">distributed property map</a> and verifying that +results written are &quot;better&quot; that what was previously written.</li>
+</ol>
+</div>
+<div class="section" id="distributed-bfs-visitor-example">
+<h2><a class="toc-backref" href="#id6">Distributed BFS Visitor Example</a></h2>
+<p>To illustrate the differences between sequential and distributed BFS
+visitors, we consider a BFS visitor that places the distance from the
+source vertex to every other vertex in a property map. The sequential
+visitor is very simple:</p>
+<pre class="literal-block">
+template&lt;typename DistanceMap&gt;
+struct bfs_discovery_visitor : bfs_visitor&lt;&gt;
+{
+  bfs_discovery_visitor(DistanceMap distance) : distance(distance) {}
+
+  template&lt;typename Edge, typename Graph&gt;
+  void tree_edge(Edge e, const Graph&amp; g)
+  {
+    std::size_t new_distance = get(distance, source(e, g)) + 1;
+    put(distance, target(e, g), new_distance);
+  }
+
+ private:
+  DistanceMap distance;
+};
+</pre>
+<p>To revisit this code for distributed BFS, we consider the three points
+in the section <a class="reference internal" href="#making-visitors-safe-for-distributed-bfs">Making Visitors Safe for Distributed BFS</a>:</p>
+<ol class="arabic">
+<li><p class="first">The distance map will need to become distributed, because the
+distance to each vertex should be stored in the process owning the
+vertex. This is actually a requirement on the user to provide such
+a distributed property map, although in many cases the property map
+will automatically be distributed and no syntactic changes will be
+required.</p>
+</li>
+<li><p class="first">This visitor <em>does</em> require a precise sequence of events that may +change with a distributed BFS. The extraneous <tt class="docutils literal"><span class="pre">tree_edge</span></tt> events
+that may occur could result in attempts to put distances into the
+distance map multiple times for a single vertex. We therefore need
+to consider bullet #3.</p>
+</li>
+<li><p class="first">Since multiple distance values may be written for each vertex, we
+must always choose the best value we can find to update the
+distance map. The distributed property map <tt class="docutils literal"><span class="pre">distance</span></tt> needs to
+resolve distances to the smallest distance it has seen. For
+instance, process 0 may find vertex <tt class="docutils literal"><span class="pre">u</span></tt> at level 3 but process 1
+finds it at level 5: the distance must remain at 3. To do this, we
+state that the property map's <em>role</em> is as a distance map, which
+introduces an appropriate reduction operation:</p>
+<pre class="literal-block">
+set_property_map_role(vertex_distance, distance);
+</pre>
+</li>
+</ol>
+<p>The resulting distributed BFS visitor (which also applies, with no
+changes, in the sequential BFS) is very similar to our original
+sequential BFS visitor. Note the single-line difference in the
+constructor:</p>
+<pre class="literal-block">
+template&lt;typename DistanceMap&gt;
+struct bfs_discovery_visitor : bfs_visitor&lt;&gt;
+{
+  bfs_discovery_visitor(DistanceMap distance) : distance(distance)
+  {
+    set_property_map_role(vertex_distance, distance);
+  }
+
+  template&lt;typename Edge, typename Graph&gt;
+  void tree_edge(Edge e, const Graph&amp; g)
+  {
+    std::size_t new_distance = get(distance, source(e, g)) + 1;
+    put(distance, target(e, g), new_distance);
+  }
+
+ private:
+  DistanceMap distance;
+};
+</pre>
+</div>
+</div>
+<div class="section" id="performance">
+<h1><a class="toc-backref" href="#id7">Performance</a></h1>
+<p>The performance of Breadth-First Search is illustrated by the
+following charts. Scaling and performance is reasonable for all of the
+graphs we have tried.</p>
+<img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png" /> +<img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png" /> +<img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4.png" /> +<img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png" />
+<hr class="docutils" />
+<p>Copyright (C) 2004 The Trustees of Indiana University.</p>
+<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
+</div>
+</div>
+<div class="footer">
+<hr class="footer" />
+Generated on: 2009-05-31 00:21 UTC.
+Generated by <a class="reference external" href="http://docutils.sourceforge.net/";>Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html";>reStructuredText</a> source.
+
+</div>
+</body>
+</html>
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_cluster_Odin_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_cluster_Odin_columns_11_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_4_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_9_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_cluster_Odin_columns_11_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_4_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
--- /dev/null   
+++ /trunk/libs/graph_parallel/doc/html/chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png Sat Nov 28 08:00:21 2009
Binary file, no diff available.
=======================================
***Additional files exist in this changeset.***

Other related posts:

  • » [boost-doc-zh] r350 committed - 升级至1.41.0,第二批,libs/目录下g-l子目录 - boost-doc-zh