Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

AdjacencyGraph

The AdjacencyGraph concept provides an 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.

Concept Checking Class

  template <class G>
  struct AdjacencyGraphConcept
  {
    typedef typename boost::graph_traits<G>::adjacency_iterator
      adjacency_iterator;
    void constraints() {
      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.

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)