123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121 |
- <?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>
|