...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

adjacency_list<OutEdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties, EdgeList>

The `adjacency_list` 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 adjacency-list
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. Figure 1 shows an adjacency list
representation of a directed graph.

The `Directed` 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. Figure 2 shows an adjacency list
representation of an undirected graph.

A tutorial on how to use the `adjacency_list` class is in
Section Using
`adjacency_list`.

The example in `examples/family_tree.cpp`
shows how to represent a family tree with a graph.

Parameter | Description | Default |
---|---|---|

OutEdgeList |
The selector for the container used to represent the edge-list for each of the vertices. | vecS |

VertexList |
The selector for the container used to represent the vertex-list of the graph. | vecS |

Directed |
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 directedS, undirectedS, and bidirectionalS. |
directedS |

VertexProperties |
for specifying internal property storage. | no_property |

EdgeProperties |
for specifying internal property storage. | no_property |

GraphProperties |
for specifying property storage for the graph object. | no_property |

EdgeList |
The selector for the container used to represent the edge-list for the graph. | listS |

VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.

`boost/graph/adjacency_list.hpp`

Also, the serialization functionality is in
`boost/graph/adj_list_serialize.hpp`.

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 `get(property, g)` function. How to use
properties is described in Section Internal
Properties . The property maps are objects that implement the
interface defined in Section Property Map
Concepts or may be bundled properties,
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
`adjacency_list` class are models of the Lvalue Property
Map concept. If the `adjacency_list` is const,
then the property map is constant, otherwise the property
map is mutable.

If the `VertexList` of the graph is `vecS`, then the
graph has a builtin vertex indices accessed via the property map for
the `vertex_index_t` property. The indices fall in the range
`[0, num_vertices(g))` 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 Readable
Property Map.

typedef adjacency_list<listS, vecS> Graph;The reason this is a problem is that we are invoking// VertexList=vecSGraph G(N);// Fill in the graph...// Attempt to remove all the vertices. Wrong!graph_traits<Graph>::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) remove_vertex(*vi, G);// Remove all the vertices. This is still wrong!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); }

If we use a different kind of `adjacency_list`, where
`VertexList=listS`, then the iterators are not invalidated by
calling `remove_vertex` unless the iterator is pointing to the
actual vertex that was removed. The following code demonstrates this.

typedef adjacency_list<listS, listS> Graph;// VertexList=listSGraph G(N);// Fill in the graph...// Attempt to remove all the vertices. Wrong!graph_traits<Graph>::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) remove_vertex(*vi, G);// Remove all the vertices. This is OK.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); }

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 `examples/dijkstra-example.cpp`).
You create the parent vector with a call to
`dijkstra_shortest_paths()`, 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.

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);// Bad idea! Invalidates vertex descriptors in parent vector.// The following will produce incorrect resultsfor(boost::tie(vi, vend) = vertices(G); vi != vend; ++vi) std::cout << p[*vi] << " is the parent of " << *vi << std::endl;

Note that in this discussion iterator and descriptor invalidation is
concerned with the invalidation of iterators and descriptors that are
**not directly affected** by the operation. For example, performing
`remove_edge(u, v, g)` will always invalidate any edge
descriptor for *(u,v)* or edge iterator pointing to *(u,v)*,
regardless of the kind `adjacency_list`. In this discussion
of iterator and descriptor invalidation, we are only concerned with the
affect of `remove_edge(u, v, g)` on edge descriptors and
iterators that point to other edges (not *(u,v)*).

In general, if you want your vertex and edge descriptors to be stable
(never invalidated) then use `listS` or `setS` for the
`VertexList` and `OutEdgeList` template parameters of
`adjacency_list`. If you are not as concerned about descriptor
and iterator stability, and are more concerned about memory
consumption and graph traversal speed, use `vecS` for the
`VertexList` and/or `OutEdgeList` template parameters.

The following table summarizes which operations cause descriptors and
iterators to become invalid. In the table, `EL` is an
abbreviation for `OutEdgeList` and `VL` means
`VertexList`. The **Adj Iter** category includes the
`out_edge_iterator`, `in_edge_iterator`, and
`adjacency_iterator` types. A more detailed description of
descriptor and iterator invalidation is given in the documentation for
each operation.

Function | Vertex Desc | Edge Desc | Vertex Iter | Edge Iter | Adj Iter |
---|---|---|---|---|---|

add_edge() |
OK |
OK |
OK |
EL=vecS && Directed=directedS |
EL=vecS |

remove_edge()
remove_edge_if() remove_out_edge_if() remove_in_edge_if() clear_vertex() |
OK |
OK |
OK |
EL=vecS && Directed=directedS |
EL=vecS |

add_vertex() |
OK |
OK |
OK |
VL=vecS && Directed=directedS |
VL=vecS && Directed=directedS |

remove_vertex() |
VL=vecS |
VL=vecS |
VL=vecS |
VL=vecS |
VL=vecS |

and

The type for the vertex descriptors associated with the

and

The type for the edge descriptors associated with the

The type for the iterators returned by

The type for the iterators returned by

The type for the iterators returned by

The type for the iterators returned by

The type for the iterators returned by

and

Provides information about whether the graph is directed (

and

This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target). The two tags are

and

The type used for dealing with the number of vertices in the graph.

and

The type used for dealing with the number of edges in the graph.

The type used for dealing with the number of edges incident to a vertex in the graph.

and

The property map type for vertex or edge properties in the graph. The specific property is specified by the

The property value type for the graph property specified by the

The type

The type

The type

The type

adjacency_list(const GraphProperty& p = GraphProperty())Default constructor. Creates an empty graph object with zero vertices and zero edges.

adjacency_list(const adjacency_list& x)Copy constructor. Creates a new graph that is a copy of graph

adjacency_list& operator=(const adjacency_list& x)Assignment operator. Makes this graph a copy of graph

adjacency_list(vertices_size_type n, const GraphProperty& p = GraphProperty())Creates a graph object with

template <class EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n, edges_size_type m = 0, const GraphProperty& p = GraphProperty())Creates a graph object with

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())Creates a graph object with

void clear()Remove all of the edges and vertices from the graph.

void swap(adjacency_list& x)Swap the vertices, edges, and properties of this graph with the vertices, edges, and properties of graph

std::pair<vertex_iterator, vertex_iterator> vertices(const adjacency_list& g)Returns an iterator-range providing access to the vertex set of graph

std::pair<edge_iterator, edge_iterator> edges(const adjacency_list& g)Returns an iterator-range providing access to the edge set of graph

std::pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor u, const adjacency_list& g)Returns an iterator-range providing access to the vertices adjacent to vertex

std::pair<inv_adjacency_iterator, inv_adjacency_iterator> inv_adjacent_vertices(vertex_descriptor u, const adjacency_list& g)Returns an iterator-range providing access to the vertices in graph

std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor u, const adjacency_list& g)Returns an iterator-range providing access to the out-edges of vertex

std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const adjacency_list& g)Returns an iterator-range providing access to the in-edges of vertex

vertex_descriptor source(edge_descriptor e, const adjacency_list& g)Returns the source vertex of edge

vertex_descriptor target(edge_descriptor e, const adjacency_list& g)Returns the target vertex of edge

degree_size_type out_degree(vertex_descriptor u, const adjacency_list& g)Returns the number of edges leaving vertex

degree_size_type in_degree(vertex_descriptor u, const adjacency_list& g)Returns the number of edges entering vertex

vertices_size_type num_vertices(const adjacency_list& g)Returns the number of vertices in the graph

edges_size_type num_edges(const adjacency_list& g)Returns the number of edges in the graph

vertex_descriptor vertex(vertices_size_type n, const adjacency_list& g)Returns the nth vertex in the graph's vertex list.

std::pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor v, const adjacency_list& g)If an edge from vertex

std::pair<out_edge_iterator, out_edge_iterator> edge_range(vertex_descriptor u, vertex_descriptor v, const adjacency_list& g)Returns a pair of out-edge iterators that give the range for all the parallel edges from

std::pair<edge_descriptor, bool> add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g)Adds edge

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 `OutEdgeList`.
If the `VertexList` selector is
`vecS`, and if either vertex descriptor `u` or
`v` (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 `std::max(u,v) + 1`.

If the `OutEdgeList` selector is `vecS` then this operation
will invalidate any `out_edge_iterator` for vertex
*u*. This also applies if the `OutEdgeList` is a user-defined
container that invalidates its iterators when `push(container,
x)` is invoked (see Section Customizing the
Adjacency List Storage). If the graph is also bidirectional then
any `in_edge_iterator` for *v* is also invalidated. If
instead the graph is undirected then any `out_edge_iterator`
for *v* is also invalidated. If instead the graph is directed,
then `add_edge()` also invalidates any `edge_iterator`.

std::pair<edge_descriptor, bool> add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g)Adds edge

void remove_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g)Removes the edge

This operation causes any outstanding edge descriptors or iterators
that point to edge *(u,v)* to become invalid. In addition, if
the `OutEdgeList` selector is `vecS` then this operation
will invalidate any iterators that point into the edge-list for vertex
*u* and also for vertex *v* in the undirected and
bidirectional case. Also, for directed graphs this invalidates any
`edge_iterator`.

void remove_edge(edge_descriptor e, adjacency_list& g)Removes the edge

This operation invalidates any outstanding edge descriptors and
iterators for the same edge pointed to by descriptor `e`. In
addition, this operation will invalidate any iterators that point into
the edge-list for the `target(e, g)`. Also, for directed
graphs this invalidates any `edge_iterator` for the graph.

void remove_edge(out_edge_iterator iter, adjacency_list& g)This has the same effect as

template <class Predicate> void remove_out_edge_if(vertex_descriptor u, Predicate predicate, adjacency_list& g)Removes all out-edges of vertex

The affect on descriptor and iterator stability is the same as that of
invoking `remove_edge()` on each of the removed edges.

template <class Predicate> void remove_in_edge_if(vertex_descriptor v, Predicate predicate, adjacency_list& g)Removes all in-edges of vertex

The affect on descriptor and iterator stability is the
same as that of invoking `remove_edge()` on each of the
removed edges.

This operation is available for undirected and bidirectional
`adjacency_list` graphs, but not for directed.

template <class Predicate> void remove_edge_if(Predicate predicate, adjacency_list& g)Removes all edges from the graph that satisfy the

The affect on descriptor and iterator stability is the same as that of
invoking `remove_edge()` on each of the removed edges.

vertex_descriptor add_vertex(adjacency_list& g)Adds a vertex to the graph and returns the vertex descriptor for the new vertex.

vertex_descriptor add_vertex(const VertexProperties& p, adjacency_list& g)Adds a vertex to the graph with the specified properties. Returns the vertex descriptor for the new vertex.

void clear_vertex(vertex_descriptor u, adjacency_list& g)Removes all edges to and from vertex

The affect on descriptor and iterator stability is the
same as that of invoking `remove_edge()` for all of
the edges that have `u` as the source or target.

void clear_out_edges(vertex_descriptor u, adjacency_list& g)Removes all out-edges from vertex

The affect on descriptor and iterator stability is the
same as that of invoking `remove_edge()` for all of
the edges that have `u` as the source.

This operation is not applicable to undirected graphs
(use `clear_vertex()` instead).

void clear_in_edges(vertex_descriptor u, adjacency_list& g)Removes all in-edges from vertex

The affect on descriptor and iterator stability is the
same as that of invoking `remove_edge()` for all of
the edges that have `u` as the target.

This operation is only applicable to bidirectional graphs.

void remove_vertex(vertex_descriptor u, adjacency_list& g)Remove vertex

If the `VertexList` template parameter of the
`adjacency_list` was `vecS`, then all vertex
descriptors, edge descriptors, and iterators for the graph are
invalidated by this operation. The builtin
`vertex_index_t` property for each vertex is renumbered so that
after the operation the vertex indices still form a contiguous range
`[0, num_vertices(g))`. 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
`remove_vertex()` function the `listS` selector is a
much better choice for the `VertexList` template parameter.

template <class PropertyTag> property_map<adjacency_list, PropertyTag>::type get(PropertyTag, adjacency_list& g) template <class PropertyTag> property_map<adjacency_list, Tag>::const_type get(PropertyTag, const adjacency_list& g)Returns the property map object for the vertex property specified by

template <class PropertyTag, class X> typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type get(PropertyTag, const adjacency_list& g, X x)This returns the property value for

template <class PropertyTag, class X, class Value> void put(PropertyTag, const adjacency_list& g, X x, const Value& value)This sets the property value for

template <class GraphProperties, class GraphPropertyTag> typename graph_property<adjacency_list, GraphPropertyTag>::type& get_property(adjacency_list& g, GraphPropertyTag);Return the property specified by

template <class GraphProperties, class GraphPropertyTag> const typename graph_property<adjacency_list, GraphPropertyTag>::type& get_property(const adjacency_list& g, GraphPropertyTag);Return the property specified by

template<class SavingArchive> SavingArchive& operator<<(SavingArchive& ar, const adjacency_list& graph);Serializes the graph into the archive. Requires the vertex and edge properties of the graph to be Serializable.

Include

template<class LoadingArchive> LoadingArchive& operator>>(LoadingArchive& ar, const adjacency_list& graph);Reads the graph from the archive. Requires the vertex and edge properties of the graph to be Serializable.

Include

Copyright © 2000-2001 |
Jeremy Siek,
Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |