12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148 |
- <HTML>
- <!--
- Copyright (c) Jeremy Siek 2000
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <Title>Boost Graph Library: Adjacency List</Title>
- <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
- <IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
- <BR Clear>
- <H1><A NAME="sec:adjacency-list-class"></A>
- <pre>
- adjacency_list<OutEdgeList, VertexList, Directed,
- VertexProperties, EdgeProperties,
- GraphProperties, EdgeList>
- </pre>
- </H1>
- <P>
- The <TT>adjacency_list</TT> class implements a generalized adjacency
- list graph structure. The template parameters provide many
- configuration options so that you can pick a version of the class that
- best meets your needs. An <a
- href="graph_theory_review.html#sec:adjacency-list-representation">adjacency-list</a>
- is basically a two-dimensional structure, where each element of the
- first dimension represents a vertex, and each of the vertices contains
- a one-dimensional structure that is its edge list. <a
- href="#fig:adj-list-graph">Figure 1</a> shows an adjacency list
- representation of a directed graph.
- <P></P>
- <DIV ALIGN="center"><A NAME="fig:adj-list-graph"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> Adjacency List Representation of a Directed Graph.</CAPTION>
- <TR><TD><IMG SRC="./figs/adj-matrix-graph2.gif" width="386" height="284"></TD>
- <TD><IMG SRC="./figs/adj-list2.gif" width="62" height="122"></TD></TR>
- </TABLE>
- </DIV><P></P>
- The
- <TT>VertexList</TT> template parameter of the <TT>adjacency_list</TT>
- class controls what kind of container is used to represent the outer
- two-dimensional container. The <TT>OutEdgeList</TT> template parameter
- controls what kind of container is used to represent the edge
- lists. The choices for <TT>OutEdgeList</TT> and <TT>VertexList</TT> will
- determine the space complexity of the graph structure, and will
- determine the time complexity of the various graph operations. The
- possible choices and tradeoffs are discussed in Section <A
- HREF="./using_adjacency_list.html#sec:choosing-graph-type">Choosing
- the <TT>Edgelist</TT> and <TT>VertexList</TT></A>.
- <P>
- The <TT>Directed</TT> template parameter controls whether the graph is
- directed, undirected, or directed with access to both the in-edges and
- out-edges (which we call bidirectional). The bidirectional graph takes
- up twice the space (per edge) of a directed graph since each edge will
- appear in both an out-edge and in-edge list. <a
- href="#fig:undir-adj-list-graph">Figure 2</a> shows an adjacency list
- representation of an undirected graph.
- <P></P>
- <DIV ALIGN="center"><A NAME="fig:undir-adj-list-graph"></A>
- <TABLE>
- <CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG> Adjacency List Representation of an Undirected Graph.</CAPTION>
- <TR><TD><IMG SRC="./figs/undir-adj-matrix-graph2.gif" width="260" height="240"></TD>
- <TD><IMG SRC="./figs/undir-adj-list.gif" width="62" height="122"></TD></TR>
- </TABLE>
- </DIV><P></P>
- <P>
- A tutorial on how to use the <TT>adjacency_list</TT> class is in
- Section <A HREF="./using_adjacency_list.html">Using
- <TT>adjacency_list</TT></A>.
- <P>
- <H3>Example</H3>
- <P>
- The example in <a
- href="../example/family-tree-eg.cpp"><tt>examples/family-tree-eg.cpp</tt></a>
- shows how to represent a family tree with a graph.
- <H3>Template Parameters</H3>
- <P>
- <TABLE border>
- <TR>
- <th>Parameter</th><th>Description</th><th>Default</th>
- </tr>
- <TR><TD><TT>OutEdgeList</TT></TD>
- <TD>The selector for the container used to represent the
- edge-list for each of the vertices.</TD>
- <TD><TT>vecS</TT></TD>
- </TR>
- <TR>
- <TD><TT>VertexList</TT></TD>
- <TD>The selector for the container used to represent the
- vertex-list of the graph.</TD>
- <TD><TT>vecS</TT></TD>
- </TR>
- <TR>
- <TD><TT>Directed</TT></TD>
- <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>
- <TD><TT>directedS</TT></TD>
- </TR>
- <TR>
- <TD><TT>VertexProperties</TT></TD>
- <TD>for specifying internal property storage.</TD>
- <TD><TT>no_property</TT></TD>
- </TR>
- <TR>
- <TD><TT>EdgeProperties</TT></TD>
- <TD>for specifying internal property storage.</TD>
- <TD><TT>no_property</TT></TD>
- </TR>
- <TR>
- <TD><TT>GraphProperties</TT></TD>
- <TD>for specifying property storage for the graph object.</TD>
- <TD><TT>no_property</TT></TD>
- </TR>
- <TR><TD><TT>EdgeList</TT></TD>
- <TD>The selector for the container used to represent the
- edge-list for the graph.</TD>
- <TD><TT>listS</TT></TD>
- </TR>
- </TABLE>
- <P>
- <H3>Model of</H3>
- <P>
- <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>,
- <a href="./MutablePropertyGraph.html">MutablePropertyGraph</a>,
- <a href="../../utility/CopyConstructible.html">CopyConstructible</a>,
- <a href="../../utility/Assignable.html">Assignable</a>,
- and <a href="../../serialization/doc/index.html">Serializable</a>.
- <P>
- <H3>Where Defined</H3>
- <P>
- <a href="../../../boost/graph/adjacency_list.hpp"><TT>boost/graph/adjacency_list.hpp</TT></a><br><br>
- Also, the serialization functionality is in
- <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>.
- <P>
- <H2>Vertex and Edge Properties</H2>
- <P>
- Properties such as color, distance, weight, and user-defined
- properties can be attached to the vertices and edges of the graph
- using properties. The property values can be read from and written to
- via the property maps provided by the graph. The property maps are
- obtained via the <TT>get(property, g)</TT> function. How to use
- properties is described in Section <A
- HREF="./using_adjacency_list.html#sec:adjacency-list-properties">Internal
- Properties </A>. The property maps are objects that implement the
- interface defined in Section <A
- HREF="../../property_map/doc/property_map.html">Property Map
- Concepts</A> or may be <a href="bundles.html">bundled properties</a>,
- which have a more succinct syntax. The types of all property values
- must be Copy Constructible, Assignable, and Default Constructible.
- The property maps obtained from the
- <TT>adjacency_list</TT> class are models of the <a
- href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
- Map</a> concept. If the <TT>adjacency_list</TT> is const,
- then the property map is constant, otherwise the property
- map is mutable.
- <P>
- If the <TT>VertexList</TT> of the graph is <TT>vecS</TT>, then the
- graph has a builtin vertex indices accessed via the property map for
- the <TT>vertex_index_t</TT> property. The indices fall in the range
- <TT>[0, num_vertices(g))</TT> and are contiguous. When a vertex is
- removed the indices are adjusted so that they retain these
- properties. Some care must be taken when using these indices to access
- exterior property storage. The property map for vertex index is a
- model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
- Property Map</a>.
- <P>
- <h2>Iterator and Descriptor Stability/Invalidation</h2>
- Some care must be taken when changing the structure of a graph (via
- adding or removing edges). Depending on the type of
- <tt>adjacency_list</tt> and on the operation, some of the iterator or
- descriptor objects that point into the graph may become invalid. For
- example, the following code will result in undefined (bad) behavior:
- <pre>
- typedef adjacency_list<listS, vecS> Graph; <b>// VertexList=vecS</b>
- Graph G(N);
- <b>// Fill in the graph...</b>
- <b>// Attempt to remove all the vertices. Wrong!</b>
- graph_traits<Graph>::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
- remove_vertex(*vi, G);
- <b>// Remove all the vertices. This is still wrong!</b>
- graph_traits<Graph>::vertex_iterator vi, vi_end, next;
- boost::tie(vi, vi_end) = vertices(G);
- for (next = vi; vi != vi_end; vi = next) {
- ++next;
- remove_vertex(*vi, G);
- }
- </pre>
- The reason this is a problem is that we are invoking
- <tt>remove_vertex()</tt>, which when used with an
- <tt>adjacency_list</tt> where <tt>VertexList=vecS</tt>, invalidates
- all iterators and descriptors for the graph (such as <tt>vi</tt> and
- <tt>vi_end</tt>), thereby causing trouble in subsequent iterations of
- the loop.
- <p>
- If we use a different kind of <tt>adjacency_list</tt>, where
- <tt>VertexList=listS</tt>, then the iterators are not invalidated by
- calling <tt>remove_vertex</tt> unless the iterator is pointing to the
- actual vertex that was removed. The following code demonstrates this.
- <pre>
- typedef adjacency_list<listS, listS> Graph; <b>// VertexList=listS</b>
- Graph G(N);
- <b>// Fill in the graph...</b>
- <b>// Attempt to remove all the vertices. Wrong!</b>
- graph_traits<Graph>::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
- remove_vertex(*vi, G);
- <b>// Remove all the vertices. This is OK.</b>
- graph_traits<Graph>::vertex_iterator vi, vi_end, next;
- boost::tie(vi, vi_end) = vertices(G);
- for (next = vi; vi != vi_end; vi = next) {
- ++next;
- remove_vertex(*vi, G);
- }
- </pre>
- <p>
- The stability issue also affects vertex and edge descriptors. For
- example, suppose you use vector of vertex descriptors to keep track of
- the parents (or predecessors) of vertices in a shortest paths tree
- (see <a
- href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>).
- You create the parent vector with a call to
- <tt>dijkstra_shortest_paths()</tt>, and then remove a vertex from the
- graph. Subsequently you try to use the parent vector, but since all
- vertex descriptors have become invalid, the result is incorrect.
- <pre>
- std::vector<Vertex> parent(num_vertices(G));
- std::vector<Vertex> distance(num_vertices(G));
- dijkstra_shortest_paths(G, s, distance_map(&distance[0]).
- predecessor_map(&parent[0]));
- remove_vertex(s, G); <b>// Bad idea! Invalidates vertex descriptors in parent vector.</b>
- <b>// The following will produce incorrect results</b>
- for(boost::tie(vi, vend) = vertices(G); vi != vend; ++vi)
- std::cout << p[*vi] << " is the parent of " << *vi << std::endl;
- </pre>
- <p>
- Note that in this discussion iterator and descriptor invalidation is
- concerned with the invalidation of iterators and descriptors that are
- <b>not directly affected</b> by the operation. For example, performing
- <tt>remove_edge(u, v, g)</tt> will always invalidate any edge
- descriptor for <i>(u,v)</i> or edge iterator pointing to <i>(u,v)</i>,
- regardless of the kind <tt>adjacency_list</tt>. In this discussion
- of iterator and descriptor invalidation, we are only concerned with the
- affect of <tt>remove_edge(u, v, g)</tt> on edge descriptors and
- iterators that point to other edges (not <i>(u,v)</i>).
- <p>
- In general, if you want your vertex and edge descriptors to be stable
- (never invalidated) then use <tt>listS</tt> or <tt>setS</tt> for the
- <tt>VertexList</tt> and <tt>OutEdgeList</tt> template parameters of
- <tt>adjacency_list</tt>. If you are not as concerned about descriptor
- and iterator stability, and are more concerned about memory
- consumption and graph traversal speed, use <tt>vecS</tt> for the
- <tt>VertexList</tt> and/or <tt>OutEdgeList</tt> template parameters.
- <p>
- The following table summarizes which operations cause descriptors and
- iterators to become invalid. In the table, <tt>EL</tt> is an
- abbreviation for <tt>OutEdgeList</tt> and <tt>VL</tt> means
- <tt>VertexList</tt>. The <b>Adj Iter</b> category includes the
- <tt>out_edge_iterator</tt>, <tt>in_edge_iterator</tt>, and
- <tt>adjacency_iterator</tt> types. A more detailed description of
- descriptor and iterator invalidation is given in the documentation for
- each operation.
- <p>
- <table border>
- <CAPTION ALIGN="BOTTOM"><STRONG>Table:</STRONG>
- Summary of Descriptor and Iterator Invalidation.
- </CAPTION>
- <tr>
- <th>Function</th>
- <th>Vertex Desc</th>
- <th>Edge Desc</th>
- <th>Vertex Iter</th>
- <th>Edge Iter</th>
- <th>Adj Iter</th>
- </tr>
- <tr>
- <td>
- <tt>add_edge()</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>EL=vecS && <br>Directed=directedS</tt></td>
- <td align=center><tt>EL=vecS</tt></td>
- </tr>
- <tr>
- <td><tt>remove_edge()<br>remove_edge_if()<br>remove_out_edge_if()<br>
- remove_in_edge_if()<br>clear_vertex()</tt>
- </td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>EL=vecS && <br>Directed=directedS</tt></td>
- <td align=center><tt>EL=vecS</tt></td>
- </tr>
- <tr>
- <td><tt>add_vertex()</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>OK</tt></td>
- <td align=center><tt>VL=vecS && <br/> Directed=directedS</tt></td>
- <td align=center><tt>VL=vecS && <br/> Directed=directedS</tt></td>
- </tr>
- <tr>
- <td><tt>remove_vertex()</tt></td>
- <td align=center><tt>VL=vecS</tt></td>
- <td align=center><tt>VL=vecS</tt></td>
- <td align=center><tt>VL=vecS</tt></td>
- <td align=center><tt>VL=vecS</tt></td>
- <td align=center><tt>VL=vecS</tt></td>
- </tr>
- </table>
- <H2>Associated Types</H2>
- <hr>
- <tt>graph_traits<adjacency_list>::vertex_descriptor</tt>
- <br>
- and
- <br>
- <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::vertex_descriptor</tt>
- <br><br>
- The type for the vertex descriptors associated with the
- <TT>adjacency_list</TT>.
- <hr>
- <tt>graph_traits<adjacency_list>::edge_descriptor</tt><br>
- and<br>
- <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_descriptor</tt>
- <br><br>
- The type for the edge descriptors associated with the
- <TT>adjacency_list</TT>.
- <hr>
- <tt>graph_traits<adjacency_list>::vertex_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>vertices()</TT>.
- When <tt>VertexList=vecS</tt> then the <tt>vertex_iterator</tt> models
- <a
- href="http://www.boost.org/sgi/stl/RandomAccessIterator.html">RandomAccessIterator</a>. Otherwise
- the <tt>vertex_iterator</tt> models <a
- href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
- <hr>
- <tt>graph_traits<adjacency_list>::edge_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>edges()</TT>.
- The <tt>edge_iterator</tt> models <a
- href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>.
- <hr>
- <tt>graph_traits<adjacency_list>::out_edge_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>out_edges()</TT>.
- When <tt>OutEdgeList=vecS</tt> then the <tt>out_edge_iterator</tt> models
- <a href="http://www.boost.org/sgi/stl/RandomAccessIterator.html">
- RandomAccessIterator</a>. When <tt>OutEdgeList=slistS</tt> then the
- <tt>out_edge_iterator</tt> models <a
- href="http://www.boost.org/sgi/stl/ForwardIterator.html">
- ForwardIterator</a>. Otherwise the <tt>out_edge_iterator</tt> models
- <a
- href="http://www.boost.org/sgi/stl/BidirectionalIterator.html">
- BidirectionalIterator</a>.
- <hr>
- <tt>graph_traits<adjacency_list>::adjacency_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>adjacent_vertices()</TT>.
- The <tt>adjacency_iterator</tt> models the same iterator concept
- as <tt>out_edge_iterator</tt>.
- <hr>
- <tt>adjacency_list::inv_adjacency_iterator</tt>
- <br><br>
- The type for the iterators returned by <TT>inv_adjacent_vertices()</TT>.
- The <tt>inv_adjacency_iterator</tt> models the same iterator concept
- as <tt>out_edge_iterator</tt>.
- <hr>
- <tt>graph_traits<adjacency_list>::directed_category</tt><br>
- and<br>
- <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::directed_category</tt>
- <br><br>
- Provides information about whether the graph is
- directed (<TT>directed_tag</TT>) or undirected
- (<TT>undirected_tag</TT>).
- <hr>
- <tt>graph_traits<adjacency_list>::edge_parallel_category</tt><br>
- and<br>
- <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_parallel_category</tt>
- <br><br>
- This describes whether the graph class allows the insertion of
- parallel edges (edges with the same source and target). The two tags
- are <TT>allow_parallel_edge_tag</TT> and
- <TT>disallow_parallel_edge_tag</TT>. The
- <TT>setS</TT> and <TT>hash_setS</TT> variants disallow
- parallel edges while the others allow parallel edges.
- <hr>
- <tt>graph_traits<adjacency_list>::vertices_size_type</tt><br>
- and<br>
- <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::vertices_size_type</tt><br>
- <br><br>
- The type used for dealing with the number of vertices in the graph.
- <hr>
- <tt>graph_traits<adjacency_list>::edges_size_type</tt><br>
- and<br>
- <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::edges_size_type</tt><br>
- <br><br>
- The type used for dealing with the number of edges in the graph.
- <hr>
- <tt>graph_traits<adjacency_list>::degree_size_type</tt>
- <br><br>
- The type used for dealing with the number of edges incident to a vertex
- in the graph.
- <hr>
- <tt>property_map<adjacency_list, Property>::type</tt><br>
- and<br>
- <tt>property_map<adjacency_list, Property>::const_type</tt>
- <br><br>
- The property map type for vertex or edge properties in the graph. The
- specific property is specified by the <TT>Property</TT> template argument,
- and must match one of the properties specified in the
- <TT>VertexProperties</TT> or <TT>EdgeProperties</TT> for the graph.
- <hr>
- <tt>graph_property<adjacency_list, Property>::type</tt>
- <br><br>
- The property value type for the graph property specified by the
- <tt>Property</tt> tag.
- <hr>
- <tt>adjacency_list::out_edge_list_selector</tt>
- <br><br>
- The type <tt>OutEdgeListS</tt>.
- <hr>
- <tt>adjacency_list::vertex_list_selector</tt>
- <br><br>
- The type <tt>VertexListS</tt>.
- <hr>
- <tt>adjacency_list::directed_selector</tt>
- <br><br>
- The type <tt>DirectedS</tt>.
- <hr>
- <tt>adjacency_list::edge_list_selector</tt>
- <br><br>
- The type <tt>EdgeListS</tt>.
- <hr>
- <H2>Member Functions</H2>
- <hr>
- <pre>
- adjacency_list(const GraphProperty& p = GraphProperty())
- </pre>
- Default constructor. Creates an empty graph object with zero vertices
- and zero edges.
- <hr>
- <pre>
- adjacency_list(const adjacency_list& x)
- </pre>
- Copy constructor. Creates a new graph that is a copy of graph
- <tt>x</tt>, including the edges, vertices, and properties.
- <hr>
- <pre>
- adjacency_list& operator=(const adjacency_list& x)
- </pre>
- Assignment operator. Makes this graph a copy of graph
- <tt>x</tt>, including the edges, vertices, and properties.
- <hr>
- <pre>
- adjacency_list(vertices_size_type n,
- const GraphProperty& p = GraphProperty())
- </pre>
- Creates a graph object with <TT>n</TT> vertices and zero edges.
- <hr>
- <a name="sec:iterator-constructor">
- <pre>
- template <class EdgeIterator>
- adjacency_list(EdgeIterator first, EdgeIterator last,
- vertices_size_type n,
- edges_size_type m = 0,
- const GraphProperty& p = GraphProperty())
- </pre>
- Creates a graph object with <TT>n</TT> vertices and with the edges
- specified in the edge list given by the range <TT>[first, last)</TT>.
- The <tt>EdgeIterator</tt> must be a model of <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>.
- The value type of the <TT>EdgeIterator</TT> must be a
- <TT>std::pair</TT>, where the type in the pair is an integer type. The
- integers will correspond to vertices, and they must all fall in the
- range of <TT>[0, n)</TT>.
- </a>
- <hr>
- <pre>
- template <class EdgeIterator, class EdgePropertyIterator>
- adjacency_list(EdgeIterator first, EdgeIterator last,
- EdgePropertyIterator ep_iter,
- vertices_size_type n,
- edges_size_type m = 0,
- const GraphProperty& p = GraphProperty())
- </pre>
- Creates a graph object with <TT>n</TT> vertices and with the edges
- specified in the edge list given by the range <TT>[first, last)</TT>.
- The <tt>EdgeIterator</tt> and <tt>EdgePropertyIterator</tt> must be a
- model of <a
- href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a>.
- The value type of the <TT>EdgeIterator</TT> must be a
- <TT>std::pair</TT>, where the type in the pair is an integer type. The
- integers will correspond to vertices, and they must all fall in the
- range of <TT>[0, n)</TT>. The <TT>value_type</TT> of the
- <TT>ep_iter</TT> should be <TT>EdgeProperties</TT>.
- <hr>
- <pre>
- void clear()
- </pre>
- Remove all of the edges and vertices from the graph.
- <hr>
- <pre>
- void swap(adjacency_list& x)
- </pre>
- Swap the vertices, edges, and properties of this graph with the
- vertices, edges, and properties of graph <tt>x</tt>.
- <hr>
- <P>
- <H2>Non-Member Functions</H2>
- <h4>Structure Access</h4>
- <hr>
- <pre>
- std::pair<vertex_iterator, vertex_iterator>
- vertices(const adjacency_list& g)
- </pre>
- Returns an iterator-range providing access to the vertex set of graph
- <tt>g</tt>.
- <hr>
- <pre>
- std::pair<edge_iterator, edge_iterator>
- edges(const adjacency_list& g)
- </pre>
- Returns an iterator-range providing access to the edge set of graph
- <tt>g</tt>.
- <hr>
- <pre>
- std::pair<adjacency_iterator, adjacency_iterator>
- adjacent_vertices(vertex_descriptor u, const adjacency_list& g)
- </pre>
- Returns an iterator-range providing access to the vertices adjacent to
- vertex <tt>u</tt> in graph <tt>g</tt>. For example, if <tt>u -> v</tt>
- is an edge in the graph, then <tt>v</tt> will be in this iterator-range.
- <hr>
- <pre>
- std::pair<inv_adjacency_iterator, inv_adjacency_iterator>
- inv_adjacent_vertices(vertex_descriptor u, const adjacency_list& g)
- </pre>
- Returns an iterator-range providing access to the vertices in graph
- <tt>g</tt> to which <tt>u</tt> is adjacent. (<tt>inv</tt> is for
- inverse.) For example, if <tt>v -> u</tt> is an edge in the graph,
- then <tt>v</tt> will be in this iterator range. This function is only
- available for bidirectional and undirected <tt>adjacency_list</tt>'s.
- <hr>
- <pre>
- std::pair<out_edge_iterator, out_edge_iterator>
- out_edges(vertex_descriptor u, const adjacency_list& g)
- </pre>
- Returns an iterator-range providing access to the out-edges of vertex
- <tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this
- iterator-range provides access to all edges incident on vertex
- <tt>u</tt>. For both directed and undirected graphs, for an out-edge
- <tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt>
- where <tt>v</tt> is a vertex adjacent to <tt>u</tt>.
- <hr>
- <pre>
- std::pair<in_edge_iterator, in_edge_iterator>
- in_edges(vertex_descriptor v, const adjacency_list& g)
- </pre>
- Returns an iterator-range providing access to the in-edges of vertex
- <tt>v</tt> in graph <tt>g</tt>. This operation is only available if
- <TT>bidirectionalS</TT> was specified for the <TT>Directed</TT>
- template parameter. For an in-edge <tt>e</tt>, <tt>target(e, g) == v</tt>
- and <tt>source(e, g) == u</tt> for some vertex <tt>u</tt> that is
- adjacent to <tt>v</tt>, whether the graph is directed or undirected.
- <hr>
- <pre>
- vertex_descriptor
- source(edge_descriptor e, const adjacency_list& g)
- </pre>
- Returns the source vertex of edge <tt>e</tt>.
- <hr>
- <pre>
- vertex_descriptor
- target(edge_descriptor e, const adjacency_list& g)
- </pre>
- Returns the target vertex of edge <tt>e</tt>.
- <hr>
- <pre>
- degree_size_type
- out_degree(vertex_descriptor u, const adjacency_list& g)
- </pre>
- Returns the number of edges leaving vertex <tt>u</tt>.
- <hr>
- <pre>
- degree_size_type
- in_degree(vertex_descriptor u, const adjacency_list& g)
- </pre>
- Returns the number of edges entering vertex <tt>u</tt>. This operation
- is only available if <TT>bidirectionalS</TT> was specified for
- the <TT>Directed</TT> template parameter.
- <hr>
- <pre>
- vertices_size_type
- num_vertices(const adjacency_list& g)
- </pre>
- Returns the number of vertices in the graph <tt>g</tt>.
- <hr>
- <pre>
- edges_size_type
- num_edges(const adjacency_list& g)
- </pre>
- Returns the number of edges in the graph <tt>g</tt>.
- <hr>
- <pre>
- vertex_descriptor
- vertex(vertices_size_type n, const adjacency_list& g)
- </pre>
- Returns the nth vertex in the graph's vertex list.
- <hr>
- <pre>
- std::pair<edge_descriptor, bool>
- edge(vertex_descriptor u, vertex_descriptor v,
- const adjacency_list& g)
- </pre>
- If an edge from vertex <tt>u</tt> to vertex <tt>v</tt> exists, return a pair
- containing one such edge and <tt>true</tt>. If there are no edges between
- <tt>u</tt> and <tt>v</tt>, return a pair with an arbitrary edge descriptor and
- <tt>false</tt>.
- <hr>
- <pre>
- std::pair<out_edge_iterator, out_edge_iterator>
- edge_range(vertex_descriptor u, vertex_descriptor v,
- const adjacency_list& g)
- </pre>
- Returns a pair of out-edge iterators that give the range for
- all the parallel edges from <tt>u</tt> to <tt>v</tt>. This
- function only works when the <tt>OutEdgeList</tt> for the
- <tt>adjacency_list</tt> is a container that sorts the
- out edges according to target vertex, and allows for
- parallel edges. The <tt>multisetS</tt> selector chooses
- such a container.
- <hr>
- <h4>Structure Modification</h4>
- <hr>
- <pre>
- std::pair<edge_descriptor, bool>
- add_edge(vertex_descriptor u, vertex_descriptor v,
- adjacency_list& g)
- </pre>
- Adds edge <i>(u,v)</i> to the graph and returns the edge descriptor
- for the new edge. For graphs that do not allow parallel edges, if the
- edge is already in the graph then a duplicate will not be added and
- the <TT>bool</TT> flag will be <TT>false</TT>. When the flag is
- <TT>false</TT>, the
- returned edge descriptor points to the already existing edge.
- <p>
- The placement of the new edge in the out-edge list is in general
- unspecified, though ordering of the out-edge list can be accomplished
- through the choice of <tt>OutEdgeList</tt>.
- If the <tt>VertexList</tt> selector is
- <tt>vecS</tt>, and if either vertex descriptor <tt>u</tt> or
- <tt>v</tt> (which are integers) has a value greater than the current
- number of vertices in the graph, the graph is enlarged so that the
- number of vertices is <tt>std::max(u,v) + 1</tt>.
- <p>
- If the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation
- will invalidate any <tt>out_edge_iterator</tt> for vertex
- <i>u</i>. This also applies if the <TT>OutEdgeList</TT> is a user-defined
- container that invalidates its iterators when <TT>push(container,
- x)</TT> is invoked (see Section <A
- HREF="./using_adjacency_list.html#sec:custom-storage">Customizing the
- Adjacency List Storage</A>). If the graph is also bidirectional then
- any <tt>in_edge_iterator</tt> for <i>v</i> is also invalidated. If
- instead the graph is undirected then any <tt>out_edge_iterator</tt>
- for <i>v</i> is also invalidated. If instead the graph is directed,
- then <tt>add_edge()</tt> also invalidates any <tt>edge_iterator</tt>.
- <hr>
- <pre>
- std::pair<edge_descriptor, bool>
- add_edge(vertex_descriptor u, vertex_descriptor v,
- const EdgeProperties& p,
- adjacency_list& g)
- </pre>
- Adds edge <i>(u,v)</i> to the graph and attaches <TT>p</TT> as the
- value of the edge's internal property storage. Also see the previous
- <TT>add_edge()</TT> non-member function for more details.
- <hr>
- <pre>
- void remove_edge(vertex_descriptor u, vertex_descriptor v,
- adjacency_list& g)
- </pre>
- Removes the edge <i>(u,v)</i> from the graph.
- <p>
- This operation causes any outstanding edge descriptors or iterators
- that point to edge <i>(u,v)</i> to become invalid. In addition, if
- the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation
- will invalidate any iterators that point into the edge-list for vertex
- <i>u</i> and also for vertex <i>v</i> in the undirected and
- bidirectional case. Also, for directed graphs this invalidates any
- <tt>edge_iterator</tt>.
- <hr>
- <pre>
- void remove_edge(edge_descriptor e, adjacency_list& g)
- </pre>
- Removes the edge <tt>e</tt> from the graph. This differs from the
- <tt>remove_edge(u, v, g)</tt> function in the case of a
- multigraph. This <tt>remove_edge(e, g)</tt> function removes a single
- edge, whereas the <tt>remove_edge(u, v, g)</tt> function removes all
- edges <i>(u,v)</i>.
- <p>
- This operation invalidates any outstanding edge descriptors and
- iterators for the same edge pointed to by descriptor <tt>e</tt>. In
- addition, this operation will invalidate any iterators that point into
- the edge-list for the <tt>target(e, g)</tt>. Also, for directed
- graphs this invalidates any <tt>edge_iterator</tt> for the graph.
- <hr>
- <pre>
- void remove_edge(out_edge_iterator iter, adjacency_list& g)
- </pre>
- This has the same effect as <tt>remove_edge(*iter, g)</tt>. The
- difference is that this function has constant time complexity
- in the case of directed graphs, whereas <tt>remove_edge(e, g)</tt>
- has time complexity <i>O(E/V)</i>.
- <hr>
- <pre>
- template <class <a href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>>
- void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
- adjacency_list& g)
- </pre>
- Removes all out-edges of vertex <i>u</i> from the graph that satisfy
- the <tt>predicate</tt>. That is, if the predicate returns true when
- applied to an edge descriptor, then the edge is removed.
- <p>
- The affect on descriptor and iterator stability is the same as that of
- invoking <tt>remove_edge()</tt> on each of the removed edges.
- <hr>
- <pre>
- template <class <a
- href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>>
- void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
- adjacency_list& g)
- </pre>
- Removes all in-edges of vertex <i>v</i> from the graph that satisfy
- the <tt>predicate</tt>. That is, if the predicate returns true when
- applied to an edge descriptor, then the edge is removed.
- <p>
- The affect on descriptor and iterator stability is the
- same as that of invoking <tt>remove_edge()</tt> on each of the
- removed edges.
- <p>
- This operation is available for undirected and bidirectional
- <tt>adjacency_list</tt> graphs, but not for directed.
- <hr>
- <pre>
- template <class <a href="http://www.boost.org/sgi/stl/Predicate.html">Predicate</a>>
- void remove_edge_if(Predicate predicate, adjacency_list& g)
- </pre>
- Removes all edges from the graph that satisfy
- the <tt>predicate</tt>. That is, if the predicate returns true when
- applied to an edge descriptor, then the edge is removed.
- <p>
- The affect on descriptor and iterator stability is the same as that of
- invoking <tt>remove_edge()</tt> on each of the removed edges.
- <hr>
- <a name="sec:add-vertex">
- <pre>
- vertex_descriptor
- add_vertex(adjacency_list& g)
- </pre>
- Adds a vertex to the graph and returns the vertex descriptor for the
- new vertex.
- </a>
- <hr>
- <pre>
- vertex_descriptor
- add_vertex(const VertexProperties& p,
- adjacency_list& g)
- </pre>
- Adds a vertex to the graph with the specified properties. Returns the
- vertex descriptor for the new vertex.
- </a>
- <hr>
- <pre>
- void clear_vertex(vertex_descriptor u, adjacency_list& g)
- </pre>
- Removes all edges to and from vertex <i>u</i>. The vertex still appears
- in the vertex set of the graph.
- <p>
- The affect on descriptor and iterator stability is the
- same as that of invoking <tt>remove_edge()</tt> for all of
- the edges that have <tt>u</tt> as the source or target.
- <hr>
- <pre>
- void clear_out_edges(vertex_descriptor u, adjacency_list& g)
- </pre>
- Removes all out-edges from vertex <i>u</i>. The vertex still appears
- in the vertex set of the graph.
- <p>
- The affect on descriptor and iterator stability is the
- same as that of invoking <tt>remove_edge()</tt> for all of
- the edges that have <tt>u</tt> as the source.
- <p>
- This operation is not applicable to undirected graphs
- (use <tt>clear_vertex()</tt> instead).
- <hr>
- <pre>
- void clear_in_edges(vertex_descriptor u, adjacency_list& g)
- </pre>
- Removes all in-edges from vertex <i>u</i>. The vertex still appears
- in the vertex set of the graph.
- <p>
- The affect on descriptor and iterator stability is the
- same as that of invoking <tt>remove_edge()</tt> for all of
- the edges that have <tt>u</tt> as the target.
- <p>
- This operation is only applicable to bidirectional graphs.
- <hr>
- <pre>
- void remove_vertex(vertex_descriptor u, adjacency_list& g)
- </pre>
- Remove vertex <i>u</i> from the vertex set of the graph. It is assumed
- that there are no edges to or from vertex <i>u</i> when it is removed.
- One way to make sure of this is to invoke <TT>clear_vertex()</TT>
- beforehand.
- <p>
- If the <TT>VertexList</TT> template parameter of the
- <TT>adjacency_list</TT> was <TT>vecS</TT>, then all vertex
- descriptors, edge descriptors, and iterators for the graph are
- invalidated by this operation. The builtin
- <tt>vertex_index_t</tt> property for each vertex is renumbered so that
- after the operation the vertex indices still form a contiguous range
- <TT>[0, num_vertices(g))</TT>. If you are using external property
- storage based on the builtin vertex index, then the external storage
- will need to be adjusted. Another option is to not use the builtin
- vertex index, and instead use a property to add your own vertex index
- property. If you need to make frequent use of the
- <TT>remove_vertex()</TT> function the <TT>listS</TT> selector is a
- much better choice for the <TT>VertexList</TT> template parameter.
- <hr>
- <h4><a name="property-map-accessors">Property Map Accessors</a></h4>
- <hr>
- <pre>
- template <class <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<adjacency_list, PropertyTag>::type
- get(PropertyTag, adjacency_list& g)
- template <class <a href="./PropertyTag.html">PropertyTag</a>>
- property_map<adjacency_list, Tag>::const_type
- get(PropertyTag, const adjacency_list& g)
- </pre>
- Returns the property map object for the vertex property specified by
- <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the
- properties specified in the graph's <TT>VertexProperty</TT> template
- argument.
- <hr>
- <pre>
- template <class <a href="./PropertyTag.html">PropertyTag</a>, class X>
- typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
- get(PropertyTag, const adjacency_list& g, X x)
- </pre>
- This returns the property value for <tt>x</tt>, where <tt>x</tt> is either
- a vertex or edge descriptor.
- <hr>
- <pre>
- template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value>
- void
- put(PropertyTag, const adjacency_list& g, X x, const Value& value)
- </pre>
- This sets the property value for <tt>x</tt> to
- <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor.
- <tt>Value</tt> must be convertible to
- <tt>typename property_traits<property_map<adjacency_list, PropertyTag>::type>::value_type</tt>
- <hr>
- <pre>
- template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- typename graph_property<adjacency_list, GraphPropertyTag>::type&
- get_property(adjacency_list& g, GraphPropertyTag);
- </pre>
- Return the property specified by <tt>GraphPropertyTag</tt> that is
- attached to the graph object <tt>g</tt>. The <tt>graph_property</tt>
- traits class is defined in <a
- href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>.
- <hr>
- <pre>
- template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>>
- const typename graph_property<adjacency_list, GraphPropertyTag>::type&
- get_property(const adjacency_list& g, GraphPropertyTag);
- </pre>
- Return the property specified by <tt>GraphPropertyTag</tt> that is
- attached to the graph object <tt>g</tt>. The <tt>graph_property</tt>
- traits class is defined in <a
- href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>.
- <!-- add the shortcut property functions -->
- <hr>
- <h4><a name="serialization">Serialization</a></h4>
- <hr>
- <pre>
- template<class <a href="../../serialization/doc/archives.html#saving_interface">SavingArchive</a>>
- SavingArchive& operator<<(SavingArchive& ar, const adjacency_list& graph);
- </pre>
- Serializes the graph into the archive. Requires the vertex and edge properties of the
- graph to be <a href="../../serialization/doc/index.html">Serializable</a>.
- <br>
- Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>.
- <hr>
- <pre>
- template<class <a href="../../serialization/doc/archives.html#loading_interface">LoadingArchive</a>>
- LoadingArchive& operator>>(LoadingArchive& ar, const adjacency_list& graph);
- </pre>
- Reads the graph from the archive. Requires the vertex and edge properties of the
- graph to be <a href="../../serialization/doc/index.html">Serializable</a>.
- <br>
- Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>.
- <hr>
- <h3>See Also</h3>
- <a href="./adjacency_list_traits.html"><tt>adjacency_list_traits</tt></a>,
- <a href="./property_map.html"><tt>property_map</tt></a>,
- <a href="./graph_traits.html"><tt>graph_traits</tt></a>
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
- Indiana University (<A
- HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
- <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>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
- <!-- LocalWords: gif ALT OutEdgeList EdgeList VertexList html VertexProperties EdgeProperties
- -->
- <!-- LocalWords: GraphPropertyTag cpp enum ai cout endl VertexAndEdgeListGraph
- -->
- <!-- LocalWords: MutablePropertyGraph hpp const ReadablePropertyMap listS num
- -->
- <!-- LocalWords: ReadWritePropertyMap vecS dijkstra ucs pre Adj Iter Desc ep
- -->
- <!-- LocalWords: EdgeIterator EdgePropertyIterator iter bool edge's IDs siek
- -->
- <!-- LocalWords: multigraph typename htm Univ Quan Lumsdaine
- -->
|