## 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() {
          BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
          BOOST_CONCEPT_ASSERT(( 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.

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)