ceph/src/boost/libs/graph_parallel/doc/html/distributed_adjacency_list.html

   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 Distributed Adjacency List</title>
   8 <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
   9 </head>
  10 <body>
  11 <div class="document" id="logo-distributed-adjacency-list">
  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> Distributed Adjacency List</h1>
  13
  14 <!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
  15 Use, modification and distribution is subject to the Boost Software
  16 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  17 http://www.boost.org/LICENSE_1_0.txt) -->
  18 <div class="contents topic" id="contents">
  19 <p class="topic-title first">Contents</p>
  20 <ul class="simple">
  21 <li><a class="reference internal" href="#introduction" id="id1">Introduction</a><ul>
  22 <li><a class="reference internal" href="#defining-a-distributed-adjacency-list" id="id2">Defining a Distributed Adjacency List</a></li>
  23 <li><a class="reference internal" href="#distributed-vertex-and-edge-properties" id="id3">Distributed Vertex and Edge Properties</a></li>
  24 <li><a class="reference internal" href="#named-vertices" id="id4">Named Vertices</a></li>
  25 <li><a class="reference internal" href="#building-a-distributed-graph" id="id5">Building a Distributed Graph</a></li>
  26 <li><a class="reference internal" href="#graph-concepts" id="id6">Graph Concepts</a></li>
  27 </ul>
  28 </li>
  29 <li><a class="reference internal" href="#reference" id="id7">Reference</a><ul>
  30 <li><a class="reference internal" href="#where-defined" id="id8">Where Defined</a></li>
  31 <li><a class="reference internal" href="#associated-types" id="id9">Associated Types</a></li>
  32 <li><a class="reference internal" href="#member-functions" id="id10">Member Functions</a></li>
  33 <li><a class="reference internal" href="#non-member-functions" id="id11">Non-Member Functions</a></li>
  34 <li><a class="reference internal" href="#structure-modification" id="id12">Structure Modification</a></li>
  35 <li><a class="reference internal" href="#property-map-accessors" id="id13">Property Map Accessors</a></li>
  36 </ul>
  37 </li>
  38 </ul>
  39 </div>
  40 <div class="section" id="introduction">
  41 <h1><a class="toc-backref" href="#id1">Introduction</a></h1>
  42 <p>The distributed adjacency list implements a graph data structure using
  43 an adjacency list representation. Its interface and behavior are
  44 roughly equivalent to the Boost Graph Library's <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>
  45 class template. However, the distributed adjacency list partitions the
  46 vertices of the graph across several processes (which need not share
  47 an address space). Edges outgoing from any vertex stored by a process
  48 are also stored on that process, except in the case of undirected
  49 graphs, where either the source or the target may store the edge.</p>
  50 <pre class="literal-block">
  51 template&lt;typename OutEdgeListS, typename ProcessGroup, typename VertexListS,
  52          typename DirectedS, typename VertexProperty, typename EdgeProperty,
  53          typename GraphProperty, typename EdgeListS&gt;
  54 class adjacency_list&lt;OutEdgeListS,
  55                      distributedS&lt;ProcessGroup, VertexListS&gt;,
  56                      DirectedS, VertexProperty,
  57                      EdgeProperty, GraphProperty, EdgeListS&gt;;
  58 </pre>
  59 <div class="section" id="defining-a-distributed-adjacency-list">
  60 <h2><a class="toc-backref" href="#id2">Defining a Distributed Adjacency List</a></h2>
  61 <p>To create a distributed adjacency list, first determine the
  62 representation of the graph in a single address space using these
  63 <a class="reference external" href="http://www.boost.org/libs/graph/doc/using_adjacency_list.html">guidelines</a>. Next, replace the vertex list selector (<tt class="docutils literal"><span class="pre">VertexListS</span></tt>)
  64 with an instantiation of <a class="reference external" href="distributedS.html">distributedS</a>, which includes:</p>
  65 <ul class="simple">
  66 <li>Selecting a <a class="reference external" href="process_group.html">process group</a> type that represents the various
  67 coordinating processes that will store the distributed graph. For
  68 example, the <a class="reference external" href="process_group.html">MPI process group</a>.</li>
  69 <li>A selector indicating how the vertex lists in each process will be
  70 stored. Only the <tt class="docutils literal"><span class="pre">vecS</span></tt> and <tt class="docutils literal"><span class="pre">listS</span></tt> selectors are well-supported
  71 at this time.</li>
  72 </ul>
  73 <p>The following <tt class="docutils literal"><span class="pre">typedef</span></tt> defines a distributed adjacency list
  74 containing directed edges. The vertices in the graph will be
  75 distributed over several processes, using the MPI process group
  76 for communication. In each process, the vertices and outgoing edges
  77 will be stored in STL vectors. There are no properties attached to the
  78 vertices or edges of the graph.</p>
  79 <pre class="literal-block">
  80 using namespace boost;
  81 typedef adjacency_list&lt;vecS,
  82                        distributedS&lt;parallel::mpi::bsp_process_group, vecS&gt;,
  83                        directedS&gt;
  84   Graph;
  85 </pre>
  86 </div>
  87 <div class="section" id="distributed-vertex-and-edge-properties">
  88 <h2><a class="toc-backref" href="#id3">Distributed Vertex and Edge Properties</a></h2>
  89 <p>Vertex and edge properties for distributed graphs mirror their
  90 counterparts for non-distributed graphs. With a distributed graph,
  91 however, vertex and edge properties are stored only in the process
  92 that owns the vertex or edge.</p>
  93 <p>The most direct way to attach properties to a distributed graph is to
  94 create a structure that will be attached to each of the vertices and
  95 edges of the graph. For example, if we wish to model a simplistic map
  96 of the United States interstate highway system, we might state that
  97 the vertices of the graph are cities and the edges are highways, then
  98 define the information that we maintain for each city and highway:</p>
  99 <pre class="literal-block">
 100 struct City {
 101   City() { }
 102   City(const std::string&amp; name, const std::string&amp; mayor = &quot;Unknown&quot;, int population = 0)
 103     : name(name), mayor(mayor), population(population) { }
 104
 105   std::string name;
 106   std::string mayor;
 107   int population;
 108
 109   // Serialization support is required!
 110   template&lt;typename Archiver&gt;
 111   void serialize(Archiver&amp; ar, const unsigned int /*version*/) {
 112     ar &amp; name &amp; mayor &amp; population;
 113   }
 114 };
 115
 116 struct Highway {
 117   Highway() { }
 118   Highway(const std::string&amp; name, int lanes, int miles_per_hour, int length)
 119     : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { }
 120
 121   std::string name;
 122   int lanes;
 123   int miles_per_hour;
 124   int length;
 125
 126   // Serialization support is required!
 127   template&lt;typename Archiver&gt;
 128   void serialize(Archiver&amp; ar, const unsigned int /*version*/) {
 129     ar &amp; name &amp; lanes &amp; miles_per_hour &amp; length;
 130   }
 131 };
 132 </pre>
 133 <p>To create a distributed graph for a road map, we supply <tt class="docutils literal"><span class="pre">City</span></tt> and
 134 <tt class="docutils literal"><span class="pre">Highway</span></tt> as the fourth and fifth parameters to <tt class="docutils literal"><span class="pre">adjacency_list</span></tt>,
 135 respectively:</p>
 136 <pre class="literal-block">
 137 typedef adjacency_list&lt;vecS,
 138                        distributedS&lt;parallel::mpi::bsp_process_group, vecS&gt;,
 139                        directedS,
 140                        City, Highway&gt;
 141   RoadMap;
 142 </pre>
 143 <p>Property maps for internal properties retain their behavior with
 144 distributed graphs via <a class="reference external" href="distributed_property_map.html">distributed property maps</a>, which automate
 145 communication among processes so that <tt class="docutils literal"><span class="pre">put</span></tt> and <tt class="docutils literal"><span class="pre">get</span></tt> operations
 146 may be applied to non-local vertices and edges. However, for
 147 distributed adjacency lists that store vertices in a vector
 148 (<tt class="docutils literal"><span class="pre">VertexListS</span></tt> is <tt class="docutils literal"><span class="pre">vecS</span></tt>), the automatic <tt class="docutils literal"><span class="pre">vertex_index</span></tt>
 149 property map restricts the domain of <tt class="docutils literal"><span class="pre">put</span></tt> and <tt class="docutils literal"><span class="pre">get</span></tt> operations
 150 to vertices local to the process executing the operation. For example,
 151 we can create a property map that accesses the length of each highway
 152 as follows:</p>
 153 <pre class="literal-block">
 154 RoadMap map; // distributed graph instance
 155
 156 typedef property_map&lt;RoadMap, int Highway::*&gt;::type
 157   road_length = get(&amp;Highway::length, map);
 158 </pre>
 159 <p>Now, one can access the length of any given road based on its edge
 160 descriptor <tt class="docutils literal"><span class="pre">e</span></tt> with the expression <tt class="docutils literal"><span class="pre">get(road_length,</span> <span class="pre">e)</span></tt>,
 161 regardless of which process stores the edge <tt class="docutils literal"><span class="pre">e</span></tt>.</p>
 162 </div>
 163 <div class="section" id="named-vertices">
 164 <h2><a class="toc-backref" href="#id4">Named Vertices</a></h2>
 165 <p>The vertices of a graph typically correspond to named entities within
 166 the application domain. In the road map example from the previous
 167 section, the vertices in the graph represent cities. The distributed
 168 adjacency list supports named vertices, which provides an implicit
 169 mapping from the names of the vertices in the application domain
 170 (e.g., the name of a city, such as &quot;Bloomington&quot;) to the actual vertex
 171 descriptor stored within the distributed graph (e.g., the third vertex
 172 on processor 1). By enabling support for named vertices, one can refer
 173 to vertices by name when manipulating the graph. For example, one can
 174 add a highway from Indianapolis to Chicago:</p>
 175 <pre class="literal-block">
 176 add_edge(&quot;Indianapolis&quot;, &quot;Chicago&quot;, Highway(&quot;I-65&quot;, 4, 65, 151), map);
 177 </pre>
 178 <p>The distributed adjacency list will find vertices associated with the
 179 names &quot;Indianapolis&quot; and &quot;Chicago&quot;, then add an edge between these
 180 vertices that represents I-65. The vertices may be stored on any
 181 processor, local or remote.</p>
 182 <p>To enable named vertices, specialize the <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt>
 183 property for the structure attached to the vertices in your
 184 graph. <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt> contains a single member, <tt class="docutils literal"><span class="pre">type</span></tt>,
 185 which is the type of a function object that accepts a vertex property
 186 and returns the name stored within that vertex property. In the case
 187 of our road map, the <tt class="docutils literal"><span class="pre">name</span></tt> field contains the name of each city, so
 188 we use the <tt class="docutils literal"><span class="pre">member</span></tt> function object from the <a class="reference external" href="http://www.boost.org/libs/multi_index/doc/index.html">Boost.MultiIndex</a>
 189 library to extract the name, e.g.,</p>
 190 <pre class="literal-block">
 191 namespace boost { namespace graph {
 192
 193 template&lt;&gt;
 194 struct internal_vertex_name&lt;City&gt;
 195 {
 196   typedef multi_index::member&lt;City, std::string, &amp;City::name&gt; type;
 197 };
 198
 199 } }
 200 </pre>
 201 <p>That's it! One can now refer to vertices by name when interacting with
 202 the distributed adjacency list.</p>
 203 <p>What happens when one uses the name of a vertex that does not exist?
 204 For example, in our <tt class="docutils literal"><span class="pre">add_edge</span></tt> call above, what happens if the
 205 vertex named &quot;Indianapolis&quot; has not yet been added to the graph? By
 206 default, the distributed adjacency list will throw an exception if a
 207 named vertex does not yet exist. However, one can customize this
 208 behavior by specifying a function object that constructs an instance
 209 of the vertex property (e.g., <tt class="docutils literal"><span class="pre">City</span></tt>) from just the name of the
 210 vertex. This customization occurs via the
 211 <tt class="docutils literal"><span class="pre">internal_vertex_constructor</span></tt> trait. For example, using the
 212 <tt class="docutils literal"><span class="pre">vertex_from_name</span></tt> template (provided with the Parallel BGL), we can
 213 state that a <tt class="docutils literal"><span class="pre">City</span></tt> can be constructed directly from the name of the
 214 city using its second constructor:</p>
 215 <pre class="literal-block">
 216 namespace boost { namespace graph {
 217
 218 template&lt;&gt;
 219 struct internal_vertex_constructor&lt;City&gt;
 220 {
 221   typedef vertex_from_name&lt;City&gt; type;
 222 };
 223
 224 } }
 225 </pre>
 226 <p>Now, one can add edges by vertex name freely, without worrying about
 227 the explicit addition of vertices. The <tt class="docutils literal"><span class="pre">mayor</span></tt> and <tt class="docutils literal"><span class="pre">population</span></tt>
 228 fields will have default values, but the graph structure will be
 229 correct.</p>
 230 </div>
 231 <div class="section" id="building-a-distributed-graph">
 232 <h2><a class="toc-backref" href="#id5">Building a Distributed Graph</a></h2>
 233 <p>Once you have determined the layout of your graph type, including the
 234 specific data structures and properties, it is time to construct an
 235 instance of the graph by adding the appropriate vertices and
 236 edges. Construction of distributed graphs can be slightly more
 237 complicated than construction of normal, non-distributed graph data
 238 structures, because one must account for both the distribution of the
 239 vertices and edges and the multiple processes executing
 240 concurrently. There are three main ways to construct distributed
 241 graphs:</p>
 242 <p>1. <em>Sequence constructors</em>: if your data can easily be generated by a
 243 pair of iterators that produce (source, target) pairs, you can use the
 244 sequence constructors to build the distributed graph in parallel. This
 245 method is often preferred when creating benchmarks, because random
 246 graph generators like the <a class="reference external" href="http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html">sorted_erdos_renyi_iterator</a> create the
 247 appropriate input sequence. Note that one must provide the same input
 248 iterator sequence on all processes. This method has the advantage that
 249 the sequential graph-building code is identical to the parallel
 250 graph-building code. An example constructing a random graph this way:</p>
 251 <blockquote>
 252 <pre class="literal-block">
 253 typedef boost::sorted_erdos_renyi_iterator&lt;boost::minstd_rand, Graph&gt; ERIter;
 254 boost::minstd_rand gen;
 255 unsigned long n = 1000000; // 1M vertices
 256 Graph g(ERIter(gen, n, 0.00005), ERIter(), n);
 257 </pre>
 258 </blockquote>
 259 <p>2. <em>Adding edges by vertex number</em>: if you are able to map your
 260 vertices into values in the random [0, <em>n</em>), where <em>n</em> is the number
 261 of vertices in the distributed graph. Use this method rather than the
 262 sequence constructors when your algorithm cannot easily be moved into
 263 input iterators, or if you can't replicate the input sequence. For
 264 example, you might be reading the graph from an input file:</p>
 265 <blockquote>
 266 <pre class="literal-block">
 267 Graph g(n); // initialize with the total number of vertices, n
 268 if (process_id(g.process_group()) == 0) {
 269   // Only process 0 loads the graph, which is distributed automatically
 270   int source, target;
 271   for (std::cin &gt;&gt; source &gt;&gt; target)
 272     add_edge(vertex(source, g), vertex(target, g), g);
 273 }
 274
 275 // All processes synchronize at this point, then the graph is complete
 276 synchronize(g.process_group());
 277 </pre>
 278 </blockquote>
 279 <p>3. <em>Adding edges by name</em>: if you are using named vertices, you can
 280 construct your graph just by calling <tt class="docutils literal"><span class="pre">add_edge</span></tt> with the names of
 281 the source and target vertices. Be careful to make sure that each edge
 282 is added by only one process (it doesn't matter which process it is),
 283 otherwise you will end up with multiple edges. For example, in the
 284 following program we read edges from the standard input of process 0,
 285 adding those edges by name. Vertices and edges will be created and
 286 distributed automatically.</p>
 287 <blockquote>
 288 <pre class="literal-block">
 289 Graph g;
 290 if (process_id(g.process_group()) == 0) {
 291   // Only process 0 loads the graph, which is distributed automatically
 292   std:string source, target;
 293   for(std::cin &gt;&gt; source &gt;&gt; target)
 294     add_edge(source, target, g);
 295 }
 296
 297 // All processes synchronize at this point, then the graph is complete
 298 synchronize(g.process_group());
 299 </pre>
 300 </blockquote>
 301 </div>
 302 <div class="section" id="graph-concepts">
 303 <h2><a class="toc-backref" href="#id6">Graph Concepts</a></h2>
 304 <p>The distributed adjacency list models the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Graph.html">Graph</a> concept, and in
 305 particular the <a class="reference external" href="DistributedGraph.html">Distributed Graph</a> concept. It also models the
 306 <a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> and <a class="reference external" href="http://www.boost.org/libs/graph/doc/AdjacencyGraph.html">Adjacency Graph</a> concept, but restricts the
 307 input domain of the operations to correspond to local vertices
 308 only. For instance, a process may only access the outgoing edges of a
 309 vertex if that vertex is stored in that process. Undirected and
 310 bidirectional distributed adjacency lists model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional
 311 Graph</a> concept, with the same domain restrictions. Distributed
 312 adjacency lists also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutableGraph.html">Mutable Graph</a> concept (with domain
 313 restrictions; see the <a class="reference internal" href="#reference">Reference</a> section), <a class="reference external" href="http://www.boost.org/libs/graph/doc/PropertyGraph.html">Property Graph</a> concept,
 314 and <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutablePropertyGraph.html">Mutable Property Graph</a> concept.</p>
 315 <p>Unlike its non-distributed counterpart, the distributed adjacency
 316 list does <strong>not</strong> model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> or <a class="reference external" href="http://www.boost.org/libs/graph/doc/EdgeListGraph.html">Edge List
 317 Graph</a> concepts, because one cannot enumerate all vertices or edges
 318 within a distributed graph. Instead, it models the weaker
 319 <a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List Graph</a> and <a class="reference external" href="DistributedEdgeListGraph.html">Distributed Edge List Graph</a>
 320 concepts, which permit access to the local edges and vertices on each
 321 processor. Note that if all processes within the process group over
 322 which the graph is distributed iterator over their respective vertex
 323 or edge lists, all vertices and edges will be covered once.</p>
 324 </div>
 325 </div>
 326 <div class="section" id="reference">
 327 <h1><a class="toc-backref" href="#id7">Reference</a></h1>
 328 <p>Since the distributed adjacency list closely follows the
 329 non-distributed <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>, this reference documentation
 330 only describes where the two implementations differ.</p>
 331 <div class="section" id="where-defined">
 332 <h2><a class="toc-backref" href="#id8">Where Defined</a></h2>
 333 <p>&lt;boost/graph/distributed/adjacency_list.hpp&gt;</p>
 334 </div>
 335 <div class="section" id="associated-types">
 336 <h2><a class="toc-backref" href="#id9">Associated Types</a></h2>
 337 <pre class="literal-block">
 338 adjacency_list::process_group_type
 339 </pre>
 340 <p>The type of the process group over which the graph will be
 341 distributed.</p>
 342 <hr class="docutils" />
 343 <blockquote>
 344 adjacency_list::distribution_type</blockquote>
 345 <p>The type of distribution used to partition vertices in the graph.</p>
 346 <hr class="docutils" />
 347 <blockquote>
 348 adjacency_list::vertex_name_type</blockquote>
 349 <p>If the graph supports named vertices, this is the type used to name
 350 vertices. Otherwise, this type is not present within the distributed
 351 adjacency list.</p>
 352 </div>
 353 <div class="section" id="member-functions">
 354 <h2><a class="toc-backref" href="#id10">Member Functions</a></h2>
 355 <pre class="literal-block">
 356 adjacency_list(const ProcessGroup&amp; pg = ProcessGroup());
 357
 358 adjacency_list(const GraphProperty&amp; g,
 359                const ProcessGroup&amp; pg = ProcessGroup());
 360 </pre>
 361 <p>Construct an empty distributed adjacency list with the given process
 362 group (or default) and graph property (or default).</p>
 363 <hr class="docutils" />
 364 <pre class="literal-block">
 365 adjacency_list(vertices_size_type n, const GraphProperty&amp; p,
 366                const ProcessGroup&amp; pg, const Distribution&amp; distribution);
 367
 368 adjacency_list(vertices_size_type n, const ProcessGroup&amp; pg,
 369                const Distribution&amp; distribution);
 370
 371 adjacency_list(vertices_size_type n, const GraphProperty&amp; p,
 372                const ProcessGroup&amp; pg = ProcessGroup());
 373
 374 adjacency_list(vertices_size_type n,
 375                const ProcessGroup&amp; pg = ProcessGroup());
 376 </pre>
 377 <p>Construct a distributed adjacency list with <tt class="docutils literal"><span class="pre">n</span></tt> vertices,
 378 optionally providing the graph property, process group, or
 379 distribution. The <tt class="docutils literal"><span class="pre">n</span></tt> vertices will be distributed via the given
 380 (or default-constructed) distribution. This operation is collective,
 381 requiring all processes with the process group to execute it
 382 concurrently.</p>
 383 <hr class="docutils" />
 384 <pre class="literal-block">
 385 template &lt;class EdgeIterator&gt;
 386 adjacency_list(EdgeIterator first, EdgeIterator last,
 387                vertices_size_type n,
 388                const ProcessGroup&amp; pg = ProcessGroup(),
 389                const GraphProperty&amp; p = GraphProperty());
 390
 391 template &lt;class EdgeIterator, class EdgePropertyIterator&gt;
 392 adjacency_list(EdgeIterator first, EdgeIterator last,
 393                EdgePropertyIterator ep_iter,
 394                vertices_size_type n,
 395                const ProcessGroup&amp; pg = ProcessGroup(),
 396                const GraphProperty&amp; p = GraphProperty());
 397
 398 template &lt;class EdgeIterator&gt;
 399 adjacency_list(EdgeIterator first, EdgeIterator last,
 400                vertices_size_type n,
 401                const ProcessGroup&amp; process_group,
 402                const Distribution&amp; distribution,
 403                const GraphProperty&amp; p = GraphProperty());
 404
 405 template &lt;class EdgeIterator, class EdgePropertyIterator&gt;
 406 adjacency_list(EdgeIterator first, EdgeIterator last,
 407                EdgePropertyIterator ep_iter,
 408                vertices_size_type n,
 409                const ProcessGroup&amp; process_group,
 410                const Distribution&amp; distribution,
 411                const GraphProperty&amp; p = GraphProperty());
 412 </pre>
 413 <p>Construct a distributed adjacency list with <tt class="docutils literal"><span class="pre">n</span></tt> vertices and with
 414 edges specified in the edge list given by the range <tt class="docutils literal"><span class="pre">[first,</span> <span class="pre">last)</span></tt>. The
 415 <tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> must be a model of <a class="reference external" href="http://www.boost.org/doc/html/InputIterator.html">InputIterator</a>. The value type of the
 416 <tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> must be a <tt class="docutils literal"><span class="pre">std::pair</span></tt>, where the type in the pair is an
 417 integer type. The integers will correspond to vertices, and they must
 418 all fall in the range of <tt class="docutils literal"><span class="pre">[0,</span> <span class="pre">n)</span></tt>. When provided, <tt class="docutils literal"><span class="pre">ep_iter</span></tt>
 419 refers to an edge property list <tt class="docutils literal"><span class="pre">[ep_iter,</span> <span class="pre">ep_iter</span> <span class="pre">+</span> <span class="pre">m)</span></tt> contains
 420 properties for each of the edges.</p>
 421 <p>This constructor is a collective operation and must be executed
 422 concurrently by each process with the same argument list. Most
 423 importantly, the edge lists provided to the constructor in each process
 424 should be equivalent. The vertices will be partitioned among the
 425 processes according to the <tt class="docutils literal"><span class="pre">distribution</span></tt>, with edges placed on the
 426 process owning the source of the edge. Note that this behavior
 427 permits sequential graph construction code to be parallelized
 428 automatically, regardless of the underlying distribution.</p>
 429 <hr class="docutils" />
 430 <pre class="literal-block">
 431 void clear()
 432 </pre>
 433 <p>Removes all of the edges and vertices from the local graph. To
 434 eliminate all vertices and edges from the graph, this routine must be
 435 executed in all processes.</p>
 436 <hr class="docutils" />
 437 <pre class="literal-block">
 438 process_group_type&amp; process_group();
 439 const process_group_type&amp; process_group() const;
 440 </pre>
 441 <p>Returns the process group over which this graph is distributed.</p>
 442 <hr class="docutils" />
 443 <pre class="literal-block">
 444 distribution_type&amp;       distribution();
 445 const distribution_type&amp; distribution() const;
 446 </pre>
 447 <p>Returns the distribution used for initial placement of vertices.</p>
 448 <hr class="docutils" />
 449 <pre class="literal-block">
 450 template&lt;typename VertexProcessorMap&gt;
 451   void redistribute(VertexProcessorMap vertex_to_processor);
 452 </pre>
 453 <p>Redistributes the vertices (and, therefore, the edges) of the
 454 graph. The property map <tt class="docutils literal"><span class="pre">vertex_to_processor</span></tt> provides, for each
 455 vertex, the process identifier indicating where the vertex should be
 456 moved. Once this collective routine has completed, the distributed
 457 graph will reflect the new distribution. All vertex and edge
 458 descsriptors and internal and external property maps are invalidated
 459 by this operation.</p>
 460 <hr class="docutils" />
 461 <pre class="literal-block">
 462 template&lt;typename OStreamConstructibleArchive&gt;
 463   void save(std::string const&amp; filename) const;
 464
 465 template&lt;typename IStreamConstructibleArchive&gt;
 466   void load(std::string const&amp; filename);
 467 </pre>
 468 <p>Serializes the graph to a Boost.Serialization archive.
 469 <tt class="docutils literal"><span class="pre">OStreamConstructibleArchive</span></tt> and <tt class="docutils literal"><span class="pre">IStreamConstructibleArchive</span></tt>
 470 are models of Boost.Serialization <em>Archive</em> with the extra
 471 requirement that they can be constructed from a <tt class="docutils literal"><span class="pre">std::ostream</span></tt>
 472 and <tt class="docutils literal"><span class="pre">std::istream</span></tt>.
 473 <tt class="docutils literal"><span class="pre">filename</span></tt> names a directory that will hold files for
 474 the different processes.</p>
 475 </div>
 476 <div class="section" id="non-member-functions">
 477 <h2><a class="toc-backref" href="#id11">Non-Member Functions</a></h2>
 478 <pre class="literal-block">
 479 std::pair&lt;vertex_iterator, vertex_iterator&gt;
 480 vertices(const adjacency_list&amp; g);
 481 </pre>
 482 <p>Returns an iterator-range providing access to the vertex set of graph
 483 <tt class="docutils literal"><span class="pre">g</span></tt> stored in this process. Each of the processes that contain <tt class="docutils literal"><span class="pre">g</span></tt>
 484 will get disjoint sets of vertices.</p>
 485 <hr class="docutils" />
 486 <pre class="literal-block">
 487 std::pair&lt;edge_iterator, edge_iterator&gt;
 488 edges(const adjacency_list&amp; g);
 489 </pre>
 490 <p>Returns an iterator-range providing access to the edge set of graph
 491 <tt class="docutils literal"><span class="pre">g</span></tt> stored in this process.</p>
 492 <hr class="docutils" />
 493 <pre class="literal-block">
 494 std::pair&lt;adjacency_iterator, adjacency_iterator&gt;
 495 adjacent_vertices(vertex_descriptor u, const adjacency_list&amp; g);
 496 </pre>
 497 <p>Returns an iterator-range providing access to the vertices adjacent to
 498 vertex <tt class="docutils literal"><span class="pre">u</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to this process.</p>
 499 <hr class="docutils" />
 500 <pre class="literal-block">
 501 std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
 502 out_edges(vertex_descriptor u, const adjacency_list&amp; g);
 503 </pre>
 504 <p>Returns an iterator-range providing access to the out-edges of vertex
 505 <tt class="docutils literal"><span class="pre">u</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. If the graph is undirected, this iterator-range
 506 provides access to all edges incident on vertex <tt class="docutils literal"><span class="pre">u</span></tt>. For both
 507 directed and undirected graphs, for an out-edge <tt class="docutils literal"><span class="pre">e</span></tt>, <tt class="docutils literal"><span class="pre">source(e,</span> <span class="pre">g)</span>
 508 <span class="pre">==</span> <span class="pre">u</span></tt> and <tt class="docutils literal"><span class="pre">target(e,</span> <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">v</span></tt> where <tt class="docutils literal"><span class="pre">v</span></tt> is a vertex adjacent to
 509 <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to this process.</p>
 510 <hr class="docutils" />
 511 <pre class="literal-block">
 512 std::pair&lt;in_edge_iterator, in_edge_iterator&gt;
 513 in_edges(vertex_descriptor v, const adjacency_list&amp; g);
 514 </pre>
 515 <p>Returns an iterator-range providing access to the in-edges of vertex
 516 <tt class="docutils literal"><span class="pre">v</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. This operation is only available if
 517 <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> was specified for the <tt class="docutils literal"><span class="pre">Directed</span></tt> template
 518 parameter. For an in-edge <tt class="docutils literal"><span class="pre">e</span></tt>, <tt class="docutils literal"><span class="pre">target(e,</span> <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">v</span></tt> and <tt class="docutils literal"><span class="pre">source(e,</span>
 519 <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">u</span></tt> for some vertex <tt class="docutils literal"><span class="pre">u</span></tt> that is adjacent to <tt class="docutils literal"><span class="pre">v</span></tt>, whether the
 520 graph is directed or undirected. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local to
 521 this process.</p>
 522 <hr class="docutils" />
 523 <pre class="literal-block">
 524 degree_size_type
 525 out_degree(vertex_descriptor u, const adjacency_list&amp; g);
 526 </pre>
 527 <p>Returns the number of edges leaving vertex <tt class="docutils literal"><span class="pre">u</span></tt>. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must
 528 be local to the executing process.</p>
 529 <hr class="docutils" />
 530 <pre class="literal-block">
 531 degree_size_type
 532 in_degree(vertex_descriptor u, const adjacency_list&amp; g);
 533 </pre>
 534 <p>Returns the number of edges entering vertex <tt class="docutils literal"><span class="pre">u</span></tt>. This operation is
 535 only available if <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> was specified for the
 536 <tt class="docutils literal"><span class="pre">Directed</span></tt> template parameter. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to the
 537 executing process.</p>
 538 <hr class="docutils" />
 539 <pre class="literal-block">
 540 vertices_size_type
 541 num_vertices(const adjacency_list&amp; g);
 542 </pre>
 543 <p>Returns the number of vertices in the graph <tt class="docutils literal"><span class="pre">g</span></tt> that are stored in
 544 the executing process.</p>
 545 <hr class="docutils" />
 546 <pre class="literal-block">
 547 edges_size_type
 548 num_edges(const adjacency_list&amp; g);
 549 </pre>
 550 <p>Returns the number of edges in the graph <tt class="docutils literal"><span class="pre">g</span></tt> that are stored in the
 551 executing process.</p>
 552 <hr class="docutils" />
 553 <pre class="literal-block">
 554 vertex_descriptor
 555 vertex(vertices_size_type n, const adjacency_list&amp; g);
 556 </pre>
 557 <p>Returns the <tt class="docutils literal"><span class="pre">n``th</span> <span class="pre">vertex</span> <span class="pre">in</span> <span class="pre">the</span> <span class="pre">graph's</span> <span class="pre">vertex</span> <span class="pre">list,</span> <span class="pre">according</span> <span class="pre">to</span> <span class="pre">the</span>
 558 <span class="pre">distribution</span> <span class="pre">used</span> <span class="pre">to</span> <span class="pre">partition</span> <span class="pre">the</span> <span class="pre">graph.</span> <span class="pre">``n</span></tt> must be a value
 559 between zero and the sum of <tt class="docutils literal"><span class="pre">num_vertices(g)</span></tt> in each process (minus
 560 one). Note that it is not necessarily the case that <tt class="docutils literal"><span class="pre">vertex(0,</span> <span class="pre">g)</span> <span class="pre">==</span>
 561 <span class="pre">*num_vertices(g).first</span></tt>. This function is only guaranteed to be
 562 accurate when no vertices have been added to or removed from the
 563 graph after its initial construction.</p>
 564 <hr class="docutils" />
 565 <pre class="literal-block">
 566 std::pair&lt;edge_descriptor, bool&gt;
 567 edge(vertex_descriptor u, vertex_descriptor v,
 568      const adjacency_list&amp; g);
 569 </pre>
 570 <p>Returns an edge connecting vertex <tt class="docutils literal"><span class="pre">u</span></tt> to vertex <tt class="docutils literal"><span class="pre">v</span></tt> in graph
 571 <tt class="docutils literal"><span class="pre">g</span></tt>. For bidirectional and undirected graphs, either vertex <tt class="docutils literal"><span class="pre">u</span></tt> or
 572 vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local; for directed graphs, vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be
 573 local.</p>
 574 <hr class="docutils" />
 575 <pre class="literal-block">
 576 std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
 577 edge_range(vertex_descriptor u, vertex_descriptor v,
 578            const adjacency_list&amp; g);
 579 </pre>
 580 <p>TODO: Not implemented.  Returns a pair of out-edge iterators that give
 581 the range for all the parallel edges from <tt class="docutils literal"><span class="pre">u</span></tt> to <tt class="docutils literal"><span class="pre">v</span></tt>. This function only
 582 works when the <tt class="docutils literal"><span class="pre">OutEdgeList</span></tt> for the <tt class="docutils literal"><span class="pre">adjacency_list</span></tt> is a container that
 583 sorts the out edges according to target vertex, and allows for
 584 parallel edges. The <tt class="docutils literal"><span class="pre">multisetS</span></tt> selector chooses such a
 585 container. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be stored in the executing process.</p>
 586 </div>
 587 <div class="section" id="structure-modification">
 588 <h2><a class="toc-backref" href="#id12">Structure Modification</a></h2>
 589 <pre class="literal-block">
 590 unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list&amp; g);
 591 unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list&amp; g);
 592 unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list&amp; g);
 593 unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list&amp; g);
 594 </pre>
 595 <p>Adds edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> to the graph. The return type itself is
 596 unspecified, but the type can be copy-constructed and implicitly
 597 converted into a <tt class="docutils literal"><span class="pre">std::pair&lt;edge_descriptor,bool&gt;</span></tt>. The edge
 598 descriptor describes the added (or found) edge. For graphs that do not
 599 allow parallel edges, if the edge
 600 is already in the graph then a duplicate will not be added and the
 601 <tt class="docutils literal"><span class="pre">bool</span></tt> flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. Also, if u and v are descriptors for
 602 the same vertex (creating a self loop) and the graph is undirected,
 603 then the edge will not be added and the flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. When
 604 the flag is <tt class="docutils literal"><span class="pre">false</span></tt>, the returned edge descriptor points to the
 605 already existing edge.</p>
 606 <p>The parameters <tt class="docutils literal"><span class="pre">u</span></tt> and <tt class="docutils literal"><span class="pre">v</span></tt> can be either vertex descriptors or, if
 607 the graph uses named vertices, the names of vertices. If no vertex
 608 with the given name exists, the internal vertex constructor will be
 609 invoked to create a new vertex property and a vertex with that
 610 property will be added to the graph implicitly. The default internal
 611 vertex constructor throws an exception.</p>
 612 <hr class="docutils" />
 613 <pre class="literal-block">
 614 unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties&amp; p, adjacency_list&amp; g);
 615 unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties&amp; p, adjacency_list&amp; g);
 616 unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties&amp; p, adjacency_list&amp; g);
 617 unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties&amp; p, adjacency_list&amp; g);
 618 </pre>
 619 <p>Adds edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> to the graph and attaches <tt class="docutils literal"><span class="pre">p</span></tt> as the value of the edge's
 620 internal property storage. See the previous <tt class="docutils literal"><span class="pre">add_edge()</span></tt> member
 621 function for more details.</p>
 622 <hr class="docutils" />
 623 <pre class="literal-block">
 624 void
 625 remove_edge(vertex_descriptor u, vertex_descriptor v,
 626             adjacency_list&amp; g);
 627 </pre>
 628 <p>Removes the edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> from the graph. If the directed selector is
 629 <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> or <tt class="docutils literal"><span class="pre">undirectedS</span></tt>, either the source or target
 630 vertex of the graph must be local. If the directed selector is
 631 <tt class="docutils literal"><span class="pre">directedS</span></tt>, then the source vertex must be local.</p>
 632 <hr class="docutils" />
 633 <pre class="literal-block">
 634 void
 635 remove_edge(edge_descriptor e, adjacency_list&amp; g);
 636 </pre>
 637 <p>Removes the edge <tt class="docutils literal"><span class="pre">e</span></tt> from the graph. If the directed selector is
 638 <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> or <tt class="docutils literal"><span class="pre">undirectedS</span></tt>, either the source or target
 639 vertex of the graph must be local. If the directed selector is
 640 <tt class="docutils literal"><span class="pre">directedS</span></tt>, then the source vertex must be local.</p>
 641 <hr class="docutils" />
 642 <pre class="literal-block">
 643 void remove_edge(out_edge_iterator iter, adjacency_list&amp; g);
 644 </pre>
 645 <p>This has the same effect as <tt class="docutils literal"><span class="pre">remove_edge(*iter,</span> <span class="pre">g)</span></tt>. For directed
 646 (but not bidirectional) graphs, this will be more efficient than
 647 <tt class="docutils literal"><span class="pre">remove_edge(*iter,</span> <span class="pre">g)</span></tt>.</p>
 648 <hr class="docutils" />
 649 <pre class="literal-block">
 650 template &lt;class Predicate &gt;
 651 void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
 652                         adjacency_list&amp; g);
 653 </pre>
 654 <p>Removes all out-edges of vertex <tt class="docutils literal"><span class="pre">u</span></tt> from the graph that satisfy the
 655 predicate. That is, if the predicate returns <tt class="docutils literal"><span class="pre">true</span></tt> when applied to an
 656 edge descriptor, then the edge is removed. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local.</p>
 657 <p>The affect on descriptor and iterator stability is the same as that of
 658 invoking remove_edge() on each of the removed edges.</p>
 659 <hr class="docutils" />
 660 <pre class="literal-block">
 661 template &lt;class Predicate &gt;
 662 void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
 663                        adjacency_list&amp; g);
 664 </pre>
 665 <p>Removes all in-edges of vertex <tt class="docutils literal"><span class="pre">v</span></tt> from the graph that satisfy the
 666 predicate. That is, if the predicate returns true when applied to an
 667 edge descriptor, then the edge is removed. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local.</p>
 668 <p>The affect on descriptor and iterator stability is the same as that of
 669 invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> on each of the removed edges.</p>
 670 <p>This operation is available for undirected and bidirectional
 671 adjacency_list graphs, but not for directed.</p>
 672 <hr class="docutils" />
 673 <pre class="literal-block">
 674 template &lt;class Predicate&gt;
 675 void remove_edge_if(Predicate predicate, adjacency_list&amp; g);
 676 </pre>
 677 <p>Removes all edges from the graph that satisfy the predicate. That is,
 678 if the predicate returns true when applied to an edge descriptor, then
 679 the edge is removed.</p>
 680 <p>The affect on descriptor and iterator stability is the same as that
 681 of invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> on each of the removed edges.</p>
 682 <hr class="docutils" />
 683 <pre class="literal-block">
 684 vertex_descriptor add_vertex(adjacency_list&amp; g);
 685 </pre>
 686 <p>Adds a vertex to the graph and returns the vertex descriptor for the
 687 new vertex. The vertex will be stored in the local process. This
 688 function is not available when using named vertices.</p>
 689 <hr class="docutils" />
 690 <pre class="literal-block">
 691 unspecified add_vertex(const VertexProperties&amp; p, adjacency_list&amp; g);
 692 unspecified add_vertex(const vertex_name_type&amp; p, adjacency_list&amp; g);
 693 </pre>
 694 <p>Adds a vertex to the graph with the specified properties. If the graph
 695 is using vertex names, the vertex will be added on whichever process
 696 &quot;owns&quot; that name. Otherwise, the vertex will be stored in the local
 697 process. Note that the second constructor will invoke the
 698 user-customizable internal vertex constructor, which (by default)
 699 throws an exception when it sees an unknown vertex.</p>
 700 <p>The return type is of unspecified type, but can be copy-constructed
 701 and can be implicitly converted into a vertex descriptor.</p>
 702 <hr class="docutils" />
 703 <pre class="literal-block">
 704 void clear_vertex(vertex_descriptor u, adjacency_list&amp; g);
 705 </pre>
 706 <p>Removes all edges to and from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears
 707 in the vertex set of the graph.</p>
 708 <p>The affect on descriptor and iterator stability is the same as that of
 709 invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the source
 710 or target.</p>
 711 <p>This operation is not applicable to directed graphs, because the
 712 incoming edges to vertex <tt class="docutils literal"><span class="pre">u</span></tt> are not known.</p>
 713 <hr class="docutils" />
 714 <pre class="literal-block">
 715 void clear_out_edges(vertex_descriptor u, adjacency_list&amp; g);
 716 </pre>
 717 <p>Removes all out-edges from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears in
 718 the vertex set of the graph.</p>
 719 <p>The affect on descriptor and iterator stability is the same as that of
 720 invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the
 721 source.</p>
 722 <p>This operation is not applicable to undirected graphs (use
 723 <tt class="docutils literal"><span class="pre">clear_vertex()</span></tt> instead).</p>
 724 <hr class="docutils" />
 725 <pre class="literal-block">
 726 void clear_in_edges(vertex_descriptor u, adjacency_list&amp; g);
 727 </pre>
 728 <p>Removes all in-edges from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears in
 729 the vertex set of the graph.</p>
 730 <p>The affect on descriptor and iterator stability is the same as that of
 731 invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the
 732 target.</p>
 733 <p>This operation is only applicable to bidirectional graphs.</p>
 734 <hr class="docutils" />
 735 <pre class="literal-block">
 736 void remove_vertex(vertex_descriptor u, adjacency_list&amp; g);
 737 </pre>
 738 <p>Remove vertex <tt class="docutils literal"><span class="pre">u</span></tt> from the vertex set of the graph. It is assumed
 739 that there are no edges to or from vertex <tt class="docutils literal"><span class="pre">u</span></tt> when it is
 740 removed. One way to make sure of this is to invoke <tt class="docutils literal"><span class="pre">clear_vertex()</span></tt>
 741 beforehand. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be stored locally.</p>
 742 </div>
 743 <div class="section" id="property-map-accessors">
 744 <h2><a class="toc-backref" href="#id13">Property Map Accessors</a></h2>
 745 <pre class="literal-block">
 746 template &lt;class PropertyTag&gt;
 747 property_map&lt;adjacency_list, PropertyTag&gt;::type
 748 get(PropertyTag, adjacency_list&amp; g);
 749
 750 template &lt;class PropertyTag&gt;
 751 property_map&lt;adjacency_list, Tag&gt;::const_type
 752 get(PropertyTag, const adjacency_list&amp; g);
 753 </pre>
 754 <p>Returns the property map object for the vertex property specified by
 755 <tt class="docutils literal"><span class="pre">PropertyTag</span></tt>. The <tt class="docutils literal"><span class="pre">PropertyTag</span></tt> must match one of the properties
 756 specified in the graph's <tt class="docutils literal"><span class="pre">VertexProperty</span></tt> template argument. The
 757 returned property map will be a <a class="reference external" href="distributed_property_map.html">distributed property map</a>.</p>
 758 <hr class="docutils" />
 759 <pre class="literal-block">
 760 template &lt;class PropertyTag , class X&gt;
 761 typename property_traits&lt;property_map&lt;adjacency_list, PropertyTag&gt;::const_type&gt;::value_type
 762 get(PropertyTag, const adjacency_list&amp; g, X x);
 763 </pre>
 764 <p>This returns the property value for <tt class="docutils literal"><span class="pre">x</span></tt>, where <tt class="docutils literal"><span class="pre">x</span></tt> is either a vertex or
 765 edge descriptor.  The entity referred to by descriptor <tt class="docutils literal"><span class="pre">x</span></tt> must be
 766 stored in the local process.</p>
 767 <hr class="docutils" />
 768 <pre class="literal-block">
 769 template &lt;class PropertyTag , class X, class Value&gt;
 770 void put(PropertyTag, const adjacency_list&amp; g, X x, const Value&amp; value);
 771 </pre>
 772 <p>This sets the property value for <tt class="docutils literal"><span class="pre">x</span></tt> to value. <tt class="docutils literal"><span class="pre">x</span></tt> is either a
 773 vertex or edge descriptor. <tt class="docutils literal"><span class="pre">Value</span></tt> must be convertible to <tt class="docutils literal"><span class="pre">typename</span>
 774 <span class="pre">property_traits&lt;property_map&lt;adjacency_list,</span>
 775 <span class="pre">PropertyTag&gt;::type&gt;::value_type</span></tt>.</p>
 776 <hr class="docutils" />
 777 <pre class="literal-block">
 778 template &lt;class GraphProperties, class GraphPropertyTag&gt;
 779 typename graph_property&lt;adjacency_list, GraphPropertyTag&gt;::type&amp;
 780 get_property(adjacency_list&amp; g, GraphPropertyTag);
 781
 782 template &lt;class GraphProperties, class GraphPropertyTag &gt;
 783 const typename graph_property&lt;adjacency_list, GraphPropertyTag&gt;::type&amp;
 784 get_property(const adjacency_list&amp; g, GraphPropertyTag);
 785 </pre>
 786 <p>TODO: not implemented.</p>
 787 <p>Return the property specified by <tt class="docutils literal"><span class="pre">GraphPropertyTag</span></tt> that is attached
 788 to the graph object <tt class="docutils literal"><span class="pre">g</span></tt>. The <tt class="docutils literal"><span class="pre">graph_property</span></tt> traits class is
 789 defined in <tt class="docutils literal"><span class="pre">boost/graph/adjacency_list.hpp</span></tt>.</p>
 790 <hr class="docutils" />
 791 <p>Copyright (C) 2004 The Trustees of Indiana University.</p>
 792 <p>Copyright (C) 2007 Douglas Gregor</p>
 793 <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
 794 </div>
 795 </div>
 796 </div>
 797 <div class="footer">
 798 <hr class="footer" />
 799 Generated on: 2009-05-31 00:21 UTC.
 800 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.
 801
 802 </div>
 803 </body>
 804 </html>