mirror of
https://github.com/boostorg/graph_parallel.git
synced 2026-01-19 16:22:15 +00:00
122 lines
7.6 KiB
HTML
122 lines
7.6 KiB
HTML
<?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 Vertex List Graph Adaptor</title>
|
|
<link rel="stylesheet" href="../../../../rst.css" type="text/css" />
|
|
</head>
|
|
<body>
|
|
<div class="document" id="logo-vertex-list-graph-adaptor">
|
|
<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>
|
|
|
|
<!-- 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">
|
|
template<typename Graph, typename GlobalIndexMap>
|
|
class vertex_list_adaptor
|
|
{
|
|
public:
|
|
vertex_list_adaptor(const Graph& g,
|
|
const GlobalIndexMap& index_map = GlobalIndexMap());
|
|
};
|
|
|
|
template<typename Graph, typename GlobalIndexMap>
|
|
vertex_list_adaptor<Graph, GlobalIndexMap>
|
|
make_vertex_list_adaptor(const Graph& g, const GlobalIndexMap& index_map);
|
|
|
|
template<typename Graph>
|
|
vertex_list_adaptor<Graph, *unspecified*>
|
|
make_vertex_list_adaptor(const Graph& g);
|
|
</pre>
|
|
<p>The vertex list graph adaptor adapts any model of <a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List
|
|
Graph</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
|
|
set of vertices is distributed across the process group, so no
|
|
process has access to all vertices. In the latter type of graph,
|
|
however, every process has access to every vertex in the graph. This
|
|
is required by some distributed algorithms, such as the
|
|
implementations of <a class="reference external" href="dehne_gotz_min_spanning_tree.html">Minimum spanning tree</a> algorithms.</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="#class-template-vertex-list-adaptor" id="id2">Class template <tt class="docutils literal"><span class="pre">vertex_list_adaptor</span></tt></a></li>
|
|
<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>
|
|
<li><a class="reference internal" href="#parameters" id="id4">Parameters</a></li>
|
|
<li><a class="reference internal" href="#complexity" id="id5">Complexity</a></li>
|
|
</ul>
|
|
</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/vertex_list_adaptor.hpp</span></tt>></p>
|
|
</div>
|
|
<div class="section" id="class-template-vertex-list-adaptor">
|
|
<h1><a class="toc-backref" href="#id2">Class template <tt class="docutils literal"><span class="pre">vertex_list_adaptor</span></tt></a></h1>
|
|
<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
|
|
Vertex List Graph</a> and a mapping from vertex descriptors to global
|
|
vertex indices, which must be in the range <em>[0, n)</em>, where <em>n</em> is the
|
|
number 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
|
|
Property Map</a> whose key type is a vertex descriptor.</p>
|
|
<p>The vertex list adaptor stores only a reference to the underlying
|
|
graph, forwarding all operations not related to the vertex list on to
|
|
the underlying graph. For instance, if the underlying graph models
|
|
<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
|
|
Graph</a>. Note, however, that no modifications to the underlying graph
|
|
can occur through the vertex list adaptor. Modifications made to the
|
|
underlying graph directly will be reflected in the vertex list
|
|
adaptor, but modifications that add or remove vertices invalidate the
|
|
vertex list adaptor. Additionally, the vertex list adaptor provides
|
|
access to the global index map via the <tt class="docutils literal"><span class="pre">vertex_index</span></tt> property.</p>
|
|
<p>On construction, the vertex list adaptor performs an all-gather
|
|
operation to create a list of all vertices in the graph within each
|
|
process. It is this list that is accessed via <em>vertices</em> and the
|
|
length of this list that is accessed via <em>num_vertices</em>. Due to the
|
|
all-gather operation, the creation of this adaptor is a collective
|
|
operation.</p>
|
|
</div>
|
|
<div class="section" id="function-templates-make-vertex-list-adaptor">
|
|
<h1><a class="toc-backref" href="#id3">Function templates <tt class="docutils literal"><span class="pre">make_vertex_list_adaptor</span></tt></a></h1>
|
|
<p>These function templates construct a vertex list adaptor from a graph
|
|
and, optionally, a property map that maps vertices to global index
|
|
numbers.</p>
|
|
<div class="section" id="parameters">
|
|
<h2><a class="toc-backref" href="#id4">Parameters</a></h2>
|
|
<dl class="docutils">
|
|
<dt>IN: <tt class="docutils literal"><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="DistributedVertexListGraph.html">Distributed Vertex List Graph</a>.</dd>
|
|
<dt>IN: <tt class="docutils literal"><span class="pre">GlobalIndexMap</span> <span class="pre">index_map</span></tt></dt>
|
|
<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
|
|
property map</a> that maps from vertices to a global index. If
|
|
provided, this map must be initialized prior to be passed to the
|
|
vertex list adaptor.</p>
|
|
<p class="last"><strong>Default:</strong> A property map of unspecified type constructed from a
|
|
distributed <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> that uses the
|
|
<tt class="docutils literal"><span class="pre">vertex_index</span></tt> property map of the underlying graph and a vector
|
|
of <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt>.</p>
|
|
</dd>
|
|
</dl>
|
|
</div>
|
|
<div class="section" id="complexity">
|
|
<h2><a class="toc-backref" href="#id5">Complexity</a></h2>
|
|
<p>These operations require <em>O(n)</em> time, where <em>n</em> is the number of
|
|
vertices in the graph, and <em>O(n)</em> communication per node in the BSP model.</p>
|
|
<hr class="docutils" />
|
|
<p>Copyright (C) 2004 The Trustees of Indiana University.</p>
|
|
<p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
|
|
</div>
|
|
</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>
|