libs/graph/doc/adjacency_list.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek 2000
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Boost Graph Library: Adjacency List</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18 <H1><A NAME="sec:adjacency-list-class"></A>
  19 <pre>
  20 adjacency_list&lt;OutEdgeList, VertexList, Directed,
  21                VertexProperties, EdgeProperties,
  22                GraphProperties, EdgeList&gt;
  23 </pre>
  24 </H1>
  25
  26
  27 <P>
  28 The <TT>adjacency_list</TT> class implements a generalized adjacency
  29 list graph structure. The template parameters provide many
  30 configuration options so that you can pick a version of the class that
  31 best meets your needs. An <a
  32 href="graph_theory_review.html#sec:adjacency-list-representation">adjacency-list</a>
  33 is basically a two-dimensional structure, where each element of the
  34 first dimension represents a vertex, and each of the vertices contains
  35 a one-dimensional structure that is its edge list. <a
  36 href="#fig:adj-list-graph">Figure 1</a> shows an adjacency list
  37 representation of a directed graph.
  38
  39 <P></P>
  40 <DIV ALIGN="center"><A NAME="fig:adj-list-graph"></A>
  41 <TABLE>
  42 <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> Adjacency List Representation of a Directed Graph.</CAPTION>
  43 <TR><TD><IMG SRC="./figs/adj-matrix-graph2.gif" width="386" height="284"></TD>
  44 <TD><IMG SRC="./figs/adj-list2.gif" width="62" height="122"></TD></TR>
  45 </TABLE>
  46 </DIV><P></P>
  47
  48 The
  49 <TT>VertexList</TT> template parameter of the <TT>adjacency_list</TT>
  50 class controls what kind of container is used to represent the outer
  51 two-dimensional container. The <TT>OutEdgeList</TT> template parameter
  52 controls what kind of container is used to represent the edge
  53 lists. The choices for <TT>OutEdgeList</TT> and <TT>VertexList</TT> will
  54 determine the space complexity of the graph structure, and will
  55 determine the time complexity of the various graph operations. The
  56 possible choices and tradeoffs are discussed in Section <A
  57 HREF="./using_adjacency_list.html#sec:choosing-graph-type">Choosing
  58 the <TT>Edgelist</TT> and <TT>VertexList</TT></A>.
  59
  60 <P>
  61 The <TT>Directed</TT> template parameter controls whether the graph is
  62 directed, undirected, or directed with access to both the in-edges and
  63 out-edges (which we call bidirectional). The bidirectional graph takes
  64 up twice the space (per edge) of a directed graph since each edge will
  65 appear in both an out-edge and in-edge list. <a
  66 href="#fig:undir-adj-list-graph">Figure 2</a> shows an adjacency list
  67 representation of an undirected graph.
  68
  69 <P></P>
  70 <DIV ALIGN="center"><A NAME="fig:undir-adj-list-graph"></A>
  71 <TABLE>
  72 <CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG> Adjacency List Representation of an Undirected Graph.</CAPTION>
  73 <TR><TD><IMG SRC="./figs/undir-adj-matrix-graph2.gif" width="260" height="240"></TD>
  74 <TD><IMG SRC="./figs/undir-adj-list.gif" width="62" height="122"></TD></TR>
  75 </TABLE>
  76 </DIV><P></P>
  77
  78 <P>
  79 A tutorial on how to use the <TT>adjacency_list</TT> class is in
  80 Section <A HREF="./using_adjacency_list.html">Using
  81 <TT>adjacency_list</TT></A>.
  82
  83 <P>
  84
  85 <H3>Example</H3>
  86
  87 <P>
  88 The example in <a
  89 href="../example/family-tree-eg.cpp"><tt>examples/family-tree-eg.cpp</tt></a>
  90 shows how to represent a family tree with a graph.
  91
  92 <H3>Template Parameters</H3>
  93
  94 <P>
  95 <TABLE border>
  96 <TR>
  97 <th>Parameter</th><th>Description</th><th>Default</th>
  98 </tr>
  99
 100 <TR><TD><TT>OutEdgeList</TT></TD>
 101 <TD>The selector for the container used to represent the
 102   edge-list for each of the vertices.</TD>
 103 <TD><TT>vecS</TT></TD>
 104 </TR>
 105
 106 <TR>
 107 <TD><TT>VertexList</TT></TD>
 108 <TD>The selector for the container used to represent the
 109   vertex-list of the graph.</TD>
 110 <TD><TT>vecS</TT></TD>
 111 </TR>
 112
 113 <TR>
 114 <TD><TT>Directed</TT></TD>
 115 <TD>A selector to choose whether the graph is directed, undirected, or directed with bidirectional edge access (access to both out-edges and in-edges). The options are <TT>directedS</TT>, <TT>undirectedS</TT>, and <TT>bidirectionalS</TT>.</TD>
 116 <TD><TT>directedS</TT></TD>
 117 </TR>
 118
 119 <TR>
 120 <TD><TT>VertexProperties</TT></TD>
 121 <TD>for specifying internal property storage.</TD>
 122 <TD><TT>no_property</TT></TD>
 123 </TR>
 124
 125 <TR>
 126 <TD><TT>EdgeProperties</TT></TD>
 127 <TD>for specifying internal property storage.</TD>
 128 <TD><TT>no_property</TT></TD>
 129 </TR>
 130
 131 <TR>
 132 <TD><TT>GraphProperties</TT></TD>
 133 <TD>for specifying property storage for the graph object.</TD>
 134 <TD><TT>no_property</TT></TD>
 135 </TR>
 136
 137 <TR><TD><TT>EdgeList</TT></TD>
 138 <TD>The selector for the container used to represent the
 139   edge-list for the graph.</TD>
 140 <TD><TT>listS</TT></TD>
 141 </TR>
 142
 143 </TABLE>
 144 <P>
 145
 146 <H3>Model of</H3>
 147
 148 <P>
 149 <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>,
 150 <a href="./MutablePropertyGraph.html">MutablePropertyGraph</a>,
 151 <a href="../../utility/CopyConstructible.html">CopyConstructible</a>,
 152 <a href="../../utility/Assignable.html">Assignable</a>,
 153 and <a href="../../serialization/doc/index.html">Serializable</a>.
 154
 155
 156 <P>
 157
 158 <H3>Where Defined</H3>
 159
 160 <P>
 161 <a href="../../../boost/graph/adjacency_list.hpp"><TT>boost/graph/adjacency_list.hpp</TT></a><br><br>
 162 Also, the serialization functionality is in
 163 <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>.
 164 <P>
 165
 166 <H2>Vertex and Edge Properties</H2>
 167
 168 <P>
 169 Properties such as color, distance, weight, and user-defined
 170 properties can be attached to the vertices and edges of the graph
 171 using properties. The property values can be read from and written to
 172 via the property maps provided by the graph. The property maps are
 173 obtained via the <TT>get(property, g)</TT> function.  How to use
 174 properties is described in Section <A
 175 HREF="./using_adjacency_list.html#sec:adjacency-list-properties">Internal
 176 Properties </A>. The property maps are objects that implement the
 177 interface defined in Section <A
 178 HREF="../../property_map/doc/property_map.html">Property Map
 179 Concepts</A> or may be <a href="bundles.html">bundled properties</a>,
 180 which have a more succinct syntax. The types of all property values
 181 must be Copy Constructible, Assignable, and Default Constructible.
 182 The property maps obtained from the
 183 <TT>adjacency_list</TT> class are models of the <a
 184 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 185 Map</a> concept. If the <TT>adjacency_list</TT> is const,
 186 then the property map is constant, otherwise the property
 187 map is mutable.
 188
 189 <P>
 190 If the <TT>VertexList</TT> of the graph is <TT>vecS</TT>, then the
 191 graph has a builtin vertex indices accessed via the property map for
 192 the <TT>vertex_index_t</TT> property.  The indices fall in the range
 193 <TT>[0, num_vertices(g))</TT> and are contiguous. When a vertex is
 194 removed the indices are adjusted so that they retain these
 195 properties. Some care must be taken when using these indices to access
 196 exterior property storage. The property map for vertex index is a
 197 model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
 198 Property Map</a>.
 199
 200 <P>
 201
 202 <h2>Iterator and Descriptor Stability/Invalidation</h2>
 203
 204 Some care must be taken when changing the structure of a graph (via
 205 adding or removing edges). Depending on the type of
 206 <tt>adjacency_list</tt> and on the operation, some of the iterator or
 207 descriptor objects that point into the graph may become invalid.  For
 208 example, the following code will result in undefined (bad) behavior:
 209
 210 <pre>
 211   typedef adjacency_list&lt;listS, vecS&gt; Graph; <b>// VertexList=vecS</b>
 212   Graph G(N);
 213   <b>// Fill in the graph...</b>
 214
 215   <b>// Attempt to remove all the vertices. Wrong!</b>
 216   graph_traits&lt;Graph&gt;::vertex_iterator vi, vi_end;
 217   for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
 218     remove_vertex(*vi, G);
 219
 220   <b>// Remove all the vertices. This is still wrong!</b>
 221   graph_traits&lt;Graph&gt;::vertex_iterator vi, vi_end, next;
 222   boost::tie(vi, vi_end) = vertices(G);
 223   for (next = vi; vi != vi_end; vi = next) {
 224     ++next;
 225     remove_vertex(*vi, G);
 226   }
 227 </pre>
 228
 229 The reason this is a problem is that we are invoking
 230 <tt>remove_vertex()</tt>, which when used with an
 231 <tt>adjacency_list</tt> where <tt>VertexList=vecS</tt>, invalidates
 232 all iterators and descriptors for the graph (such as <tt>vi</tt> and
 233 <tt>vi_end</tt>), thereby causing trouble in subsequent iterations of
 234 the loop.
 235
 236 <p>
 237
 238 If we use a different kind of <tt>adjacency_list</tt>, where
 239 <tt>VertexList=listS</tt>, then the iterators are not invalidated by
 240 calling <tt>remove_vertex</tt> unless the iterator is pointing to the
 241 actual vertex that was removed. The following code demonstrates this.
 242
 243 <pre>
 244   typedef adjacency_list&lt;listS, listS&gt; Graph; <b>// VertexList=listS</b>
 245   Graph G(N);
 246   <b>// Fill in the graph...</b>
 247
 248   <b>// Attempt to remove all the vertices. Wrong!</b>
 249   graph_traits&lt;Graph&gt;::vertex_iterator vi, vi_end;
 250   for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
 251     remove_vertex(*vi, G);
 252
 253   <b>// Remove all the vertices. This is OK.</b>
 254   graph_traits&lt;Graph&gt;::vertex_iterator vi, vi_end, next;
 255   boost::tie(vi, vi_end) = vertices(G);
 256   for (next = vi; vi != vi_end; vi = next) {
 257     ++next;
 258     remove_vertex(*vi, G);
 259   }
 260 </pre>
 261
 262 <p>
 263
 264 The stability issue also affects vertex and edge descriptors.  For
 265 example, suppose you use vector of vertex descriptors to keep track of
 266 the parents (or predecessors) of vertices in a shortest paths tree
 267 (see <a
 268 href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>).
 269 You create the parent vector with a call to
 270 <tt>dijkstra_shortest_paths()</tt>, and then remove a vertex from the
 271 graph. Subsequently you try to use the parent vector, but since all
 272 vertex descriptors have become invalid, the result is incorrect.
 273
 274 <pre>
 275   std::vector&lt;Vertex&gt; parent(num_vertices(G));
 276   std::vector&lt;Vertex&gt; distance(num_vertices(G));
 277
 278   dijkstra_shortest_paths(G, s, distance_map(&amp;distance[0]).
 279     predecessor_map(&amp;parent[0]));
 280
 281   remove_vertex(s, G); <b>// Bad idea! Invalidates vertex descriptors in parent vector.</b>
 282
 283   <b>// The following will produce incorrect results</b>
 284   for(boost::tie(vi, vend) = vertices(G); vi != vend; ++vi)
 285     std::cout << p[*vi] << " is the parent of " << *vi << std::endl;
 286 </pre>
 287
 288
 289 <p>
 290 Note that in this discussion iterator and descriptor invalidation is
 291 concerned with the invalidation of iterators and descriptors that are
 292 <b>not directly affected</b> by the operation. For example, performing
 293 <tt>remove_edge(u, v, g)</tt> will always invalidate any edge
 294 descriptor for <i>(u,v)</i> or edge iterator pointing to <i>(u,v)</i>,
 295 regardless of the kind <tt>adjacency_list</tt>.  In this discussion
 296 of iterator and descriptor invalidation, we are only concerned with the
 297 affect of <tt>remove_edge(u, v, g)</tt> on edge descriptors and
 298 iterators that point to other edges (not <i>(u,v)</i>).
 299
 300 <p>
 301 In general, if you want your vertex and edge descriptors to be stable
 302 (never invalidated) then use <tt>listS</tt> or <tt>setS</tt> for the
 303 <tt>VertexList</tt> and <tt>OutEdgeList</tt> template parameters of
 304 <tt>adjacency_list</tt>. If you are not as concerned about descriptor
 305 and iterator stability, and are more concerned about memory
 306 consumption and graph traversal speed, use <tt>vecS</tt> for the
 307 <tt>VertexList</tt> and/or <tt>OutEdgeList</tt> template parameters.
 308
 309 <p>
 310 The following table summarizes which operations cause descriptors and
 311 iterators to become invalid. In the table, <tt>EL</tt> is an
 312 abbreviation for <tt>OutEdgeList</tt> and <tt>VL</tt> means
 313 <tt>VertexList</tt>. The <b>Adj Iter</b> category includes the
 314 <tt>out_edge_iterator</tt>, <tt>in_edge_iterator</tt>, and
 315 <tt>adjacency_iterator</tt> types. A more detailed description of
 316 descriptor and iterator invalidation is given in the documentation for
 317 each operation.
 318
 319 <p>
 320
 321 <table border>
 322 <CAPTION ALIGN="BOTTOM"><STRONG>Table:</STRONG>
 323     Summary of Descriptor and Iterator Invalidation.
 324     </CAPTION>
 325 <tr>
 326     <th>Function</th>
 327     <th>Vertex Desc</th>
 328     <th>Edge Desc</th>
 329     <th>Vertex Iter</th>
 330     <th>Edge Iter</th>
 331     <th>Adj Iter</th>
 332 </tr>
 333 <tr>
 334 <td>
 335     <tt>add_edge()</tt></td>
 336     <td align=center><tt>OK</tt></td>
 337     <td align=center><tt>OK</tt></td>
 338     <td align=center><tt>OK</tt></td>
 339     <td align=center><tt>EL=vecS &amp;&amp; <br>Directed=directedS</tt></td>
 340     <td align=center><tt>EL=vecS</tt></td>
 341 </tr>
 342 <tr>
 343     <td><tt>remove_edge()<br>remove_edge_if()<br>remove_out_edge_if()<br>
 344             remove_in_edge_if()<br>clear_vertex()</tt>
 345     </td>
 346     <td align=center><tt>OK</tt></td>
 347     <td align=center><tt>OK</tt></td>
 348     <td align=center><tt>OK</tt></td>
 349     <td align=center><tt>EL=vecS &amp;&amp; <br>Directed=directedS</tt></td>
 350     <td align=center><tt>EL=vecS</tt></td>
 351 </tr>
 352 <tr>
 353     <td><tt>add_vertex()</tt></td>
 354     <td align=center><tt>OK</tt></td>
 355     <td align=center><tt>OK</tt></td>
 356     <td align=center><tt>OK</tt></td>
 357     <td align=center><tt>VL=vecS &amp;&amp; <br/> Directed=directedS</tt></td>
 358     <td align=center><tt>VL=vecS &amp;&amp; <br/> Directed=directedS</tt></td>
 359 </tr>
 360 <tr>
 361     <td><tt>remove_vertex()</tt></td>
 362     <td align=center><tt>VL=vecS</tt></td>
 363     <td align=center><tt>VL=vecS</tt></td>
 364     <td align=center><tt>VL=vecS</tt></td>
 365     <td align=center><tt>VL=vecS</tt></td>
 366     <td align=center><tt>VL=vecS</tt></td>
 367 </tr>
 368 </table>
 369
 370 <H2>Associated Types</H2>
 371
 372 <hr>
 373
 374 <tt>graph_traits&lt;adjacency_list&gt;::vertex_descriptor</tt>
 375 <br>
 376 and
 377 <br>
 378 <tt>adjacency_list_traits&lt;OutEdgeList, VertexList, Directed, EdgeList&gt;::vertex_descriptor</tt>
 379 <br><br>
 380 The type for the vertex descriptors associated with the
 381 <TT>adjacency_list</TT>.
 382
 383 <hr>
 384
 385 <tt>graph_traits&lt;adjacency_list&gt;::edge_descriptor</tt><br>
 386 and<br>
 387 <tt>adjacency_list_traits&lt;OutEdgeList, VertexList, Directed, EdgeList&gt;::edge_descriptor</tt>
 388 <br><br>
 389 The type for the edge descriptors associated with the
 390 <TT>adjacency_list</TT>.
 391
 392 <hr>
 393
 394 <tt>graph_traits&lt;adjacency_list&gt;::vertex_iterator</tt>
 395 <br><br>
 396 The type for the iterators returned by <TT>vertices()</TT>.
 397
 398 When <tt>VertexList=vecS</tt> then the <tt>vertex_iterator</tt> models
 399 <a
 400 href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>. Otherwise
 401 the <tt>vertex_iterator</tt> models <a
 402 href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
 403
 404 <hr>
 405
 406 <tt>graph_traits&lt;adjacency_list&gt;::edge_iterator</tt>
 407 <br><br>
 408 The type for the iterators returned by <TT>edges()</TT>.
 409 The <tt>edge_iterator</tt> models <a
 410 href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
 411
 412
 413 <hr>
 414
 415
 416 <tt>graph_traits&lt;adjacency_list&gt;::out_edge_iterator</tt>
 417 <br><br>
 418
 419 The type for the iterators returned by <TT>out_edges()</TT>.
 420 When <tt>OutEdgeList=vecS</tt> then the <tt>out_edge_iterator</tt> models
 421 <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">
 422 RandomAccessIterator</a>.  When <tt>OutEdgeList=slistS</tt> then the
 423 <tt>out_edge_iterator</tt> models <a
 424 href="http://www.sgi.com/tech/stl/ForwardIterator.html">
 425 ForwardIterator</a>.  Otherwise the <tt>out_edge_iterator</tt> models
 426 <a
 427 href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">
 428 BidirectionalIterator</a>.
 429
 430 <hr>
 431
 432 <tt>graph_traits&lt;adjacency_list&gt;::adjacency_iterator</tt>
 433 <br><br>
 434 The type for the iterators returned by <TT>adjacent_vertices()</TT>.
 435 The <tt>adjacency_iterator</tt> models the same iterator concept
 436 as <tt>out_edge_iterator</tt>.
 437 <hr>
 438
 439 <tt>adjacency_list::inv_adjacency_iterator</tt>
 440 <br><br>
 441 The type for the iterators returned by <TT>inv_adjacent_vertices()</TT>.
 442 The <tt>inv_adjacency_iterator</tt> models the same iterator concept
 443 as <tt>out_edge_iterator</tt>.
 444 <hr>
 445
 446 <tt>graph_traits&lt;adjacency_list&gt;::directed_category</tt><br>
 447 and<br>
 448 <tt>adjacency_list_traits&lt;OutEdgeList, VertexList, Directed, EdgeList&gt;::directed_category</tt>
 449 <br><br>
 450 Provides information about whether the graph is
 451 directed (<TT>directed_tag</TT>) or undirected
 452 (<TT>undirected_tag</TT>).
 453
 454 <hr>
 455
 456 <tt>graph_traits&lt;adjacency_list&gt;::edge_parallel_category</tt><br>
 457 and<br>
 458 <tt>adjacency_list_traits&lt;OutEdgeList, VertexList, Directed, EdgeList&gt;::edge_parallel_category</tt>
 459 <br><br>
 460 This describes whether the graph class allows the insertion of
 461 parallel edges (edges with the same source and target). The two tags
 462 are <TT>allow_parallel_edge-_tag</TT> and
 463 <TT>disallow_parallel_edge_tag</TT>. The
 464 <TT>setS</TT> and <TT>hash_setS</TT> variants disallow
 465 parallel edges while the others allow parallel edges.
 466
 467 <hr>
 468
 469 <tt>graph_traits&lt;adjacency_list&gt;::vertices_size_type</tt><br>
 470 and<br>
 471 <tt>adjacency_list_traits&lt;OutEdgeList, VertexList, Directed_list, EdgeList&gt;::vertices_size_type</tt><br>
 472 <br><br>
 473 The type used for dealing with the number of vertices in the graph.
 474
 475 <hr>
 476
 477 <tt>graph_traits&lt;adjacency_list&gt;::edge_size_type</tt><br>
 478 and<br>
 479 <tt>adjacency_list_traits&lt;OutEdgeList, VertexList, Directed_list, EdgeList&gt;::edge_size_type</tt><br>
 480 <br><br>
 481 The type used for dealing with the number of edges in the graph.
 482
 483 <hr>
 484
 485 <tt>graph_traits&lt;adjacency_list&gt;::degree_size_type</tt>
 486 <br><br>
 487 The type used for dealing with the number of edges incident to a vertex
 488 in the graph.
 489
 490 <hr>
 491
 492 <tt>property_map&lt;adjacency_list, Property&gt;::type</tt><br>
 493 and<br>
 494 <tt>property_map&lt;adjacency_list, Property&gt;::const_type</tt>
 495 <br><br>
 496 The property map type for vertex or edge properties in the graph. The
 497 specific property is specified by the <TT>Property</TT> template argument,
 498 and must match one of the properties specified in the
 499 <TT>VertexProperties</TT> or <TT>EdgeProperties</TT> for the graph.
 500
 501 <hr>
 502
 503 <tt>graph_property&lt;adjacency_list, Property&gt;::type</tt>
 504 <br><br>
 505 The property value type for the graph property specified by the
 506 <tt>Property</tt> tag.
 507
 508 <hr>
 509
 510 <tt>adjacency_list::out_edge_list_selector</tt>
 511 <br><br>
 512 The type <tt>OutEdgeListS</tt>.
 513
 514 <hr>
 515
 516 <tt>adjacency_list::vertex_list_selector</tt>
 517 <br><br>
 518 The type <tt>VertexListS</tt>.
 519
 520 <hr>
 521
 522 <tt>adjacency_list::directed_selector</tt>
 523 <br><br>
 524 The type <tt>DirectedS</tt>.
 525
 526 <hr>
 527
 528 <tt>adjacency_list::edge_list_selector</tt>
 529 <br><br>
 530 The type <tt>EdgeListS</tt>.
 531
 532 <hr>
 533
 534 <H2>Member Functions</H2>
 535
 536 <hr>
 537
 538 <pre>
 539 adjacency_list(const&nbsp;GraphProperty&amp;&nbsp;p = GraphProperty())
 540 </pre>
 541 Default constructor. Creates an empty graph object with zero vertices
 542 and zero edges.
 543
 544 <hr>
 545
 546 <pre>
 547 adjacency_list(const&nbsp;adjacency_list&amp;&nbsp;x)
 548 </pre>
 549 Copy constructor. Creates a new graph that is a copy of graph
 550 <tt>x</tt>, including the edges, vertices, and properties.
 551
 552 <hr>
 553
 554 <pre>
 555 adjacency_list&amp; operator=(const&nbsp;adjacency_list&amp;&nbsp;x)
 556 </pre>
 557 Assignment operator. Makes this graph a copy of graph
 558 <tt>x</tt>, including the edges, vertices, and properties.
 559
 560 <hr>
 561
 562 <pre>
 563 adjacency_list(vertices_size_type&nbsp;n,
 564                const&nbsp;GraphProperty&amp;&nbsp;p = GraphProperty())
 565 </pre>
 566 Creates a graph object with <TT>n</TT> vertices and zero edges.
 567
 568 <hr>
 569
 570 <a name="sec:iterator-constructor">
 571 <pre>
 572 template &lt;class&nbsp;EdgeIterator&gt;
 573 adjacency_list(EdgeIterator&nbsp;first, EdgeIterator&nbsp;last,
 574                vertices_size_type&nbsp;n,
 575                edges_size_type&nbsp;m = 0,
 576                const&nbsp;GraphProperty&amp;&nbsp;p&nbsp;=&nbsp;GraphProperty())
 577 </pre>
 578 Creates a graph object with <TT>n</TT> vertices and with the edges
 579 specified in the edge list given by the range <TT>[first, last)</TT>.
 580 The <tt>EdgeIterator</tt> must be a model of <a
 581 href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
 582 The value type of the <TT>EdgeIterator</TT> must be a
 583 <TT>std::pair</TT>, where the type in the pair is an integer type. The
 584 integers will correspond to vertices, and they must all fall in the
 585 range of <TT>[0, n)</TT>.
 586 </a>
 587
 588 <hr>
 589
 590 <pre>
 591 template &lt;class&nbsp;EdgeIterator, class&nbsp;EdgePropertyIterator&gt;
 592 adjacency_list(EdgeIterator&nbsp;first, EdgeIterator&nbsp;last,
 593                EdgePropertyIterator&nbsp;ep_iter,
 594                vertices_size_type&nbsp;n,
 595                edges_size_type&nbsp;m = 0,
 596                const&nbsp;GraphProperty&amp;&nbsp;p&nbsp;=&nbsp;GraphProperty())
 597 </pre>
 598 Creates a graph object with <TT>n</TT> vertices and with the edges
 599 specified in the edge list given by the range <TT>[first, last)</TT>.
 600 The <tt>EdgeIterator</tt> and <tt>EdgePropertyIterator</tt> must be a
 601 model of <a
 602 href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.
 603 The value type of the <TT>EdgeIterator</TT> must be a
 604 <TT>std::pair</TT>, where the type in the pair is an integer type. The
 605 integers will correspond to vertices, and they must all fall in the
 606 range of <TT>[0, n)</TT>. The <TT>value_type</TT> of the
 607 <TT>ep_iter</TT> should be <TT>EdgeProperties</TT>.
 608
 609 <hr>
 610
 611 <pre>
 612 void clear()
 613 </pre>
 614 Remove all of the edges and vertices from the graph.
 615
 616 <hr>
 617
 618 <pre>
 619 void swap(adjacency_list&amp; x)
 620 </pre>
 621 Swap the vertices, edges, and properties of this graph with the
 622 vertices, edges, and properties of graph <tt>x</tt>.
 623 <hr>
 624
 625 <P>
 626
 627 <H2>Non-Member Functions</H2>
 628
 629
 630 <h4>Structure Access</h4>
 631
 632 <hr>
 633
 634 <pre>
 635 std::pair&lt;vertex_iterator,&nbsp;vertex_iterator&gt;
 636 vertices(const adjacency_list&amp; g)
 637 </pre>
 638 Returns an iterator-range providing access to the vertex set of graph
 639 <tt>g</tt>.
 640
 641 <hr>
 642
 643 <pre>
 644 std::pair&lt;edge_iterator,&nbsp;edge_iterator&gt;
 645 edges(const adjacency_list&amp; g)
 646 </pre>
 647 Returns an iterator-range providing access to the edge set of graph
 648 <tt>g</tt>.
 649
 650 <hr>
 651
 652 <pre>
 653 std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;
 654 adjacent_vertices(vertex_descriptor&nbsp;u, const&nbsp;adjacency_list&amp;&nbsp;g)
 655 </pre>
 656 Returns an iterator-range providing access to the vertices adjacent to
 657 vertex <tt>u</tt> in graph <tt>g</tt>. For example, if <tt>u -> v</tt>
 658 is an edge in the graph, then <tt>v</tt> will be in this iterator-range.
 659
 660 <hr>
 661
 662 <pre>
 663 std::pair&lt;inv_adjacency_iterator,&nbsp;inv_adjacency_iterator&gt;
 664 inv_adjacent_vertices(vertex_descriptor&nbsp;u, const&nbsp;adjacency_list&amp;&nbsp;g)
 665 </pre>
 666
 667 Returns an iterator-range providing access to the vertices in graph
 668 <tt>g</tt> to which <tt>u</tt> is adjacent. (<tt>inv</tt> is for
 669 inverse.) For example, if <tt>v -> u</tt> is an edge in the graph,
 670 then <tt>v</tt> will be in this iterator range. This function is only
 671 available for bidirectional and undirected <tt>adjacency_list</tt>'s.
 672
 673 <hr>
 674
 675
 676 <pre>
 677 std::pair&lt;out_edge_iterator,&nbsp;out_edge_iterator&gt;
 678 out_edges(vertex_descriptor&nbsp;u, const&nbsp;adjacency_list&amp;&nbsp;g)
 679 </pre>
 680 Returns an iterator-range providing access to the out-edges of vertex
 681 <tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this
 682 iterator-range provides access to all edges incident on vertex
 683 <tt>u</tt>. For both directed and undirected graphs, for an out-edge
 684 <tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt>
 685 where <tt>v</tt> is a vertex adjacent to <tt>u</tt>.
 686
 687 <hr>
 688
 689 <pre>
 690 std::pair&lt;in_edge_iterator,&nbsp;in_edge_iterator&gt;
 691 in_edges(vertex_descriptor&nbsp;v, const&nbsp;adjacency_list&amp;&nbsp;g)
 692 </pre>
 693 Returns an iterator-range providing access to the in-edges of vertex
 694 <tt>v</tt> in graph <tt>g</tt>.  This operation is only available if
 695 <TT>bidirectionalS</TT> was specified for the <TT>Directed</TT>
 696 template parameter. For an in-edge <tt>e</tt>, <tt>target(e, g) == v</tt>
 697 and <tt>source(e, g) == u</tt> for some vertex <tt>u</tt> that is
 698 adjacent to <tt>v</tt>, whether the graph is directed or undirected.
 699
 700 <hr>
 701
 702 <pre>
 703 vertex_descriptor
 704 source(edge_descriptor&nbsp;e, const&nbsp;adjacency_list&amp;&nbsp;g)
 705 </pre>
 706 Returns the source vertex of edge <tt>e</tt>.
 707
 708 <hr>
 709
 710 <pre>
 711 vertex_descriptor
 712 target(edge_descriptor&nbsp;e, const&nbsp;adjacency_list&amp;&nbsp;g)
 713 </pre>
 714 Returns the target vertex of edge <tt>e</tt>.
 715
 716 <hr>
 717
 718 <pre>
 719 degree_size_type
 720 out_degree(vertex_descriptor&nbsp;u, const&nbsp;adjacency_list&amp;&nbsp;g)
 721 </pre>
 722 Returns the number of edges leaving vertex <tt>u</tt>.
 723
 724 <hr>
 725
 726 <pre>
 727 degree_size_type
 728 in_degree(vertex_descriptor&nbsp;u, const&nbsp;adjacency_list&amp;&nbsp;g)
 729 </pre>
 730 Returns the number of edges entering vertex <tt>u</tt>. This operation
 731 is only available if <TT>bidirectionalS</TT> was specified for
 732 the <TT>Directed</TT> template parameter.
 733
 734 <hr>
 735
 736 <pre>
 737 vertices_size_type
 738 num_vertices(const adjacency_list&amp; g)
 739 </pre>
 740 Returns the number of vertices in the graph <tt>g</tt>.
 741
 742 <hr>
 743
 744 <pre>
 745 edges_size_type
 746 num_edges(const adjacency_list&amp; g)
 747 </pre>
 748 Returns the number of edges in the graph <tt>g</tt>.
 749
 750 <hr>
 751
 752 <pre>
 753 vertex_descriptor
 754 vertex(vertices_size_type&nbsp;n, const&nbsp;adjacency_list&amp;&nbsp;g)
 755 </pre>
 756 Returns the nth vertex in the graph's vertex list.
 757
 758 <hr>
 759
 760
 761 <pre>
 762 std::pair&lt;edge_descriptor, bool&gt;
 763 edge(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
 764      const&nbsp;adjacency_list&amp;&nbsp;g)
 765 </pre>
 766 If an edge from vertex <tt>u</tt> to vertex <tt>v</tt> exists, return a pair
 767 containing one such edge and <tt>true</tt>.  If there are no edges between
 768 <tt>u</tt> and <tt>v</tt>, return a pair with an arbitrary edge descriptor and
 769 <tt>false</tt>.
 770
 771 <hr>
 772
 773 <pre>
 774 std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
 775 edge_range(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
 776            const&nbsp;adjacency_list&amp;&nbsp;g)
 777 </pre>
 778 Returns a pair of out-edge iterators that give the range for
 779 all the parallel edges from <tt>u</tt> to <tt>v</tt>. This
 780 function only works when the <tt>OutEdgeList</tt> for the
 781 <tt>adjacency_list</tt> is a container that sorts the
 782 out edges according to target vertex, and allows for
 783 parallel edges. The <tt>multisetS</tt> selector chooses
 784 such a container.
 785
 786 <hr>
 787
 788 <h4>Structure Modification</h4>
 789
 790 <hr>
 791
 792 <pre>
 793 std::pair&lt;edge_descriptor, bool&gt;
 794 add_edge(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
 795          adjacency_list&amp; g)
 796 </pre>
 797 Adds edge <i>(u,v)</i> to the graph and returns the edge descriptor
 798 for the new edge. For graphs that do not allow parallel edges, if the
 799 edge is already in the graph then a duplicate will not be added and
 800 the <TT>bool</TT> flag will be <TT>false</TT>. When the flag is
 801 <TT>false</TT>, the
 802 returned edge descriptor points to the already existing edge.
 803
 804 <p>
 805 The placement of the new edge in the out-edge list is in general
 806 unspecified, though ordering of the out-edge list can be accomplished
 807 through the choice of <tt>OutEdgeList</tt>.
 808
 809 If the <tt>VertexList</tt> selector is
 810 <tt>vecS</tt>, and if either vertex descriptor <tt>u</tt> or
 811 <tt>v</tt> (which are integers) has a value greater than the current
 812 number of vertices in the graph, the graph is enlarged so that the
 813 number of vertices is <tt>std::max(u,v) + 1</tt>.
 814
 815 <p>
 816 If the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation
 817 will invalidate any <tt>out_edge_iterator</tt> for vertex
 818 <i>u</i>. This also applies if the <TT>OutEdgeList</TT> is a user-defined
 819 container that invalidates its iterators when <TT>push(container,
 820 x)</TT> is invoked (see Section <A
 821 HREF="./using_adjacency_list.html#sec:custom-storage">Customizing the
 822 Adjacency List Storage</A>). If the graph is also bidirectional then
 823 any <tt>in_edge_iterator</tt> for <i>v</i> is also invalidated.  If
 824 instead the graph is undirected then any <tt>out_edge_iterator</tt>
 825 for <i>v</i> is also invalidated. If instead the graph is directed,
 826 then <tt>add_edge()</tt> also invalidates any <tt>edge_iterator</tt>.
 827
 828
 829 <hr>
 830
 831 <pre>
 832 std::pair&lt;edge_descriptor,&nbsp;bool&gt;
 833 add_edge(vertex_descriptor&nbsp;u, vertex_descriptor&nbsp;v,
 834          const&nbsp;EdgeProperties&amp;&nbsp;p,
 835          adjacency_list&amp;&nbsp;g)
 836 </pre>
 837 Adds edge <i>(u,v)</i> to the graph and attaches <TT>p</TT> as the
 838 value of the edge's internal property storage.  Also see the previous
 839 <TT>add_edge()</TT> member function for more details.
 840
 841 <hr>
 842
 843 <pre>
 844 void remove_edge(vertex_descriptor u, vertex_descriptor v,
 845                  adjacency_list&amp; g)
 846 </pre>
 847 Removes the edge <i>(u,v)</i> from the graph.
 848 <p>
 849 This operation causes any outstanding edge descriptors or iterators
 850 that point to edge <i>(u,v)</i> to become invalid.  In addition, if
 851 the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation
 852 will invalidate any iterators that point into the edge-list for vertex
 853 <i>u</i> and also for vertex <i>v</i> in the undirected and
 854 bidirectional case. Also, for directed graphs this invalidates any
 855 <tt>edge_iterator</tt>.
 856
 857 <hr>
 858
 859 <pre>
 860 void remove_edge(edge_descriptor e, adjacency_list&amp; g)
 861 </pre>
 862 Removes the edge <tt>e</tt> from the graph. This differs from the
 863 <tt>remove_edge(u, v, g)</tt> function in the case of a
 864 multigraph. This <tt>remove_edge(e, g)</tt> function removes a single
 865 edge, whereas the <tt>remove_edge(u, v, g)</tt> function removes all
 866 edges <i>(u,v)</i>.
 867 <p>
 868 This operation invalidates any outstanding edge descriptors and
 869 iterators for the same edge pointed to by descriptor <tt>e</tt>.  In
 870 addition, this operation will invalidate any iterators that point into
 871 the edge-list for the <tt>target(e, g)</tt>.  Also, for directed
 872 graphs this invalidates any <tt>edge_iterator</tt> for the graph.
 873
 874 <hr>
 875
 876 <pre>
 877 void remove_edge(out_edge_iterator iter, adjacency_list&amp; g)
 878 </pre>
 879 This has the same effect as <tt>remove_edge(*iter, g)</tt>. The
 880 difference is that this function has constant time complexity
 881 in the case of directed graphs, whereas <tt>remove_edge(e, g)</tt>
 882 has time complexity <i>O(E/V)</i>.
 883
 884 <hr>
 885
 886 <pre>
 887 template &lt;class <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>&gt;
 888 void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
 889                         adjacency_list&amp; g)
 890 </pre>
 891 Removes all out-edges of vertex <i>u</i> from the graph that satisfy
 892 the <tt>predicate</tt>. That is, if the predicate returns true when
 893 applied to an edge descriptor, then the edge is removed.
 894 <p>
 895 The affect on descriptor and iterator stability is the same as that of
 896 invoking <tt>remove_edge()</tt> on each of the removed edges.
 897
 898 <hr>
 899
 900 <pre>
 901 template &lt;class <a
 902 href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>&gt;
 903 void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
 904                        adjacency_list&amp; g)
 905 </pre>
 906 Removes all in-edges of vertex <i>v</i> from the graph that satisfy
 907 the <tt>predicate</tt>. That is, if the predicate returns true when
 908 applied to an edge descriptor, then the edge is removed.
 909 <p>
 910 The affect on descriptor and iterator stability is the
 911 same as that of invoking <tt>remove_edge()</tt> on each of the
 912 removed edges.
 913 <p>
 914 This operation is available for undirected and bidirectional
 915 <tt>adjacency_list</tt> graphs, but not for directed.
 916
 917 <hr>
 918
 919 <pre>
 920 template &lt;class <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>&gt;
 921 void remove_edge_if(Predicate predicate, adjacency_list&amp; g)
 922 </pre>
 923 Removes all edges from the graph that satisfy
 924 the <tt>predicate</tt>. That is, if the predicate returns true when
 925 applied to an edge descriptor, then the edge is removed.
 926 <p>
 927 The affect on descriptor and iterator stability is the same as that of
 928 invoking <tt>remove_edge()</tt> on each of the removed edges.
 929
 930 <hr>
 931
 932 <a name="sec:add-vertex">
 933 <pre>
 934 vertex_descriptor
 935 add_vertex(adjacency_list&amp; g)
 936 </pre>
 937 Adds a vertex to the graph and returns the vertex descriptor for the
 938 new vertex.
 939 </a>
 940
 941 <hr>
 942
 943 <pre>
 944 vertex_descriptor
 945 add_vertex(const&nbsp;VertexProperties&amp;&nbsp;p,
 946            adjacency_list&amp; g)
 947 </pre>
 948 Adds a vertex to the graph with the specified properties. Returns the
 949 vertex descriptor for the new vertex.
 950 </a>
 951
 952 <hr>
 953
 954 <pre>
 955 void clear_vertex(vertex_descriptor u, adjacency_list&amp; g)
 956 </pre>
 957 Removes all edges to and from vertex <i>u</i>. The vertex still appears
 958 in the vertex set of the graph.
 959 <p>
 960 The affect on descriptor and iterator stability is the
 961 same as that of invoking <tt>remove_edge()</tt> for all of
 962 the edges that have <tt>u</tt> as the source or target.
 963
 964 <hr>
 965
 966 <pre>
 967 void clear_out_edges(vertex_descriptor u, adjacency_list&amp; g)
 968 </pre>
 969 Removes all out-edges from vertex <i>u</i>. The vertex still appears
 970 in the vertex set of the graph.
 971 <p>
 972 The affect on descriptor and iterator stability is the
 973 same as that of invoking <tt>remove_edge()</tt> for all of
 974 the edges that have <tt>u</tt> as the source.
 975 <p>
 976 This operation is not applicable to undirected graphs
 977 (use <tt>clear_vertex()</tt> instead).
 978
 979 <hr>
 980
 981 <pre>
 982 void clear_in_edges(vertex_descriptor u, adjacency_list&amp; g)
 983 </pre>
 984 Removes all in-edges from vertex <i>u</i>. The vertex still appears
 985 in the vertex set of the graph.
 986 <p>
 987 The affect on descriptor and iterator stability is the
 988 same as that of invoking <tt>remove_edge()</tt> for all of
 989 the edges that have <tt>u</tt> as the target.
 990 <p>
 991 This operation is only applicable to bidirectional graphs.
 992
 993 <hr>
 994
 995 <pre>
 996 void remove_vertex(vertex_descriptor u, adjacency_list&amp; g)
 997 </pre>
 998 Remove vertex <i>u</i> from the vertex set of the graph. It is assumed
 999 that there are no edges to or from vertex <i>u</i> when it is removed.
1000 One way to make sure of this is to invoke <TT>clear_vertex()</TT>
1001 beforehand.
1002 <p>
1003 If the <TT>VertexList</TT> template parameter of the
1004 <TT>adjacency_list</TT> was <TT>vecS</TT>, then all vertex
1005 descriptors, edge descriptors, and iterators for the graph are
1006 invalidated by this operation. The builtin
1007 <tt>vertex_index_t</tt> property for each vertex is renumbered so that
1008 after the operation the vertex indices still form a contiguous range
1009 <TT>[0, num_vertices(g))</TT>. If you are using external property
1010 storage based on the builtin vertex index, then the external storage
1011 will need to be adjusted. Another option is to not use the builtin
1012 vertex index, and instead use a property to add your own vertex index
1013 property. If you need to make frequent use of the
1014 <TT>remove_vertex()</TT> function the <TT>listS</TT> selector is a
1015 much better choice for the <TT>VertexList</TT> template parameter.
1016
1017 <hr>
1018
1019 <h4><a name="property-map-accessors">Property Map Accessors</a></h4>
1020
1021 <hr>
1022
1023 <pre>
1024 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
1025 property_map&lt;adjacency_list, PropertyTag&gt;::type
1026 get(PropertyTag, adjacency_list&amp; g)
1027
1028 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>&gt;
1029 property_map&lt;adjacency_list, Tag&gt;::const_type
1030 get(PropertyTag, const adjacency_list&amp; g)
1031 </pre>
1032 Returns the property map object for the vertex property specified by
1033 <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the
1034 properties specified in the graph's <TT>VertexProperty</TT> template
1035 argument.
1036
1037 <hr>
1038
1039 <pre>
1040 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X&gt;
1041 typename property_traits&lt;property_map&lt;adjacency_list, PropertyTag&gt;::const_type&gt::value_type
1042 get(PropertyTag, const adjacency_list&amp; g, X x)
1043 </pre>
1044 This returns the property value for <tt>x</tt>, where <tt>x</tt> is either
1045 a vertex or edge descriptor.
1046 <hr>
1047
1048 <pre>
1049 template &lt;class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value&gt;
1050 void
1051 put(PropertyTag, const adjacency_list&amp; g, X x, const Value& value)
1052 </pre>
1053 This sets the property value for <tt>x</tt> to
1054 <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
1055 <tt>Value</tt> must be convertible to
1056 <tt>typename property_traits&lt;property_map&lt;adjacency_list, PropertyTag&gt;::type&gt::value_type</tt>
1057
1058 <hr>
1059
1060 <pre>
1061 template &lt;class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>&gt;
1062 typename graph_property&lt;adjacency_list, GraphPropertyTag&gt;::type&amp;
1063 get_property(adjacency_list&amp; g, GraphPropertyTag);
1064 </pre>
1065 Return the property specified by <tt>GraphPropertyTag</tt> that is
1066 attached to the graph object <tt>g</tt>. The <tt>graph_property</tt>
1067 traits class is defined in <a
1068 href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>.
1069
1070 <hr>
1071
1072 <pre>
1073 template &lt;class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>&gt;
1074 const typename graph_property&lt;adjacency_list, GraphPropertyTag&gt;::type&amp;
1075 get_property(const adjacency_list&amp; g, GraphPropertyTag);
1076 </pre>
1077 Return the property specified by <tt>GraphPropertyTag</tt> that is
1078 attached to the graph object <tt>g</tt>.  The <tt>graph_property</tt>
1079 traits class is defined in <a
1080 href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>.
1081
1082 <!-- add the shortcut property functions -->
1083
1084 <hr>
1085
1086
1087
1088 <h4><a name="serialization">Serialization</a></h4>
1089
1090 <hr>
1091
1092 <pre>
1093 template&lt;class <a href="../../serialization/doc/archives.html#saving_interface">SavingArchive</a>&gt;
1094 SavingArchive&amp; operator<<(SavingArchive&amp; ar, const adjacency_list&amp graph);
1095 </pre>
1096 Serializes the graph into the archive. Requires the vertex and edge properties of the
1097 graph to be <a href="../../serialization/doc/index.html">Serializable</a>.
1098 <br>
1099 Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>.
1100 <hr>
1101
1102 <pre>
1103 template&lt;class <a href="../../serialization/doc/archives.html#loading_interface">LoadingArchive</a>&gt;
1104 LoadingArchive&amp; operator>>(LoadingArchive&amp; ar, const adjacency_list&amp graph);
1105 </pre>
1106 Reads the graph from the archive. Requires the vertex and edge properties of the
1107 graph to be <a href="../../serialization/doc/index.html">Serializable</a>.
1108 <br>
1109 Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>.
1110 <hr>
1111
1112
1113 <h3>See Also</h3>
1114
1115 <a href="./adjacency_list_traits.html"><tt>adjacency_list_traits</tt></a>,
1116 <a href="./property_map.html"><tt>property_map</tt></a>,
1117 <a href="./graph_traits.html"><tt>graph_traits</tt></a>
1118
1119
1120
1121 <br>
1122 <HR>
1123 <TABLE>
1124 <TR valign=top>
1125 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
1126 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
1127 Indiana University (<A
1128 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
1129 <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
1130 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
1131 Indiana University (<A
1132 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
1133 </TD></TR></TABLE>
1134
1135 </BODY>
1136 </HTML>
1137 <!--  LocalWords:  gif ALT OutEdgeList EdgeList VertexList html VertexProperties EdgeProperties
1138  -->
1139 <!--  LocalWords:  GraphPropertyTag cpp enum ai cout endl VertexAndEdgeListGraph
1140  -->
1141 <!--  LocalWords:  MutablePropertyGraph hpp const ReadablePropertyMap listS num
1142  -->
1143 <!--  LocalWords:  ReadWritePropertyMap vecS dijkstra ucs pre Adj Iter Desc ep
1144  -->
1145 <!--  LocalWords:  EdgeIterator EdgePropertyIterator iter bool edge's IDs siek
1146  -->
1147 <!--  LocalWords:  multigraph typename htm Univ Quan Lumsdaine
1148  -->