1149 lines
38 KiB
HTML
1149 lines
38 KiB
HTML
<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
|
|
-->
|