|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r53332 - in trunk/libs/graph_parallel/doc: . html
From: ngedmond_at_[hidden]
Date: 2009-05-27 19:35:35
Author: ngedmond
Date: 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
New Revision: 53332
URL: http://svn.boost.org/trac/boost/changeset/53332
Log:
Added/updated graph_parallel docs
Added:
trunk/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html (contents, props changed)
trunk/libs/graph_parallel/doc/non_distributed_betweenness_centrality.rst (contents, props changed)
Text files modified:
trunk/libs/graph_parallel/doc/betweenness_centrality.rst | 219 +++++++++++++++++
trunk/libs/graph_parallel/doc/html/betweenness_centrality.html | 502 +++++++++++++++++++++++++++++++++++++++
trunk/libs/graph_parallel/doc/html/index.html | 286 ++++++++++++++++++++++
trunk/libs/graph_parallel/doc/html/sorted_unique_rmat_generator.html | 283 ++++++++++++++++++++++
trunk/libs/graph_parallel/doc/index.rst | 8
trunk/libs/graph_parallel/doc/sorted_unique_rmat_generator.rst | 2
6 files changed, 1279 insertions(+), 21 deletions(-)
Modified: trunk/libs/graph_parallel/doc/betweenness_centrality.rst
==============================================================================
--- trunk/libs/graph_parallel/doc/betweenness_centrality.rst (original)
+++ trunk/libs/graph_parallel/doc/betweenness_centrality.rst 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -7,13 +7,230 @@
|Logo| Betweenness Centrality
=============================
+::
+
+ // named parameter versions
+ template<typename Graph, typename Param, typename Tag, typename Rest>
+ void
+ brandes_betweenness_centrality(const Graph& g,
+ const bgl_named_params<Param,Tag,Rest>& params);
+
+ template<typename Graph, typename CentralityMap>
+ void
+ brandes_betweenness_centrality(const Graph& g, CentralityMap centrality);
+
+ template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
+ void
+ brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map);
+
+ // non-named parameter versions
+ template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
+ typename IncomingMap, typename DistanceMap, typename DependencyMap,
+ typename PathCountMap, typename VertexIndexMap, typename Buffer>
+ void
+ brandes_betweenness_centrality(const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ Buffer sources,
+ typename property_traits<DistanceMap>::value_type delta);
+
+ template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
+ typename IncomingMap, typename DistanceMap, typename DependencyMap,
+ typename PathCountMap, typename VertexIndexMap, typename WeightMap,
+ typename Buffer>
+ void
+ brandes_betweenness_centrality(const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ Buffer sources,
+ typename property_traits<WeightMap>::value_type delta,
+ WeightMap weight_map);
+
+ // helper functions
+ template<typename Graph, typename CentralityMap>
+ typename property_traits<CentralityMap>::value_type
+ central_point_dominance(const Graph& g, CentralityMap centrality);
+
+The ``brandes_betweenness_centrality()`` function computes the
+betweenness centrality of the vertices and edges in a graph. The
+method of calculating betweenness centrality in *O(V)* space is due to
+Brandes [Brandes01]_. The algorithm itself is a modification of
+Brandes algorithm by Edmonds [Edmonds09]_.
+
+.. contents::
+
+Where Defined
+-------------
+<``boost/graph/distributed/betweenness_centrality.hpp``>
+
+also accessible from
+
+<``boost/graph/betweenness_centrality.hpp``>
+
+Parameters
+----------
+
+IN: ``const Graph& g``
+ The graph type must be a model of `Distributed Graph`_. The graph
+ type must also model the `Incidence Graph`_ concept. 0-weighted
+ edges in ``g`` will result in undefined behavior.
+
+IN: ``CentralityMap centrality``
+ A centrality map may be supplied to the algorithm, if not supplied a
+ ``dummy_property_map`` will be used and no vertex centrality
+ information will be recorded. The ``CentralityMap`` type must be a
+ `Distributed Property Map`_. The key type must be the graph's
+ vertex descriptor type.
+
+ **Default**: A ``dummy_property_map``.
+
+IN: ``EdgeCentralityMap edge_centrality_map``
+ An edge centrality map may be supplied to the algorithm, if not
+ supplied a ``dummy_property_map`` will be used and no edge
+ centrality information will be recorded. The ``EdgeCentralityMap``
+ type must be a `Distributed Property Map`_. The key type must be
+ the graph's vertex descriptor type.
+
+ **Default**: A ``dummy_property_map``.
+
+IN: ``IncomingMap incoming``
+ The incoming map contains the incoming edges to a vertex that are
+ part of shortest paths to that vertex. The ``IncomingMap`` type
+ must be a `Distributed Property Map`_. Its key type and value type
+ must both be the graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of ``std::vector`` of the graph's vertex
+ descriptor type.
+
+IN: ``DistanceMap distance``
+ The distance map records the distance to vertices during the
+ shortest paths portion of the algorithm. The ``DistanceMap`` type
+ must be a `Distributed Property Map`_. Its key type must be the
+ graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of the value type of the ``CentralityMap``.
+
+IN: ``DependencyMap dependency``
+ The dependency map records the dependency of each vertex during the
+ centrality calculation portion of the algorithm. The
+ ``DependencyMap`` type must be a `Distributed Property Map`_. Its
+ key type must be the graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of the value type of the ``CentralityMap``.
+
+IN: ``PathCountMap path_count``
+
+ The path count map records the number of shortest paths each vertex
+ is on during the centrality calculation portion of the algorithm.
+ The ``PathCountMap`` type must be a `Distributed Property Map`_.
+ Its key type must be the graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of the graph's degree size type.
+
+IN: ``VertexIndexMap vertex_index``
+ A model of `Readable Property Map`_ whose key type is the vertex
+ descriptor type of the graph ``g`` and whose value type is an
+ integral type. The property map should map from vertices to their
+ (local) indices in the range *[0, num_vertices(g))*.
+
+ **Default**: ``get(vertex_index, g)``
+
+IN: ``WeightMap weight_map``
+ A model of `Readable Property Map`_ whose key type is the edge
+ descriptor type of the graph ``g``. If not supplied the betweenness
+ centrality calculation will be unweighted.
+
+IN: ``Buffer sources``
+ A model of Buffer_ containing the starting vertices for the
+ algorithm. If ``sources`` is empty a complete betweenness
+ centrality calculation using all vertices in ``g`` will be
+ performed. The value type of the Buffer must be the graph's vertex
+ descriptor type.
+
+ **Default**: An empty ``boost::queue`` of int.
+
+Complexity
+----------
+
+Computing the shortest paths, counting them, and computing the
+contribution to the centrality map is *O(V log V)*. Calculating exact
+betweenness centrality requires counting the shortest paths from all
+vertices in ``g``, thus exact betweenness centrality is *O(V^2 log
+V)*.
+
+Algorithm Description
+---------------------
+
+For the vertices in ``sources`` (or all vertices in ``g`` when
+``sources`` is empty) the algorithm first calls a customized
+implementation of delta_stepping_shortest_paths_ which maintains a
+shortest path tree using an ``IncomingMap``. The ``IncomingMap``
+contains the source of all incoming edges on shortest paths.
+
+The ``IncomingMap`` 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 ``IncomingMap`` would result in
+adding an *O(V)* 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 ``outgoing`` map is explicitly
+constructed by simply reversing the edges in the incoming map. Once
+the ``outgoing`` 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.
+
+The algorithm is complete when the centrality has been computed from
+all vertices in ``g``.
+
+Bibliography
+------------
+
+.. [Brandes01] Ulrik Brandes. A Faster Algorithm for Betweenness
+ Centrality. In the Journal of Mathematical Sociology, volume 25
+ number 2, pages 163--177, 2001.
+
+.. [Edmonds09] Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine.
+ A Space-Efficient Parallel Algorithm for Computing Betweenness
+ Centrality in Sparse Networks. Indiana University tech report.
+ 2009.
+
-----------------------------------------------------------------------------
Copyright (C) 2009 The Trustees of Indiana University.
Authors: Nick Edmonds and Andrew Lumsdaine
-.. |Logo| image:: pbgl-logo.png
+.. |Logo| image:: http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png
:align: middle
:alt: Parallel BGL
:target: http://www.osl.iu.edu/research/pbgl
+
+.. _delta_stepping_shortest_paths: dijkstra_shortest_paths.html
+.. _Distributed Graph: DistributedGraph.html
+.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
+.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
+.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
+.. _Process Group: process_group.html
+.. _Distributed Property Map: distributed_property_map.html
\ No newline at end of file
Modified: trunk/libs/graph_parallel/doc/html/betweenness_centrality.html
==============================================================================
--- trunk/libs/graph_parallel/doc/html/betweenness_centrality.html (original)
+++ trunk/libs/graph_parallel/doc/html/betweenness_centrality.html 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -1,28 +1,520 @@
-<?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" />
+<style type="text/css">
+
+/*
+:Author: David Goodger (goodger_at_[hidden])
+:Id: $Id: html4css1.css 5631 2008-08-24 13:01:23Z goodger $
+:Copyright: This stylesheet has been placed in the public domain.
+
+Default cascading style sheet for the HTML output of Docutils.
+
+See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
+customize this style sheet.
+*/
+
+/* used to remove borders from tables and images */
+.borderless, table.borderless td, table.borderless th {
+ border: 0 }
+
+table.borderless td, table.borderless th {
+ /* Override padding for "table.docutils td" with "! important".
+ The right padding separates the table cells. */
+ padding: 0 0.5em 0 0 ! important }
+
+.first {
+ /* Override more specific margin styles with "! important". */
+ margin-top: 0 ! important }
+
+.last, .with-subtitle {
+ margin-bottom: 0 ! important }
+
+.hidden {
+ display: none }
+
+a.toc-backref {
+ text-decoration: none ;
+ color: black }
+
+blockquote.epigraph {
+ margin: 2em 5em ; }
+
+dl.docutils dd {
+ margin-bottom: 0.5em }
+
+/* Uncomment (and remove this text!) to get bold-faced definition list terms
+dl.docutils dt {
+ font-weight: bold }
+*/
+
+div.abstract {
+ margin: 2em 5em }
+
+div.abstract p.topic-title {
+ font-weight: bold ;
+ text-align: center }
+
+div.admonition, div.attention, div.caution, div.danger, div.error,
+div.hint, div.important, div.note, div.tip, div.warning {
+ margin: 2em ;
+ border: medium outset ;
+ padding: 1em }
+
+div.admonition p.admonition-title, div.hint p.admonition-title,
+div.important p.admonition-title, div.note p.admonition-title,
+div.tip p.admonition-title {
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.attention p.admonition-title, div.caution p.admonition-title,
+div.danger p.admonition-title, div.error p.admonition-title,
+div.warning p.admonition-title {
+ color: red ;
+ font-weight: bold ;
+ font-family: sans-serif }
+
+/* Uncomment (and remove this text!) to get reduced vertical space in
+ compound paragraphs.
+div.compound .compound-first, div.compound .compound-middle {
+ margin-bottom: 0.5em }
+
+div.compound .compound-last, div.compound .compound-middle {
+ margin-top: 0.5em }
+*/
+
+div.dedication {
+ margin: 2em 5em ;
+ text-align: center ;
+ font-style: italic }
+
+div.dedication p.topic-title {
+ font-weight: bold ;
+ font-style: normal }
+
+div.figure {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+div.footer, div.header {
+ clear: both;
+ font-size: smaller }
+
+div.line-block {
+ display: block ;
+ margin-top: 1em ;
+ margin-bottom: 1em }
+
+div.line-block div.line-block {
+ margin-top: 0 ;
+ margin-bottom: 0 ;
+ margin-left: 1.5em }
+
+div.sidebar {
+ margin: 0 0 0.5em 1em ;
+ border: medium outset ;
+ padding: 1em ;
+ background-color: #ffffee ;
+ width: 40% ;
+ float: right ;
+ clear: right }
+
+div.sidebar p.rubric {
+ font-family: sans-serif ;
+ font-size: medium }
+
+div.system-messages {
+ margin: 5em }
+
+div.system-messages h1 {
+ color: red }
+
+div.system-message {
+ border: medium outset ;
+ padding: 1em }
+
+div.system-message p.system-message-title {
+ color: red ;
+ font-weight: bold }
+
+div.topic {
+ margin: 2em }
+
+h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
+h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
+ margin-top: 0.4em }
+
+h1.title {
+ text-align: center }
+
+h2.subtitle {
+ text-align: center }
+
+hr.docutils {
+ width: 75% }
+
+img.align-left {
+ clear: left }
+
+img.align-right {
+ clear: right }
+
+ol.simple, ul.simple {
+ margin-bottom: 1em }
+
+ol.arabic {
+ list-style: decimal }
+
+ol.loweralpha {
+ list-style: lower-alpha }
+
+ol.upperalpha {
+ list-style: upper-alpha }
+
+ol.lowerroman {
+ list-style: lower-roman }
+
+ol.upperroman {
+ list-style: upper-roman }
+
+p.attribution {
+ text-align: right ;
+ margin-left: 50% }
+
+p.caption {
+ font-style: italic }
+
+p.credits {
+ font-style: italic ;
+ font-size: smaller }
+
+p.label {
+ white-space: nowrap }
+
+p.rubric {
+ font-weight: bold ;
+ font-size: larger ;
+ color: maroon ;
+ text-align: center }
+
+p.sidebar-title {
+ font-family: sans-serif ;
+ font-weight: bold ;
+ font-size: larger }
+
+p.sidebar-subtitle {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+p.topic-title {
+ font-weight: bold }
+
+pre.address {
+ margin-bottom: 0 ;
+ margin-top: 0 ;
+ font: inherit }
+
+pre.literal-block, pre.doctest-block {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+span.classifier {
+ font-family: sans-serif ;
+ font-style: oblique }
+
+span.classifier-delimiter {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+span.interpreted {
+ font-family: sans-serif }
+
+span.option {
+ white-space: nowrap }
+
+span.pre {
+ white-space: pre }
+
+span.problematic {
+ color: red }
+
+span.section-subtitle {
+ /* font-size relative to parent (h1..h6 element) */
+ font-size: 80% }
+
+table.citation {
+ border-left: solid 1px gray;
+ margin-left: 1px }
+
+table.docinfo {
+ margin: 2em 4em }
+
+table.docutils {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
+
+table.footnote {
+ border-left: solid 1px black;
+ margin-left: 1px }
+
+table.docutils td, table.docutils th,
+table.docinfo td, table.docinfo th {
+ padding-left: 0.5em ;
+ padding-right: 0.5em ;
+ vertical-align: top }
+
+table.docutils th.field-name, table.docinfo th.docinfo-name {
+ font-weight: bold ;
+ text-align: left ;
+ white-space: nowrap ;
+ padding-left: 0 }
+
+h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
+h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+ font-size: 100% }
+
+ul.auto-toc {
+ list-style-type: none }
+
+</style>
</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>
+<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="http://www.osl.iu.edu/research/pbgl/images/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<typename Graph, typename Param, typename Tag, typename Rest>
+void
+brandes_betweenness_centrality(const Graph& g,
+ const bgl_named_params<Param,Tag,Rest>& params);
+
+template<typename Graph, typename CentralityMap>
+void
+brandes_betweenness_centrality(const Graph& g, CentralityMap centrality);
+
+template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
+void
+brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map);
+
+// non-named parameter versions
+template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
+ typename IncomingMap, typename DistanceMap, typename DependencyMap,
+ typename PathCountMap, typename VertexIndexMap, typename Buffer>
+void
+brandes_betweenness_centrality(const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ Buffer sources,
+ typename property_traits<DistanceMap>::value_type delta);
+
+template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
+ typename IncomingMap, typename DistanceMap, typename DependencyMap,
+ typename PathCountMap, typename VertexIndexMap, typename WeightMap,
+ typename Buffer>
+void
+brandes_betweenness_centrality(const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ Buffer sources,
+ typename property_traits<WeightMap>::value_type delta,
+ WeightMap weight_map);
+
+// helper functions
+template<typename Graph, typename CentralityMap>
+typename property_traits<CentralityMap>::value_type
+central_point_dominance(const Graph& 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><<tt class="docutils literal"><span class="pre">boost/graph/distributed/betweenness_centrality.hpp</span></tt>></p>
+<p>also accessible from</p>
+<p><<tt class="docutils literal"><span class="pre">boost/graph/betweenness_centrality.hpp</span></tt>></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&</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-18 17:42 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.
+Generated on: 2009-05-26 17:48 UTC.
</div>
</body>
Modified: trunk/libs/graph_parallel/doc/html/index.html
==============================================================================
--- trunk/libs/graph_parallel/doc/html/index.html (original)
+++ trunk/libs/graph_parallel/doc/html/index.html 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -1,15 +1,289 @@
-<?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 Parallel Boost Graph Library</title>
-<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+<style type="text/css">
+
+/*
+:Author: David Goodger (goodger_at_[hidden])
+:Id: $Id: html4css1.css 5631 2008-08-24 13:01:23Z goodger $
+:Copyright: This stylesheet has been placed in the public domain.
+
+Default cascading style sheet for the HTML output of Docutils.
+
+See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
+customize this style sheet.
+*/
+
+/* used to remove borders from tables and images */
+.borderless, table.borderless td, table.borderless th {
+ border: 0 }
+
+table.borderless td, table.borderless th {
+ /* Override padding for "table.docutils td" with "! important".
+ The right padding separates the table cells. */
+ padding: 0 0.5em 0 0 ! important }
+
+.first {
+ /* Override more specific margin styles with "! important". */
+ margin-top: 0 ! important }
+
+.last, .with-subtitle {
+ margin-bottom: 0 ! important }
+
+.hidden {
+ display: none }
+
+a.toc-backref {
+ text-decoration: none ;
+ color: black }
+
+blockquote.epigraph {
+ margin: 2em 5em ; }
+
+dl.docutils dd {
+ margin-bottom: 0.5em }
+
+/* Uncomment (and remove this text!) to get bold-faced definition list terms
+dl.docutils dt {
+ font-weight: bold }
+*/
+
+div.abstract {
+ margin: 2em 5em }
+
+div.abstract p.topic-title {
+ font-weight: bold ;
+ text-align: center }
+
+div.admonition, div.attention, div.caution, div.danger, div.error,
+div.hint, div.important, div.note, div.tip, div.warning {
+ margin: 2em ;
+ border: medium outset ;
+ padding: 1em }
+
+div.admonition p.admonition-title, div.hint p.admonition-title,
+div.important p.admonition-title, div.note p.admonition-title,
+div.tip p.admonition-title {
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.attention p.admonition-title, div.caution p.admonition-title,
+div.danger p.admonition-title, div.error p.admonition-title,
+div.warning p.admonition-title {
+ color: red ;
+ font-weight: bold ;
+ font-family: sans-serif }
+
+/* Uncomment (and remove this text!) to get reduced vertical space in
+ compound paragraphs.
+div.compound .compound-first, div.compound .compound-middle {
+ margin-bottom: 0.5em }
+
+div.compound .compound-last, div.compound .compound-middle {
+ margin-top: 0.5em }
+*/
+
+div.dedication {
+ margin: 2em 5em ;
+ text-align: center ;
+ font-style: italic }
+
+div.dedication p.topic-title {
+ font-weight: bold ;
+ font-style: normal }
+
+div.figure {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+div.footer, div.header {
+ clear: both;
+ font-size: smaller }
+
+div.line-block {
+ display: block ;
+ margin-top: 1em ;
+ margin-bottom: 1em }
+
+div.line-block div.line-block {
+ margin-top: 0 ;
+ margin-bottom: 0 ;
+ margin-left: 1.5em }
+
+div.sidebar {
+ margin: 0 0 0.5em 1em ;
+ border: medium outset ;
+ padding: 1em ;
+ background-color: #ffffee ;
+ width: 40% ;
+ float: right ;
+ clear: right }
+
+div.sidebar p.rubric {
+ font-family: sans-serif ;
+ font-size: medium }
+
+div.system-messages {
+ margin: 5em }
+
+div.system-messages h1 {
+ color: red }
+
+div.system-message {
+ border: medium outset ;
+ padding: 1em }
+
+div.system-message p.system-message-title {
+ color: red ;
+ font-weight: bold }
+
+div.topic {
+ margin: 2em }
+
+h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
+h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
+ margin-top: 0.4em }
+
+h1.title {
+ text-align: center }
+
+h2.subtitle {
+ text-align: center }
+
+hr.docutils {
+ width: 75% }
+
+img.align-left {
+ clear: left }
+
+img.align-right {
+ clear: right }
+
+ol.simple, ul.simple {
+ margin-bottom: 1em }
+
+ol.arabic {
+ list-style: decimal }
+
+ol.loweralpha {
+ list-style: lower-alpha }
+
+ol.upperalpha {
+ list-style: upper-alpha }
+
+ol.lowerroman {
+ list-style: lower-roman }
+
+ol.upperroman {
+ list-style: upper-roman }
+
+p.attribution {
+ text-align: right ;
+ margin-left: 50% }
+
+p.caption {
+ font-style: italic }
+
+p.credits {
+ font-style: italic ;
+ font-size: smaller }
+
+p.label {
+ white-space: nowrap }
+
+p.rubric {
+ font-weight: bold ;
+ font-size: larger ;
+ color: maroon ;
+ text-align: center }
+
+p.sidebar-title {
+ font-family: sans-serif ;
+ font-weight: bold ;
+ font-size: larger }
+
+p.sidebar-subtitle {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+p.topic-title {
+ font-weight: bold }
+
+pre.address {
+ margin-bottom: 0 ;
+ margin-top: 0 ;
+ font: inherit }
+
+pre.literal-block, pre.doctest-block {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+span.classifier {
+ font-family: sans-serif ;
+ font-style: oblique }
+
+span.classifier-delimiter {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+span.interpreted {
+ font-family: sans-serif }
+
+span.option {
+ white-space: nowrap }
+
+span.pre {
+ white-space: pre }
+
+span.problematic {
+ color: red }
+
+span.section-subtitle {
+ /* font-size relative to parent (h1..h6 element) */
+ font-size: 80% }
+
+table.citation {
+ border-left: solid 1px gray;
+ margin-left: 1px }
+
+table.docinfo {
+ margin: 2em 4em }
+
+table.docutils {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
+
+table.footnote {
+ border-left: solid 1px black;
+ margin-left: 1px }
+
+table.docutils td, table.docutils th,
+table.docinfo td, table.docinfo th {
+ padding-left: 0.5em ;
+ padding-right: 0.5em ;
+ vertical-align: top }
+
+table.docutils th.field-name, table.docinfo th.docinfo-name {
+ font-weight: bold ;
+ text-align: left ;
+ white-space: nowrap ;
+ padding-left: 0 }
+
+h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
+h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+ font-size: 100% }
+
+ul.auto-toc {
+ list-style-type: none }
+
+</style>
</head>
<body>
<div class="document" id="logo-parallel-boost-graph-library">
-<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> Parallel Boost Graph Library</h1>
+<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="http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png" /></a> Parallel Boost Graph Library</h1>
<h2 class="subtitle" id="overview">Overview</h2>
<!-- Copyright (C) 2004-2009 The Trustees of Indiana University.
@@ -86,8 +360,8 @@
<ul class="simple">
<li><a class="reference external" href="rmat_generator.html">R-MAT generator</a></li>
<li><a class="reference external" href="sorted_rmat_generator.html">Sorted R-MAT generator</a></li>
-<li><a class="reference external" href="unique_rmat_generator.html">Unique R-MAT generator</a></li>
<li><a class="reference external" href="sorted_unique_rmat_generator.html">Sorted unique R-MAT generator</a></li>
+<li><a class="reference external" href="unique_rmat_generator.html">Unique R-MAT generator</a></li>
<li><a class="reference external" href="scalable_rmat_generator.html">Scalable R-MAT generator</a></li>
<li><a class="reference external" href="http://www.boost.org/libs/graph/doc/erdos_renyi_generator.html">Erdos-Renyi generator</a></li>
<li><a class="reference external" href="http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html">Sorted Erdos-Renyi generator</a></li>
@@ -128,6 +402,7 @@
<li><a class="reference external" href="fruchterman_reingold.html">Fruchterman Reingold force-directed layout</a></li>
<li><a class="reference external" href="st_connected.html">s-t connectivity</a></li>
<li><a class="reference external" href="betweenness_centrality.html">Betweenness centrality</a></li>
+<li><a class="reference external" href="non_distributed_betweenness_centrality.html">Non-distributed betweenness centrality</a></li>
</ul>
</li>
</ul>
@@ -138,8 +413,7 @@
</div>
<div class="footer">
<hr class="footer" />
-Generated on: 2009-05-18 17:42 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.
+Generated on: 2009-05-26 17:55 UTC.
</div>
</body>
Added: trunk/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -0,0 +1,496 @@
+<!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 Non-Distributed Betweenness Centrality</title>
+<style type="text/css">
+
+/*
+:Author: David Goodger (goodger_at_[hidden])
+:Id: $Id: html4css1.css 5631 2008-08-24 13:01:23Z goodger $
+:Copyright: This stylesheet has been placed in the public domain.
+
+Default cascading style sheet for the HTML output of Docutils.
+
+See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
+customize this style sheet.
+*/
+
+/* used to remove borders from tables and images */
+.borderless, table.borderless td, table.borderless th {
+ border: 0 }
+
+table.borderless td, table.borderless th {
+ /* Override padding for "table.docutils td" with "! important".
+ The right padding separates the table cells. */
+ padding: 0 0.5em 0 0 ! important }
+
+.first {
+ /* Override more specific margin styles with "! important". */
+ margin-top: 0 ! important }
+
+.last, .with-subtitle {
+ margin-bottom: 0 ! important }
+
+.hidden {
+ display: none }
+
+a.toc-backref {
+ text-decoration: none ;
+ color: black }
+
+blockquote.epigraph {
+ margin: 2em 5em ; }
+
+dl.docutils dd {
+ margin-bottom: 0.5em }
+
+/* Uncomment (and remove this text!) to get bold-faced definition list terms
+dl.docutils dt {
+ font-weight: bold }
+*/
+
+div.abstract {
+ margin: 2em 5em }
+
+div.abstract p.topic-title {
+ font-weight: bold ;
+ text-align: center }
+
+div.admonition, div.attention, div.caution, div.danger, div.error,
+div.hint, div.important, div.note, div.tip, div.warning {
+ margin: 2em ;
+ border: medium outset ;
+ padding: 1em }
+
+div.admonition p.admonition-title, div.hint p.admonition-title,
+div.important p.admonition-title, div.note p.admonition-title,
+div.tip p.admonition-title {
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.attention p.admonition-title, div.caution p.admonition-title,
+div.danger p.admonition-title, div.error p.admonition-title,
+div.warning p.admonition-title {
+ color: red ;
+ font-weight: bold ;
+ font-family: sans-serif }
+
+/* Uncomment (and remove this text!) to get reduced vertical space in
+ compound paragraphs.
+div.compound .compound-first, div.compound .compound-middle {
+ margin-bottom: 0.5em }
+
+div.compound .compound-last, div.compound .compound-middle {
+ margin-top: 0.5em }
+*/
+
+div.dedication {
+ margin: 2em 5em ;
+ text-align: center ;
+ font-style: italic }
+
+div.dedication p.topic-title {
+ font-weight: bold ;
+ font-style: normal }
+
+div.figure {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+div.footer, div.header {
+ clear: both;
+ font-size: smaller }
+
+div.line-block {
+ display: block ;
+ margin-top: 1em ;
+ margin-bottom: 1em }
+
+div.line-block div.line-block {
+ margin-top: 0 ;
+ margin-bottom: 0 ;
+ margin-left: 1.5em }
+
+div.sidebar {
+ margin: 0 0 0.5em 1em ;
+ border: medium outset ;
+ padding: 1em ;
+ background-color: #ffffee ;
+ width: 40% ;
+ float: right ;
+ clear: right }
+
+div.sidebar p.rubric {
+ font-family: sans-serif ;
+ font-size: medium }
+
+div.system-messages {
+ margin: 5em }
+
+div.system-messages h1 {
+ color: red }
+
+div.system-message {
+ border: medium outset ;
+ padding: 1em }
+
+div.system-message p.system-message-title {
+ color: red ;
+ font-weight: bold }
+
+div.topic {
+ margin: 2em }
+
+h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
+h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
+ margin-top: 0.4em }
+
+h1.title {
+ text-align: center }
+
+h2.subtitle {
+ text-align: center }
+
+hr.docutils {
+ width: 75% }
+
+img.align-left {
+ clear: left }
+
+img.align-right {
+ clear: right }
+
+ol.simple, ul.simple {
+ margin-bottom: 1em }
+
+ol.arabic {
+ list-style: decimal }
+
+ol.loweralpha {
+ list-style: lower-alpha }
+
+ol.upperalpha {
+ list-style: upper-alpha }
+
+ol.lowerroman {
+ list-style: lower-roman }
+
+ol.upperroman {
+ list-style: upper-roman }
+
+p.attribution {
+ text-align: right ;
+ margin-left: 50% }
+
+p.caption {
+ font-style: italic }
+
+p.credits {
+ font-style: italic ;
+ font-size: smaller }
+
+p.label {
+ white-space: nowrap }
+
+p.rubric {
+ font-weight: bold ;
+ font-size: larger ;
+ color: maroon ;
+ text-align: center }
+
+p.sidebar-title {
+ font-family: sans-serif ;
+ font-weight: bold ;
+ font-size: larger }
+
+p.sidebar-subtitle {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+p.topic-title {
+ font-weight: bold }
+
+pre.address {
+ margin-bottom: 0 ;
+ margin-top: 0 ;
+ font: inherit }
+
+pre.literal-block, pre.doctest-block {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+span.classifier {
+ font-family: sans-serif ;
+ font-style: oblique }
+
+span.classifier-delimiter {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+span.interpreted {
+ font-family: sans-serif }
+
+span.option {
+ white-space: nowrap }
+
+span.pre {
+ white-space: pre }
+
+span.problematic {
+ color: red }
+
+span.section-subtitle {
+ /* font-size relative to parent (h1..h6 element) */
+ font-size: 80% }
+
+table.citation {
+ border-left: solid 1px gray;
+ margin-left: 1px }
+
+table.docinfo {
+ margin: 2em 4em }
+
+table.docutils {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
+
+table.footnote {
+ border-left: solid 1px black;
+ margin-left: 1px }
+
+table.docutils td, table.docutils th,
+table.docinfo td, table.docinfo th {
+ padding-left: 0.5em ;
+ padding-right: 0.5em ;
+ vertical-align: top }
+
+table.docutils th.field-name, table.docinfo th.docinfo-name {
+ font-weight: bold ;
+ text-align: left ;
+ white-space: nowrap ;
+ padding-left: 0 }
+
+h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
+h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+ font-size: 100% }
+
+ul.auto-toc {
+ list-style-type: none }
+
+</style>
+</head>
+<body>
+<div class="document" id="logo-non-distributed-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="http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png" /></a> Non-Distributed 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<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest>
+void
+non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
+ const bgl_named_params<Param,Tag,Rest>& params);
+
+template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename Buffer>
+void
+non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
+ CentralityMap centrality, Buffer sources);
+
+template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename EdgeCentralityMap, typename Buffer>
+void
+non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ Buffer sources);
+
+// non-named parameter versions
+template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap,
+ typename DependencyMap, typename PathCountMap, typename VertexIndexMap,
+ typename Buffer>
+void
+non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
+ const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ Buffer sources);
+
+template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap,
+ typename DependencyMap, typename PathCountMap, typename VertexIndexMap,
+ typename WeightMap, typename Buffer>
+void
+non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
+ const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ WeightMap weight_map,
+ Buffer sources);
+
+// helper functions
+template<typename Graph, typename CentralityMap>
+typename property_traits<CentralityMap>::value_type
+central_point_dominance(const Graph& g, CentralityMap centrality);
+</pre>
+<p>The <tt class="docutils literal"><span class="pre">non_distributed_betweenness_centrality()</span></tt> function computes the
+betweenness centrality of the vertices and edges in a graph. The name
+is somewhat confusing, the graph <tt class="docutils literal"><span class="pre">g</span></tt> is not a distributed graph,
+however the algorithm does run in parallel. Rather than parallelizing
+the individual shortest paths calculations that are required by
+betweenness centrality, this variant of the algorithm performs the
+shortest paths calculations in parallel with each process in <tt class="docutils literal"><span class="pre">pg</span></tt>
+calculating the shortest path from a different set of source vertices
+using the BGL's implementation of <a class="reference external" href="http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html">Dijkstra shortest paths</a>. Each
+process accumulates into it's local centrality map and once all the
+shortest paths calculations are performed a reduction is performed to
+combine the centrality from all the processes.</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="#parameters" id="id2">Parameters</a></li>
+<li><a class="reference internal" href="#complexity" id="id3">Complexity</a></li>
+<li><a class="reference internal" href="#algorithm-description" id="id4">Algorithm Description</a></li>
+</ul>
+</div>
+<div class="section" id="where-defined">
+<h1><a class="toc-backref" href="#id1">Where Defined</a></h1>
+<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/betweenness_centrality.hpp</span></tt>></p>
+</div>
+<div class="section" id="parameters">
+<h1><a class="toc-backref" href="#id2">Parameters</a></h1>
+<dl class="docutils">
+<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">ProcessGroup&</span> <span class="pre">pg</span></tt></dt>
+<dd>The process group over which the the processes involved in
+betweenness centrality communicate. The process group type must
+model the <a class="reference external" href="process_group.html">Process Group</a> concept.</dd>
+<dt>IN: <tt class="docutils literal"><span class="pre">const</span> <span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
+<dd>The graph type must be a model of the <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> concept.</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 one is 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 key type of the
+<tt class="docutils literal"><span class="pre">CentralityMap</span></tt> 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 one is
+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 key type of the
+<tt class="docutils literal"><span class="pre">EdgeCentralityMap</span></tt> 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. Its key type must be the
+graph's vertex descriptor type and its value type must be the
+graph's edge 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 edge 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. 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. 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">PathCountMap</span> <span class="pre">path_count</span></tt></dt>
+<dd><p class="first">The path count map records the number of shortest paths each vertex
+is on during the centrality calculation portion of the algorithm.
+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 graph's degree size type.</dd>
+</dl>
+</dd>
+<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="#id3">Complexity</a></h1>
+<p>Each of the shortest paths calculations is <em>O(V log V)</em> and each of
+them may be run in parallel (one per process in <tt class="docutils literal"><span class="pre">pg</span></tt>). The
+reduction phase to calculate the total centrality at the end of the
+shortest paths phase is <em>O(V log V)</em>.</p>
+</div>
+<div class="section" id="algorithm-description">
+<h1><a class="toc-backref" href="#id4">Algorithm Description</a></h1>
+<p>The algorithm uses a non-distributed (sequential) graph, as well as
+non-distributed property maps. Each process contains a separate copy
+of the sequential graph <tt class="docutils literal"><span class="pre">g</span></tt>. In order for the algorithm to be
+correct, these copies of <tt class="docutils literal"><span class="pre">g</span></tt> must be identical. The <tt class="docutils literal"><span class="pre">sources</span></tt>
+buffer contains the vertices to use as the source of single source
+shortest paths calculations when approximating betweenness centrality
+using a subset of the vertices in the graph. If <tt class="docutils literal"><span class="pre">sources</span></tt> is empty
+then a complete betweenness centrality calculation is performed using
+all vertices.</p>
+<p>In the sequential phase of the algorithm each process computes
+shortest paths from a subset of the vertices in the graph using the
+Brandes shortest paths methods from the BGL's betweenness centrality
+implementation. In the parallel phase of the algorithm a reduction is
+performed to sum the values computed by each process for all vertices
+in the graph.</p>
+<p>Either weighted or unweighted betweenness centrality is calculated
+depending on whether a <tt class="docutils literal"><span class="pre">WeightMap</span></tt> is passed.</p>
+<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-26 17:48 UTC.
+
+</div>
+</body>
+</html>
Modified: trunk/libs/graph_parallel/doc/html/sorted_unique_rmat_generator.html
==============================================================================
--- trunk/libs/graph_parallel/doc/html/sorted_unique_rmat_generator.html (original)
+++ trunk/libs/graph_parallel/doc/html/sorted_unique_rmat_generator.html 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -1,15 +1,289 @@
-<?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 Sorted unique R-MAT generator</title>
-<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
+<style type="text/css">
+
+/*
+:Author: David Goodger (goodger_at_[hidden])
+:Id: $Id: html4css1.css 5631 2008-08-24 13:01:23Z goodger $
+:Copyright: This stylesheet has been placed in the public domain.
+
+Default cascading style sheet for the HTML output of Docutils.
+
+See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
+customize this style sheet.
+*/
+
+/* used to remove borders from tables and images */
+.borderless, table.borderless td, table.borderless th {
+ border: 0 }
+
+table.borderless td, table.borderless th {
+ /* Override padding for "table.docutils td" with "! important".
+ The right padding separates the table cells. */
+ padding: 0 0.5em 0 0 ! important }
+
+.first {
+ /* Override more specific margin styles with "! important". */
+ margin-top: 0 ! important }
+
+.last, .with-subtitle {
+ margin-bottom: 0 ! important }
+
+.hidden {
+ display: none }
+
+a.toc-backref {
+ text-decoration: none ;
+ color: black }
+
+blockquote.epigraph {
+ margin: 2em 5em ; }
+
+dl.docutils dd {
+ margin-bottom: 0.5em }
+
+/* Uncomment (and remove this text!) to get bold-faced definition list terms
+dl.docutils dt {
+ font-weight: bold }
+*/
+
+div.abstract {
+ margin: 2em 5em }
+
+div.abstract p.topic-title {
+ font-weight: bold ;
+ text-align: center }
+
+div.admonition, div.attention, div.caution, div.danger, div.error,
+div.hint, div.important, div.note, div.tip, div.warning {
+ margin: 2em ;
+ border: medium outset ;
+ padding: 1em }
+
+div.admonition p.admonition-title, div.hint p.admonition-title,
+div.important p.admonition-title, div.note p.admonition-title,
+div.tip p.admonition-title {
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.attention p.admonition-title, div.caution p.admonition-title,
+div.danger p.admonition-title, div.error p.admonition-title,
+div.warning p.admonition-title {
+ color: red ;
+ font-weight: bold ;
+ font-family: sans-serif }
+
+/* Uncomment (and remove this text!) to get reduced vertical space in
+ compound paragraphs.
+div.compound .compound-first, div.compound .compound-middle {
+ margin-bottom: 0.5em }
+
+div.compound .compound-last, div.compound .compound-middle {
+ margin-top: 0.5em }
+*/
+
+div.dedication {
+ margin: 2em 5em ;
+ text-align: center ;
+ font-style: italic }
+
+div.dedication p.topic-title {
+ font-weight: bold ;
+ font-style: normal }
+
+div.figure {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+div.footer, div.header {
+ clear: both;
+ font-size: smaller }
+
+div.line-block {
+ display: block ;
+ margin-top: 1em ;
+ margin-bottom: 1em }
+
+div.line-block div.line-block {
+ margin-top: 0 ;
+ margin-bottom: 0 ;
+ margin-left: 1.5em }
+
+div.sidebar {
+ margin: 0 0 0.5em 1em ;
+ border: medium outset ;
+ padding: 1em ;
+ background-color: #ffffee ;
+ width: 40% ;
+ float: right ;
+ clear: right }
+
+div.sidebar p.rubric {
+ font-family: sans-serif ;
+ font-size: medium }
+
+div.system-messages {
+ margin: 5em }
+
+div.system-messages h1 {
+ color: red }
+
+div.system-message {
+ border: medium outset ;
+ padding: 1em }
+
+div.system-message p.system-message-title {
+ color: red ;
+ font-weight: bold }
+
+div.topic {
+ margin: 2em }
+
+h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
+h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
+ margin-top: 0.4em }
+
+h1.title {
+ text-align: center }
+
+h2.subtitle {
+ text-align: center }
+
+hr.docutils {
+ width: 75% }
+
+img.align-left {
+ clear: left }
+
+img.align-right {
+ clear: right }
+
+ol.simple, ul.simple {
+ margin-bottom: 1em }
+
+ol.arabic {
+ list-style: decimal }
+
+ol.loweralpha {
+ list-style: lower-alpha }
+
+ol.upperalpha {
+ list-style: upper-alpha }
+
+ol.lowerroman {
+ list-style: lower-roman }
+
+ol.upperroman {
+ list-style: upper-roman }
+
+p.attribution {
+ text-align: right ;
+ margin-left: 50% }
+
+p.caption {
+ font-style: italic }
+
+p.credits {
+ font-style: italic ;
+ font-size: smaller }
+
+p.label {
+ white-space: nowrap }
+
+p.rubric {
+ font-weight: bold ;
+ font-size: larger ;
+ color: maroon ;
+ text-align: center }
+
+p.sidebar-title {
+ font-family: sans-serif ;
+ font-weight: bold ;
+ font-size: larger }
+
+p.sidebar-subtitle {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+p.topic-title {
+ font-weight: bold }
+
+pre.address {
+ margin-bottom: 0 ;
+ margin-top: 0 ;
+ font: inherit }
+
+pre.literal-block, pre.doctest-block {
+ margin-left: 2em ;
+ margin-right: 2em }
+
+span.classifier {
+ font-family: sans-serif ;
+ font-style: oblique }
+
+span.classifier-delimiter {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+span.interpreted {
+ font-family: sans-serif }
+
+span.option {
+ white-space: nowrap }
+
+span.pre {
+ white-space: pre }
+
+span.problematic {
+ color: red }
+
+span.section-subtitle {
+ /* font-size relative to parent (h1..h6 element) */
+ font-size: 80% }
+
+table.citation {
+ border-left: solid 1px gray;
+ margin-left: 1px }
+
+table.docinfo {
+ margin: 2em 4em }
+
+table.docutils {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
+
+table.footnote {
+ border-left: solid 1px black;
+ margin-left: 1px }
+
+table.docutils td, table.docutils th,
+table.docinfo td, table.docinfo th {
+ padding-left: 0.5em ;
+ padding-right: 0.5em ;
+ vertical-align: top }
+
+table.docutils th.field-name, table.docinfo th.docinfo-name {
+ font-weight: bold ;
+ text-align: left ;
+ white-space: nowrap ;
+ padding-left: 0 }
+
+h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
+h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+ font-size: 100% }
+
+ul.auto-toc {
+ list-style-type: none }
+
+</style>
</head>
<body>
<div class="document" id="logo-sorted-unique-r-mat-generator">
-<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> Sorted unique R-MAT generator</h1>
+<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="http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png" /></a> Sorted unique R-MAT generator</h1>
<!-- Copyright (C) 2004-2009 The Trustees of Indiana University.
Use, modification and distribution is subject to the Boost Software
@@ -132,8 +406,7 @@
</div>
<div class="footer">
<hr class="footer" />
-Generated on: 2009-05-18 17:42 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.
+Generated on: 2009-05-26 17:48 UTC.
</div>
</body>
Modified: trunk/libs/graph_parallel/doc/index.rst
==============================================================================
--- trunk/libs/graph_parallel/doc/index.rst (original)
+++ trunk/libs/graph_parallel/doc/index.rst 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -54,8 +54,8 @@
- `R-MAT generator`_
- `Sorted R-MAT generator`_
- - `Unique R-MAT generator`_
- `Sorted unique R-MAT generator`_
+ - `Unique R-MAT generator`_
- `Scalable R-MAT generator`_
- `Erdos-Renyi generator`_
- `Sorted Erdos-Renyi generator`_
@@ -93,6 +93,7 @@
- `Fruchterman Reingold force-directed layout`_
- `s-t connectivity`_
- `Betweenness centrality`_
+ - `Non-distributed betweenness centrality`_
----------------------------------------------------------------------------
@@ -100,7 +101,7 @@
Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine
-.. |Logo| image:: pbgl-logo.png
+.. |Logo| image:: http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png
:align: middle
:alt: Parallel BGL
:target: http://www.osl.iu.edu/research/pbgl
@@ -123,8 +124,8 @@
.. _Distributed property map: distributed_property_map.html
.. _R-MAT generator: rmat_generator.html
.. _Sorted R-MAT generator: sorted_rmat_generator.html
+.. _Sorted Unique R-MAT generator: sorted_unique_rmat_generator.html
.. _Unique R-MAT generator: unique_rmat_generator.html
-.. _Sorted unique R-MAT generator: sorted_unique_rmat_generator.html
.. _Scalable R-MAT generator: scalable_rmat_generator.html
.. _Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/erdos_renyi_generator.html
.. _Sorted Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html
@@ -156,3 +157,4 @@
.. _Fruchterman Reingold force-directed layout: fruchterman_reingold.html
.. _s-t connectivity: st_connected.html
.. _Betweenness centrality: betweenness_centrality.html
+.. _Non-distributed betweenness centrality: non_distributed_betweenness_centrality.html
Added: trunk/libs/graph_parallel/doc/non_distributed_betweenness_centrality.rst
==============================================================================
--- (empty file)
+++ trunk/libs/graph_parallel/doc/non_distributed_betweenness_centrality.rst 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -0,0 +1,219 @@
+.. Copyright (C) 2004-2009 The Trustees of Indiana University.
+ Use, modification and distribution is subject to the Boost Software
+ License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+
+=============================================
+|Logo| Non-Distributed Betweenness Centrality
+=============================================
+
+::
+
+ // named parameter versions
+ template<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest>
+ void
+ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
+ const bgl_named_params<Param,Tag,Rest>& params);
+
+ template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename Buffer>
+ void
+ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
+ CentralityMap centrality, Buffer sources);
+
+ template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename EdgeCentralityMap, typename Buffer>
+ void
+ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ Buffer sources);
+
+ // non-named parameter versions
+ template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap,
+ typename DependencyMap, typename PathCountMap, typename VertexIndexMap,
+ typename Buffer>
+ void
+ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
+ const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ Buffer sources);
+
+ template<typename ProcessGroup, typename Graph, typename CentralityMap,
+ typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap,
+ typename DependencyMap, typename PathCountMap, typename VertexIndexMap,
+ typename WeightMap, typename Buffer>
+ void
+ non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
+ const Graph& g,
+ CentralityMap centrality,
+ EdgeCentralityMap edge_centrality_map,
+ IncomingMap incoming,
+ DistanceMap distance,
+ DependencyMap dependency,
+ PathCountMap path_count,
+ VertexIndexMap vertex_index,
+ WeightMap weight_map,
+ Buffer sources);
+
+ // helper functions
+ template<typename Graph, typename CentralityMap>
+ typename property_traits<CentralityMap>::value_type
+ central_point_dominance(const Graph& g, CentralityMap centrality);
+
+The ``non_distributed_betweenness_centrality()`` function computes the
+betweenness centrality of the vertices and edges in a graph. The name
+is somewhat confusing, the graph ``g`` is not a distributed graph,
+however the algorithm does run in parallel. Rather than parallelizing
+the individual shortest paths calculations that are required by
+betweenness centrality, this variant of the algorithm performs the
+shortest paths calculations in parallel with each process in ``pg``
+calculating the shortest path from a different set of source vertices
+using the BGL's implementation of `Dijkstra shortest paths`_. Each
+process accumulates into it's local centrality map and once all the
+shortest paths calculations are performed a reduction is performed to
+combine the centrality from all the processes.
+
+.. contents::
+
+Where Defined
+-------------
+<``boost/graph/distributed/betweenness_centrality.hpp``>
+
+Parameters
+----------
+
+IN: ``const ProcessGroup& pg``
+ The process group over which the the processes involved in
+ betweenness centrality communicate. The process group type must
+ model the `Process Group`_ concept.
+
+IN: ``const Graph& g``
+ The graph type must be a model of the `Incidence Graph`_ concept.
+
+IN: ``CentralityMap centrality``
+ A centrality map may be supplied to the algorithm, if one is not
+ supplied a ``dummy_property_map`` will be used and no vertex
+ centrality information will be recorded. The key type of the
+ ``CentralityMap`` must be the graph's vertex descriptor type.
+
+ **Default**: A ``dummy_property_map``.
+
+IN: ``EdgeCentralityMap edge_centrality_map``
+ An edge centrality map may be supplied to the algorithm, if one is
+ not supplied a ``dummy_property_map`` will be used and no edge
+ centrality information will be recorded. The key type of the
+ ``EdgeCentralityMap`` must be the graph's vertex descriptor type.
+
+ **Default**: A ``dummy_property_map``.
+
+IN: ``IncomingMap incoming``
+ The incoming map contains the incoming edges to a vertex that are
+ part of shortest paths to that vertex. Its key type must be the
+ graph's vertex descriptor type and its value type must be the
+ graph's edge descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of ``std::vector`` of the graph's edge descriptor
+ type.
+
+IN: ``DistanceMap distance``
+ The distance map records the distance to vertices during the
+ shortest paths portion of the algorithm. Its key type must be the
+ graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of the value type of the ``CentralityMap``.
+
+IN: ``DependencyMap dependency``
+ The dependency map records the dependency of each vertex during the
+ centrality calculation portion of the algorithm. Its key type must
+ be the graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of the value type of the ``CentralityMap``.
+
+IN: ``PathCountMap path_count``
+ The path count map records the number of shortest paths each vertex
+ is on during the centrality calculation portion of the algorithm.
+ Its key type must be the graph's vertex descriptor type.
+
+ **Default**: An ``iterator_property_map`` created from a
+ ``std::vector`` of the graph's degree size type.
+
+IN: ``VertexIndexMap vertex_index``
+ A model of `Readable Property Map`_ whose key type is the vertex
+ descriptor type of the graph ``g`` and whose value type is an
+ integral type. The property map should map from vertices to their
+ (local) indices in the range *[0, num_vertices(g))*.
+
+ **Default**: ``get(vertex_index, g)``
+
+IN: ``WeightMap weight_map``
+ A model of `Readable Property Map`_ whose key type is the edge
+ descriptor type of the graph ``g``. If not supplied the betweenness
+ centrality calculation will be unweighted.
+
+IN: ``Buffer sources``
+ A model of Buffer_ containing the starting vertices for the
+ algorithm. If ``sources`` is empty a complete betweenness
+ centrality calculation using all vertices in ``g`` will be
+ performed. The value type of the Buffer must be the graph's vertex
+ descriptor type.
+
+ **Default**: An empty ``boost::queue`` of int.
+
+Complexity
+----------
+
+Each of the shortest paths calculations is *O(V log V)* and each of
+them may be run in parallel (one per process in ``pg``). The
+reduction phase to calculate the total centrality at the end of the
+shortest paths phase is *O(V log V)*.
+
+Algorithm Description
+---------------------
+
+The algorithm uses a non-distributed (sequential) graph, as well as
+non-distributed property maps. Each process contains a separate copy
+of the sequential graph ``g``. In order for the algorithm to be
+correct, these copies of ``g`` must be identical. The ``sources``
+buffer contains the vertices to use as the source of single source
+shortest paths calculations when approximating betweenness centrality
+using a subset of the vertices in the graph. If ``sources`` is empty
+then a complete betweenness centrality calculation is performed using
+all vertices.
+
+In the sequential phase of the algorithm each process computes
+shortest paths from a subset of the vertices in the graph using the
+Brandes shortest paths methods from the BGL's betweenness centrality
+implementation. In the parallel phase of the algorithm a reduction is
+performed to sum the values computed by each process for all vertices
+in the graph.
+
+Either weighted or unweighted betweenness centrality is calculated
+depending on whether a ``WeightMap`` is passed.
+
+-----------------------------------------------------------------------------
+
+Copyright (C) 2009 The Trustees of Indiana University.
+
+Authors: Nick Edmonds and Andrew Lumsdaine
+
+.. |Logo| image:: http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png
+ :align: middle
+ :alt: Parallel BGL
+ :target: http://www.osl.iu.edu/research/pbgl
+
+.. _Process Group: process_group.html
+.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
+.. _Dijkstra shortest paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
+.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
+.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
\ No newline at end of file
Modified: trunk/libs/graph_parallel/doc/sorted_unique_rmat_generator.rst
==============================================================================
--- trunk/libs/graph_parallel/doc/sorted_unique_rmat_generator.rst (original)
+++ trunk/libs/graph_parallel/doc/sorted_unique_rmat_generator.rst 2009-05-27 19:35:34 EDT (Wed, 27 May 2009)
@@ -128,7 +128,7 @@
Authors: Nick Edmonds and Andrew Lumsdaine
-.. |Logo| image:: pbgl-logo.png
+.. |Logo| image:: http://www.osl.iu.edu/research/pbgl/images/pbgl-logo.png
:align: middle
:alt: Parallel BGL
:target: http://www.osl.iu.edu/research/pbgl
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
