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> 20adjacency_list<OutEdgeList, VertexList, Directed, 21 VertexProperties, EdgeProperties, 22 GraphProperties, EdgeList> 23</pre> 24</H1> 25 26 27<P> 28The <TT>adjacency_list</TT> class implements a generalized adjacency 29list graph structure. The template parameters provide many 30configuration options so that you can pick a version of the class that 31best meets your needs. An <a 32href="graph_theory_review.html#sec:adjacency-list-representation">adjacency-list</a> 33is basically a two-dimensional structure, where each element of the 34first dimension represents a vertex, and each of the vertices contains 35a one-dimensional structure that is its edge list. <a 36href="#fig:adj-list-graph">Figure 1</a> shows an adjacency list 37representation 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 48The 49<TT>VertexList</TT> template parameter of the <TT>adjacency_list</TT> 50class controls what kind of container is used to represent the outer 51two-dimensional container. The <TT>OutEdgeList</TT> template parameter 52controls what kind of container is used to represent the edge 53lists. The choices for <TT>OutEdgeList</TT> and <TT>VertexList</TT> will 54determine the space complexity of the graph structure, and will 55determine the time complexity of the various graph operations. The 56possible choices and tradeoffs are discussed in Section <A 57HREF="./using_adjacency_list.html#sec:choosing-graph-type">Choosing 58the <TT>Edgelist</TT> and <TT>VertexList</TT></A>. 59 60<P> 61The <TT>Directed</TT> template parameter controls whether the graph is 62directed, undirected, or directed with access to both the in-edges and 63out-edges (which we call bidirectional). The bidirectional graph takes 64up twice the space (per edge) of a directed graph since each edge will 65appear in both an out-edge and in-edge list. <a 66href="#fig:undir-adj-list-graph">Figure 2</a> shows an adjacency list 67representation 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> 79A tutorial on how to use the <TT>adjacency_list</TT> class is in 80Section <A HREF="./using_adjacency_list.html">Using 81<TT>adjacency_list</TT></A>. 82 83<P> 84 85<H3>Example</H3> 86 87<P> 88The example in <a 89href="../example/family_tree.cpp"><tt>examples/family_tree.cpp</tt></a> 90shows 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>, 153and <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> 162Also, 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> 169Properties such as color, distance, weight, and user-defined 170properties can be attached to the vertices and edges of the graph 171using properties. The property values can be read from and written to 172via the property maps provided by the graph. The property maps are 173obtained via the <TT>get(property, g)</TT> function. How to use 174properties is described in Section <A 175HREF="./using_adjacency_list.html#sec:adjacency-list-properties">Internal 176Properties </A>. The property maps are objects that implement the 177interface defined in Section <A 178HREF="../../property_map/doc/property_map.html">Property Map 179Concepts</A> or may be <a href="bundles.html">bundled properties</a>, 180which have a more succinct syntax. The types of all property values 181must be Copy Constructible, Assignable, and Default Constructible. 182The property maps obtained from the 183<TT>adjacency_list</TT> class are models of the <a 184href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property 185Map</a> concept. If the <TT>adjacency_list</TT> is const, 186then the property map is constant, otherwise the property 187map is mutable. 188 189<P> 190If the <TT>VertexList</TT> of the graph is <TT>vecS</TT>, then the 191graph has a builtin vertex indices accessed via the property map for 192the <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 194removed the indices are adjusted so that they retain these 195properties. Some care must be taken when using these indices to access 196exterior property storage. The property map for vertex index is a 197model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable 198Property Map</a>. 199 200<P> 201 202<h2>Iterator and Descriptor Stability/Invalidation</h2> 203 204Some care must be taken when changing the structure of a graph (via 205adding or removing edges). Depending on the type of 206<tt>adjacency_list</tt> and on the operation, some of the iterator or 207descriptor objects that point into the graph may become invalid. For 208example, the following code will result in undefined (bad) behavior: 209 210<pre> 211 typedef adjacency_list<listS, vecS> 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<Graph>::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<Graph>::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 229The 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 232all iterators and descriptors for the graph (such as <tt>vi</tt> and 233<tt>vi_end</tt>), thereby causing trouble in subsequent iterations of 234the loop. 235 236<p> 237 238If we use a different kind of <tt>adjacency_list</tt>, where 239<tt>VertexList=listS</tt>, then the iterators are not invalidated by 240calling <tt>remove_vertex</tt> unless the iterator is pointing to the 241actual vertex that was removed. The following code demonstrates this. 242 243<pre> 244 typedef adjacency_list<listS, listS> 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<Graph>::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<Graph>::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 264The stability issue also affects vertex and edge descriptors. For 265example, suppose you use vector of vertex descriptors to keep track of 266the parents (or predecessors) of vertices in a shortest paths tree 267(see <a 268href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>). 269You create the parent vector with a call to 270<tt>dijkstra_shortest_paths()</tt>, and then remove a vertex from the 271graph. Subsequently you try to use the parent vector, but since all 272vertex descriptors have become invalid, the result is incorrect. 273 274<pre> 275 std::vector<Vertex> parent(num_vertices(G)); 276 std::vector<Vertex> distance(num_vertices(G)); 277 278 dijkstra_shortest_paths(G, s, distance_map(&distance[0]). 279 predecessor_map(&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> 290Note that in this discussion iterator and descriptor invalidation is 291concerned 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 294descriptor for <i>(u,v)</i> or edge iterator pointing to <i>(u,v)</i>, 295regardless of the kind <tt>adjacency_list</tt>. In this discussion 296of iterator and descriptor invalidation, we are only concerned with the 297affect of <tt>remove_edge(u, v, g)</tt> on edge descriptors and 298iterators that point to other edges (not <i>(u,v)</i>). 299 300<p> 301In 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 305and iterator stability, and are more concerned about memory 306consumption and graph traversal speed, use <tt>vecS</tt> for the 307<tt>VertexList</tt> and/or <tt>OutEdgeList</tt> template parameters. 308 309<p> 310The following table summarizes which operations cause descriptors and 311iterators to become invalid. In the table, <tt>EL</tt> is an 312abbreviation 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 316descriptor and iterator invalidation is given in the documentation for 317each 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 && <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 && <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 && <br/> Directed=directedS</tt></td> 358 <td align=center><tt>VL=vecS && <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<adjacency_list>::vertex_descriptor</tt> 375<br> 376and 377<br> 378<tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::vertex_descriptor</tt> 379<br><br> 380The type for the vertex descriptors associated with the 381<TT>adjacency_list</TT>. 382 383<hr> 384 385<tt>graph_traits<adjacency_list>::edge_descriptor</tt><br> 386and<br> 387<tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_descriptor</tt> 388<br><br> 389The type for the edge descriptors associated with the 390<TT>adjacency_list</TT>. 391 392<hr> 393 394<tt>graph_traits<adjacency_list>::vertex_iterator</tt> 395<br><br> 396The type for the iterators returned by <TT>vertices()</TT>. 397 398When <tt>VertexList=vecS</tt> then the <tt>vertex_iterator</tt> models 399<a 400href="http://www.boost.org/sgi/stl/RandomAccessIterator.html">RandomAccessIterator</a>. Otherwise 401the <tt>vertex_iterator</tt> models <a 402href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>. 403 404<hr> 405 406<tt>graph_traits<adjacency_list>::edge_iterator</tt> 407<br><br> 408The type for the iterators returned by <TT>edges()</TT>. 409The <tt>edge_iterator</tt> models <a 410href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>. 411 412 413<hr> 414 415 416<tt>graph_traits<adjacency_list>::out_edge_iterator</tt> 417<br><br> 418 419The type for the iterators returned by <TT>out_edges()</TT>. 420When <tt>OutEdgeList=vecS</tt> then the <tt>out_edge_iterator</tt> models 421<a href="http://www.boost.org/sgi/stl/RandomAccessIterator.html"> 422RandomAccessIterator</a>. When <tt>OutEdgeList=slistS</tt> then the 423<tt>out_edge_iterator</tt> models <a 424href="http://www.boost.org/sgi/stl/ForwardIterator.html"> 425ForwardIterator</a>. Otherwise the <tt>out_edge_iterator</tt> models 426<a 427href="http://www.boost.org/sgi/stl/BidirectionalIterator.html"> 428BidirectionalIterator</a>. 429 430<hr> 431 432<tt>graph_traits<adjacency_list>::adjacency_iterator</tt> 433<br><br> 434The type for the iterators returned by <TT>adjacent_vertices()</TT>. 435The <tt>adjacency_iterator</tt> models the same iterator concept 436as <tt>out_edge_iterator</tt>. 437<hr> 438 439<tt>adjacency_list::inv_adjacency_iterator</tt> 440<br><br> 441The type for the iterators returned by <TT>inv_adjacent_vertices()</TT>. 442The <tt>inv_adjacency_iterator</tt> models the same iterator concept 443as <tt>out_edge_iterator</tt>. 444<hr> 445 446<tt>graph_traits<adjacency_list>::directed_category</tt><br> 447and<br> 448<tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::directed_category</tt> 449<br><br> 450Provides information about whether the graph is 451directed (<TT>directed_tag</TT>) or undirected 452(<TT>undirected_tag</TT>). 453 454<hr> 455 456<tt>graph_traits<adjacency_list>::edge_parallel_category</tt><br> 457and<br> 458<tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_parallel_category</tt> 459<br><br> 460This describes whether the graph class allows the insertion of 461parallel edges (edges with the same source and target). The two tags 462are <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 465parallel edges while the others allow parallel edges. 466 467<hr> 468 469<tt>graph_traits<adjacency_list>::vertices_size_type</tt><br> 470and<br> 471<tt>adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::vertices_size_type</tt><br> 472<br><br> 473The type used for dealing with the number of vertices in the graph. 474 475<hr> 476 477<tt>graph_traits<adjacency_list>::edges_size_type</tt><br> 478and<br> 479<tt>adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::edges_size_type</tt><br> 480<br><br> 481The type used for dealing with the number of edges in the graph. 482 483<hr> 484 485<tt>graph_traits<adjacency_list>::degree_size_type</tt> 486<br><br> 487The type used for dealing with the number of edges incident to a vertex 488in the graph. 489 490<hr> 491 492<tt>property_map<adjacency_list, Property>::type</tt><br> 493and<br> 494<tt>property_map<adjacency_list, Property>::const_type</tt> 495<br><br> 496The property map type for vertex or edge properties in the graph. The 497specific property is specified by the <TT>Property</TT> template argument, 498and 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<adjacency_list, Property>::type</tt> 504<br><br> 505The 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> 512The type <tt>OutEdgeListS</tt>. 513 514<hr> 515 516<tt>adjacency_list::vertex_list_selector</tt> 517<br><br> 518The type <tt>VertexListS</tt>. 519 520<hr> 521 522<tt>adjacency_list::directed_selector</tt> 523<br><br> 524The type <tt>DirectedS</tt>. 525 526<hr> 527 528<tt>adjacency_list::edge_list_selector</tt> 529<br><br> 530The type <tt>EdgeListS</tt>. 531 532<hr> 533 534<H2>Member Functions</H2> 535 536<hr> 537 538<pre> 539adjacency_list(const GraphProperty& p = GraphProperty()) 540</pre> 541Default constructor. Creates an empty graph object with zero vertices 542and zero edges. 543 544<hr> 545 546<pre> 547adjacency_list(const adjacency_list& x) 548</pre> 549Copy 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> 555adjacency_list& operator=(const adjacency_list& x) 556</pre> 557Assignment operator. Makes this graph a copy of graph 558<tt>x</tt>, including the edges, vertices, and properties. 559 560<hr> 561 562<pre> 563adjacency_list(vertices_size_type n, 564 const GraphProperty& p = GraphProperty()) 565</pre> 566Creates a graph object with <TT>n</TT> vertices and zero edges. 567 568<hr> 569 570<a name="sec:iterator-constructor"> 571<pre> 572template <class EdgeIterator> 573adjacency_list(EdgeIterator first, EdgeIterator last, 574 vertices_size_type n, 575 edges_size_type m = 0, 576 const GraphProperty& p = GraphProperty()) 577</pre> 578Creates a graph object with <TT>n</TT> vertices and with the edges 579specified in the edge list given by the range <TT>[first, last)</TT>. 580The <tt>EdgeIterator</tt> must be a model of <a 581href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>. 582The 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 584integers will correspond to vertices, and they must all fall in the 585range of <TT>[0, n)</TT>. 586</a> 587 588<hr> 589 590<pre> 591template <class EdgeIterator, class EdgePropertyIterator> 592adjacency_list(EdgeIterator first, EdgeIterator last, 593 EdgePropertyIterator ep_iter, 594 vertices_size_type n, 595 edges_size_type m = 0, 596 const GraphProperty& p = GraphProperty()) 597</pre> 598Creates a graph object with <TT>n</TT> vertices and with the edges 599specified in the edge list given by the range <TT>[first, last)</TT>. 600The <tt>EdgeIterator</tt> and <tt>EdgePropertyIterator</tt> must be a 601model of <a 602href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>. 603The 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 605integers will correspond to vertices, and they must all fall in the 606range 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> 612void clear() 613</pre> 614Remove all of the edges and vertices from the graph. 615 616<hr> 617 618<pre> 619void swap(adjacency_list& x) 620</pre> 621Swap the vertices, edges, and properties of this graph with the 622vertices, 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> 635std::pair<vertex_iterator, vertex_iterator> 636vertices(const adjacency_list& g) 637</pre> 638Returns an iterator-range providing access to the vertex set of graph 639<tt>g</tt>. 640 641<hr> 642 643<pre> 644std::pair<edge_iterator, edge_iterator> 645edges(const adjacency_list& g) 646</pre> 647Returns an iterator-range providing access to the edge set of graph 648<tt>g</tt>. 649 650<hr> 651 652<pre> 653std::pair<adjacency_iterator, adjacency_iterator> 654adjacent_vertices(vertex_descriptor u, const adjacency_list& g) 655</pre> 656Returns an iterator-range providing access to the vertices adjacent to 657vertex <tt>u</tt> in graph <tt>g</tt>. For example, if <tt>u -> v</tt> 658is an edge in the graph, then <tt>v</tt> will be in this iterator-range. 659 660<hr> 661 662<pre> 663std::pair<inv_adjacency_iterator, inv_adjacency_iterator> 664inv_adjacent_vertices(vertex_descriptor u, const adjacency_list& g) 665</pre> 666 667Returns 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 669inverse.) For example, if <tt>v -> u</tt> is an edge in the graph, 670then <tt>v</tt> will be in this iterator range. This function is only 671available for bidirectional and undirected <tt>adjacency_list</tt>'s. 672 673<hr> 674 675 676<pre> 677std::pair<out_edge_iterator, out_edge_iterator> 678out_edges(vertex_descriptor u, const adjacency_list& g) 679</pre> 680Returns 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 682iterator-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> 685where <tt>v</tt> is a vertex adjacent to <tt>u</tt>. 686 687<hr> 688 689<pre> 690std::pair<in_edge_iterator, in_edge_iterator> 691in_edges(vertex_descriptor v, const adjacency_list& g) 692</pre> 693Returns 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> 696template parameter. For an in-edge <tt>e</tt>, <tt>target(e, g) == v</tt> 697and <tt>source(e, g) == u</tt> for some vertex <tt>u</tt> that is 698adjacent to <tt>v</tt>, whether the graph is directed or undirected. 699 700<hr> 701 702<pre> 703vertex_descriptor 704source(edge_descriptor e, const adjacency_list& g) 705</pre> 706Returns the source vertex of edge <tt>e</tt>. 707 708<hr> 709 710<pre> 711vertex_descriptor 712target(edge_descriptor e, const adjacency_list& g) 713</pre> 714Returns the target vertex of edge <tt>e</tt>. 715 716<hr> 717 718<pre> 719degree_size_type 720out_degree(vertex_descriptor u, const adjacency_list& g) 721</pre> 722Returns the number of edges leaving vertex <tt>u</tt>. 723 724<hr> 725 726<pre> 727degree_size_type 728in_degree(vertex_descriptor u, const adjacency_list& g) 729</pre> 730Returns the number of edges entering vertex <tt>u</tt>. This operation 731is only available if <TT>bidirectionalS</TT> was specified for 732the <TT>Directed</TT> template parameter. 733 734<hr> 735 736<pre> 737vertices_size_type 738num_vertices(const adjacency_list& g) 739</pre> 740Returns the number of vertices in the graph <tt>g</tt>. 741 742<hr> 743 744<pre> 745edges_size_type 746num_edges(const adjacency_list& g) 747</pre> 748Returns the number of edges in the graph <tt>g</tt>. 749 750<hr> 751 752<pre> 753vertex_descriptor 754vertex(vertices_size_type n, const adjacency_list& g) 755</pre> 756Returns the nth vertex in the graph's vertex list. 757 758<hr> 759 760 761<pre> 762std::pair<edge_descriptor, bool> 763edge(vertex_descriptor u, vertex_descriptor v, 764 const adjacency_list& g) 765</pre> 766If an edge from vertex <tt>u</tt> to vertex <tt>v</tt> exists, return a pair 767containing 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> 774std::pair<out_edge_iterator, out_edge_iterator> 775edge_range(vertex_descriptor u, vertex_descriptor v, 776 const adjacency_list& g) 777</pre> 778Returns a pair of out-edge iterators that give the range for 779all the parallel edges from <tt>u</tt> to <tt>v</tt>. This 780function only works when the <tt>OutEdgeList</tt> for the 781<tt>adjacency_list</tt> is a container that sorts the 782out edges according to target vertex, and allows for 783parallel edges. The <tt>multisetS</tt> selector chooses 784such a container. 785 786<hr> 787 788<h4>Structure Modification</h4> 789 790<hr> 791 792<pre> 793std::pair<edge_descriptor, bool> 794add_edge(vertex_descriptor u, vertex_descriptor v, 795 adjacency_list& g) 796</pre> 797Adds edge <i>(u,v)</i> to the graph and returns the edge descriptor 798for the new edge. For graphs that do not allow parallel edges, if the 799edge is already in the graph then a duplicate will not be added and 800the <TT>bool</TT> flag will be <TT>false</TT>. When the flag is 801<TT>false</TT>, the 802returned edge descriptor points to the already existing edge. 803 804<p> 805The placement of the new edge in the out-edge list is in general 806unspecified, though ordering of the out-edge list can be accomplished 807through the choice of <tt>OutEdgeList</tt>. 808 809If 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 812number of vertices in the graph, the graph is enlarged so that the 813number of vertices is <tt>std::max(u,v) + 1</tt>. 814 815<p> 816If the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation 817will 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 819container that invalidates its iterators when <TT>push(container, 820x)</TT> is invoked (see Section <A 821HREF="./using_adjacency_list.html#sec:custom-storage">Customizing the 822Adjacency List Storage</A>). If the graph is also bidirectional then 823any <tt>in_edge_iterator</tt> for <i>v</i> is also invalidated. If 824instead the graph is undirected then any <tt>out_edge_iterator</tt> 825for <i>v</i> is also invalidated. If instead the graph is directed, 826then <tt>add_edge()</tt> also invalidates any <tt>edge_iterator</tt>. 827 828 829<hr> 830 831<pre> 832std::pair<edge_descriptor, bool> 833add_edge(vertex_descriptor u, vertex_descriptor v, 834 const EdgeProperties& p, 835 adjacency_list& g) 836</pre> 837Adds edge <i>(u,v)</i> to the graph and attaches <TT>p</TT> as the 838value of the edge's internal property storage. Also see the previous 839<TT>add_edge()</TT> non-member function for more details. 840 841<hr> 842 843<pre> 844void remove_edge(vertex_descriptor u, vertex_descriptor v, 845 adjacency_list& g) 846</pre> 847Removes the edge <i>(u,v)</i> from the graph. 848<p> 849This operation causes any outstanding edge descriptors or iterators 850that point to edge <i>(u,v)</i> to become invalid. In addition, if 851the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation 852will 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 854bidirectional case. Also, for directed graphs this invalidates any 855<tt>edge_iterator</tt>. 856 857<hr> 858 859<pre> 860void remove_edge(edge_descriptor e, adjacency_list& g) 861</pre> 862Removes 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 864multigraph. This <tt>remove_edge(e, g)</tt> function removes a single 865edge, whereas the <tt>remove_edge(u, v, g)</tt> function removes all 866edges <i>(u,v)</i>. 867<p> 868This operation invalidates any outstanding edge descriptors and 869iterators for the same edge pointed to by descriptor <tt>e</tt>. In 870addition, this operation will invalidate any iterators that point into 871the edge-list for the <tt>target(e, g)</tt>. Also, for directed 872graphs this invalidates any <tt>edge_iterator</tt> for the graph. 873 874<hr> 875 876<pre> 877void remove_edge(out_edge_iterator iter, adjacency_list& g) 878</pre> 879This has the same effect as <tt>remove_edge(*iter, g)</tt>. The 880difference is that this function has constant time complexity 881in the case of directed graphs, whereas <tt>remove_edge(e, g)</tt> 882has time complexity <i>O(E/V)</i>. 883 884<hr> 885 886<pre> 887template <class <a href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>> 888void remove_out_edge_if(vertex_descriptor u, Predicate predicate, 889 adjacency_list& g) 890</pre> 891Removes all out-edges of vertex <i>u</i> from the graph that satisfy 892the <tt>predicate</tt>. That is, if the predicate returns true when 893applied to an edge descriptor, then the edge is removed. 894<p> 895The affect on descriptor and iterator stability is the same as that of 896invoking <tt>remove_edge()</tt> on each of the removed edges. 897 898<hr> 899 900<pre> 901template <class <a 902href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>> 903void remove_in_edge_if(vertex_descriptor v, Predicate predicate, 904 adjacency_list& g) 905</pre> 906Removes all in-edges of vertex <i>v</i> from the graph that satisfy 907the <tt>predicate</tt>. That is, if the predicate returns true when 908applied to an edge descriptor, then the edge is removed. 909<p> 910The affect on descriptor and iterator stability is the 911same as that of invoking <tt>remove_edge()</tt> on each of the 912removed edges. 913<p> 914This operation is available for undirected and bidirectional 915<tt>adjacency_list</tt> graphs, but not for directed. 916 917<hr> 918 919<pre> 920template <class <a href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>> 921void remove_edge_if(Predicate predicate, adjacency_list& g) 922</pre> 923Removes all edges from the graph that satisfy 924the <tt>predicate</tt>. That is, if the predicate returns true when 925applied to an edge descriptor, then the edge is removed. 926<p> 927The affect on descriptor and iterator stability is the same as that of 928invoking <tt>remove_edge()</tt> on each of the removed edges. 929 930<hr> 931 932<a name="sec:add-vertex"> 933<pre> 934vertex_descriptor 935add_vertex(adjacency_list& g) 936</pre> 937Adds a vertex to the graph and returns the vertex descriptor for the 938new vertex. 939</a> 940 941<hr> 942 943<pre> 944vertex_descriptor 945add_vertex(const VertexProperties& p, 946 adjacency_list& g) 947</pre> 948Adds a vertex to the graph with the specified properties. Returns the 949vertex descriptor for the new vertex. 950</a> 951 952<hr> 953 954<pre> 955void clear_vertex(vertex_descriptor u, adjacency_list& g) 956</pre> 957Removes all edges to and from vertex <i>u</i>. The vertex still appears 958in the vertex set of the graph. 959<p> 960The affect on descriptor and iterator stability is the 961same as that of invoking <tt>remove_edge()</tt> for all of 962the edges that have <tt>u</tt> as the source or target. 963 964<hr> 965 966<pre> 967void clear_out_edges(vertex_descriptor u, adjacency_list& g) 968</pre> 969Removes all out-edges from vertex <i>u</i>. The vertex still appears 970in the vertex set of the graph. 971<p> 972The affect on descriptor and iterator stability is the 973same as that of invoking <tt>remove_edge()</tt> for all of 974the edges that have <tt>u</tt> as the source. 975<p> 976This operation is not applicable to undirected graphs 977(use <tt>clear_vertex()</tt> instead). 978 979<hr> 980 981<pre> 982void clear_in_edges(vertex_descriptor u, adjacency_list& g) 983</pre> 984Removes all in-edges from vertex <i>u</i>. The vertex still appears 985in the vertex set of the graph. 986<p> 987The affect on descriptor and iterator stability is the 988same as that of invoking <tt>remove_edge()</tt> for all of 989the edges that have <tt>u</tt> as the target. 990<p> 991This operation is only applicable to bidirectional graphs. 992 993<hr> 994 995<pre> 996void remove_vertex(vertex_descriptor u, adjacency_list& g) 997</pre> 998Remove vertex <i>u</i> from the vertex set of the graph. It is assumed 999that there are no edges to or from vertex <i>u</i> when it is removed. 1000One way to make sure of this is to invoke <TT>clear_vertex()</TT> 1001beforehand. 1002<p> 1003If the <TT>VertexList</TT> template parameter of the 1004<TT>adjacency_list</TT> was <TT>vecS</TT>, then all vertex 1005descriptors, edge descriptors, and iterators for the graph are 1006invalidated by this operation. The builtin 1007<tt>vertex_index_t</tt> property for each vertex is renumbered so that 1008after the operation the vertex indices still form a contiguous range 1009<TT>[0, num_vertices(g))</TT>. If you are using external property 1010storage based on the builtin vertex index, then the external storage 1011will need to be adjusted. Another option is to not use the builtin 1012vertex index, and instead use a property to add your own vertex index 1013property. If you need to make frequent use of the 1014<TT>remove_vertex()</TT> function the <TT>listS</TT> selector is a 1015much 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> 1024template <class <a href="./PropertyTag.html">PropertyTag</a>> 1025property_map<adjacency_list, PropertyTag>::type 1026get(PropertyTag, adjacency_list& g) 1027 1028template <class <a href="./PropertyTag.html">PropertyTag</a>> 1029property_map<adjacency_list, Tag>::const_type 1030get(PropertyTag, const adjacency_list& g) 1031</pre> 1032Returns the property map object for the vertex property specified by 1033<TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the 1034properties specified in the graph's <TT>VertexProperty</TT> template 1035argument. 1036 1037<hr> 1038 1039<pre> 1040template <class <a href="./PropertyTag.html">PropertyTag</a>, class X> 1041typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type 1042get(PropertyTag, const adjacency_list& g, X x) 1043</pre> 1044This returns the property value for <tt>x</tt>, where <tt>x</tt> is either 1045a vertex or edge descriptor. 1046<hr> 1047 1048<pre> 1049template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> 1050void 1051put(PropertyTag, const adjacency_list& g, X x, const Value& value) 1052</pre> 1053This 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<property_map<adjacency_list, PropertyTag>::type>::value_type</tt> 1057 1058<hr> 1059 1060<pre> 1061template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 1062typename graph_property<adjacency_list, GraphPropertyTag>::type& 1063get_property(adjacency_list& g, GraphPropertyTag); 1064</pre> 1065Return the property specified by <tt>GraphPropertyTag</tt> that is 1066attached to the graph object <tt>g</tt>. The <tt>graph_property</tt> 1067traits class is defined in <a 1068href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>. 1069 1070<hr> 1071 1072<pre> 1073template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> 1074const typename graph_property<adjacency_list, GraphPropertyTag>::type& 1075get_property(const adjacency_list& g, GraphPropertyTag); 1076</pre> 1077Return the property specified by <tt>GraphPropertyTag</tt> that is 1078attached to the graph object <tt>g</tt>. The <tt>graph_property</tt> 1079traits class is defined in <a 1080href="../../../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> 1093template<class <a href="../../serialization/doc/archives.html#saving_interface">SavingArchive</a>> 1094SavingArchive& operator<<(SavingArchive& ar, const adjacency_list& graph); 1095</pre> 1096Serializes the graph into the archive. Requires the vertex and edge properties of the 1097graph to be <a href="../../serialization/doc/index.html">Serializable</a>. 1098<br> 1099Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>. 1100<hr> 1101 1102<pre> 1103template<class <a href="../../serialization/doc/archives.html#loading_interface">LoadingArchive</a>> 1104LoadingArchive& operator>>(LoadingArchive& ar, const adjacency_list& graph); 1105</pre> 1106Reads the graph from the archive. Requires the vertex and edge properties of the 1107graph to be <a href="../../serialization/doc/index.html">Serializable</a>. 1108<br> 1109Include <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 © 2000-2001</TD><TD> 1126<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 1127Indiana University (<A 1128HREF="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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 1131Indiana University (<A 1132HREF="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 --> 1149
