1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>Parallel BGL Vertex List Graph Adaptor</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-vertex-list-graph-adaptor"> 12<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> Vertex List Graph Adaptor</h1> 13 14<!-- Copyright (C) 2004-2008 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<pre class="literal-block"> 19template<typename Graph, typename GlobalIndexMap> 20class vertex_list_adaptor 21{ 22public: 23 vertex_list_adaptor(const Graph& g, 24 const GlobalIndexMap& index_map = GlobalIndexMap()); 25}; 26 27template<typename Graph, typename GlobalIndexMap> 28vertex_list_adaptor<Graph, GlobalIndexMap> 29make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map); 30 31template<typename Graph> 32vertex_list_adaptor<Graph, *unspecified*> 33make_vertex_list_adaptor(const Graph& g); 34</pre> 35<p>The vertex list graph adaptor adapts any model of <a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List 36Graph</a> in a <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a>. In the former type of graph, the 37set of vertices is distributed across the process group, so no 38process has access to all vertices. In the latter type of graph, 39however, every process has access to every vertex in the graph. This 40is required by some distributed algorithms, such as the 41implementations of <a class="reference external" href="dehne_gotz_min_spanning_tree.html">Minimum spanning tree</a> algorithms.</p> 42<div class="contents topic" id="contents"> 43<p class="topic-title first">Contents</p> 44<ul class="simple"> 45<li><a class="reference internal" href="#where-defined" id="id1">Where Defined</a></li> 46<li><a class="reference internal" href="#class-template-vertex-list-adaptor" id="id2">Class template <tt class="docutils literal"><span class="pre">vertex_list_adaptor</span></tt></a></li> 47<li><a class="reference internal" href="#function-templates-make-vertex-list-adaptor" id="id3">Function templates <tt class="docutils literal"><span class="pre">make_vertex_list_adaptor</span></tt></a><ul> 48<li><a class="reference internal" href="#parameters" id="id4">Parameters</a></li> 49<li><a class="reference internal" href="#complexity" id="id5">Complexity</a></li> 50</ul> 51</li> 52</ul> 53</div> 54<div class="section" id="where-defined"> 55<h1><a class="toc-backref" href="#id1">Where Defined</a></h1> 56<p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/vertex_list_adaptor.hpp</span></tt>></p> 57</div> 58<div class="section" id="class-template-vertex-list-adaptor"> 59<h1><a class="toc-backref" href="#id2">Class template <tt class="docutils literal"><span class="pre">vertex_list_adaptor</span></tt></a></h1> 60<p>The <tt class="docutils literal"><span class="pre">vertex_list_adaptor</span></tt> class template takes a <a class="reference external" href="DistributedVertexListGraph.html">Distributed 61Vertex List Graph</a> and a mapping from vertex descriptors to global 62vertex indices, which must be in the range <em>[0, n)</em>, where <em>n</em> is the 63number of vertices in the entire graph. The mapping is a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable 64Property Map</a> whose key type is a vertex descriptor.</p> 65<p>The vertex list adaptor stores only a reference to the underlying 66graph, forwarding all operations not related to the vertex list on to 67the underlying graph. For instance, if the underlying graph models 68<a class="reference external" href="http://www.boost.org/libs/graph/doc/AdjacencyGraph.html">Adjacency Graph</a>, then the adaptor will also model <a class="reference external" href="http://www.boost.org/libs/graph/doc/AdjacencyGraph.html">Adjacency 69Graph</a>. Note, however, that no modifications to the underlying graph 70can occur through the vertex list adaptor. Modifications made to the 71underlying graph directly will be reflected in the vertex list 72adaptor, but modifications that add or remove vertices invalidate the 73vertex list adaptor. Additionally, the vertex list adaptor provides 74access to the global index map via the <tt class="docutils literal"><span class="pre">vertex_index</span></tt> property.</p> 75<p>On construction, the vertex list adaptor performs an all-gather 76operation to create a list of all vertices in the graph within each 77process. It is this list that is accessed via <em>vertices</em> and the 78length of this list that is accessed via <em>num_vertices</em>. Due to the 79all-gather operation, the creation of this adaptor is a collective 80operation.</p> 81</div> 82<div class="section" id="function-templates-make-vertex-list-adaptor"> 83<h1><a class="toc-backref" href="#id3">Function templates <tt class="docutils literal"><span class="pre">make_vertex_list_adaptor</span></tt></a></h1> 84<p>These function templates construct a vertex list adaptor from a graph 85and, optionally, a property map that maps vertices to global index 86numbers.</p> 87<div class="section" id="parameters"> 88<h2><a class="toc-backref" href="#id4">Parameters</a></h2> 89<dl class="docutils"> 90<dt>IN: <tt class="docutils literal"><span class="pre">Graph&</span> <span class="pre">g</span></tt></dt> 91<dd>The graph type must be a model of <a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List Graph</a>.</dd> 92<dt>IN: <tt class="docutils literal"><span class="pre">GlobalIndexMap</span> <span class="pre">index_map</span></tt></dt> 93<dd><p class="first">A <a class="reference external" href="distributed_property_map.html">Distributed property map</a> whose type must model <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable 94property map</a> that maps from vertices to a global index. If 95provided, this map must be initialized prior to be passed to the 96vertex list adaptor.</p> 97<p class="last"><strong>Default:</strong> A property map of unspecified type constructed from a 98distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> that uses the 99<tt class="docutils literal"><span class="pre">vertex_index</span></tt> property map of the underlying graph and a vector 100of <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt>.</p> 101</dd> 102</dl> 103</div> 104<div class="section" id="complexity"> 105<h2><a class="toc-backref" href="#id5">Complexity</a></h2> 106<p>These operations require <em>O(n)</em> time, where <em>n</em> is the number of 107vertices in the graph, and <em>O(n)</em> communication per node in the BSP model.</p> 108<hr class="docutils" /> 109<p>Copyright (C) 2004 The Trustees of Indiana University.</p> 110<p>Authors: Douglas Gregor and Andrew Lumsdaine</p> 111</div> 112</div> 113</div> 114<div class="footer"> 115<hr class="footer" /> 116Generated on: 2009-05-31 00:21 UTC. 117Generated 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. 118 119</div> 120</body> 121</html> 122
