AdjacencyGraph
The AdjacencyGraph concept provides and interface for efficient access
of the adjacent vertices to a vertex in a graph. This is quite similar
to the IncidenceGraph concept (the
target of an out-edge is an adjacent vertex). Both concepts are
provided because in some contexts there is only concern for the
vertices, whereas in other contexts the edges are also important.
Refinement of
Graph
Notation
| G |
A type that is a model of Graph. |
| g |
An object of type G. |
| v |
An object of type boost::graph_traits<G>::vertex_descriptor. |
Associated Types
boost::graph_traits<G>::traversal_category
This tag type must be convertible to adjacency_graph_tag.
|
boost::graph_traits<G>::adjacency_iterator
An adjacency iterator for a vertex v provides access to the
vertices adjacent to v. As such, the value type of an
adjacency iterator is the vertex descriptor type of its graph. An
adjacency iterator must meet the requirements of MultiPassInputIterator.
|
Valid Expressions
| adjacent_vertices(v, g) |
Returns an iterator-range providing access to the vertices adjacent to
vertex v in graph g.[1]
Return type:
std::pair<adjacency_iterator, adjacency_iterator>
|
Complexity guarantees
The adjacent_vertices() function must return in constant time.
See Also
Graph concepts,
adjacency_iterator
Concept Checking Class
template <class G>
struct AdjacencyGraphConcept
{
typedef typename boost::graph_traits<G>::adjacency_iterator
adjacency_iterator;
void constraints() {
function_requires< IncidenceGraphConcept<G> >();
function_requires< MultiPassInputIteratorConcept<adjacency_iterator> >();
p = adjacent_vertices(v, g);
v = *p.first;
const_constraints(g);
}
void const_constraints(const G& g) {
p = adjacent_vertices(v, g);
}
std::pair<adjacency_iterator,adjacency_iterator> p;
typename boost::graph_traits<G>::vertex_descriptor v;
G g;
};
Design Rationale
The AdjacencyGraph concept is somewhat frivolous since IncidenceGraph really covers the same
functionality (and more). The AdjacencyGraph concept exists because
there are situations when adjacent_vertices() is more
convenient to use than out_edges(). If you are constructing a
graph class and do not want to put in the extra work of creating an
adjacency iterator, have no fear. There is an adaptor class named adjacency_iterator that
you can use to create an adjacency iterator out of an out-edge
iterator.
Notes
[1] The case of a
multigraph (where multiple edges can connect the same two
vertices) brings up an issue as to whether the iterators returned by
the adjacent_vertices() function access a range that
includes each adjacent vertex once, or whether it should match the
behavior of the out_edges() function, and access a
range that may include an adjacent vertex more than once. For now the
behavior is defined to match that of out_edges(),
though this decision may need to be reviewed in light of more
experience with graph algorithm implementations.