Boost C++ Libraries

VertexListGraph

The VertexListGraph concept refines the Graph concept, and adds the requirement for efficient traversal of all the vertices in the graph.

Refinement of

Graph

Associated Types

boost::graph_traits<G>::traversal_category

This tag type must be convertible to vertex_list_graph_tag.

boost::graph_traits<G>::vertex_iterator

A vertex iterator (obtained via vertices(g)) provides access to all of the vertices in a graph. A vertex iterator type must meet the requirements of MultiPassInputIterator. The value type of the vertex iterator must be the vertex descriptor of the graph.

boost::graph_traits<G>::vertices_size_type

The unsigned integer type used to represent the number of vertices in the graph.

Valid Expressions

Name	Expression	Return Type	Description
Vertex Set of the Graph	`vertices(g)`	`std::pair<vertex_iterator, vertex_iterator>`	Returns an iterator-range providing access to all the vertices in the graph`g`.
Number of Vertices in the Graph	`num_vertices(g)`	`vertices_size_type`	Returns the number of vertices in the graph `g`.

Complexity guarantees

The vertices() function must return in constant time.

Design Rationale

One issue in the design of this concept is whether to include the refinement from the IncidenceGraph and AdjacencyGraph concepts. The ability to traverse the vertices of a graph is orthogonal to traversing out-edges, so it would make sense to have a VertexListGraph concept that only includes vertex traversal. However, such a concept would no longer really be a graph, but would just be a set, and the STL already has concepts for dealing with such things. However, there are many BGL algorithms that need to traverse the vertices and out-edges of a graph, so for convenience a concept is needed that groups these requirements together, hence the VertexListGraph concept.

Concept Checking Class

  template <class G>
  struct VertexListGraphConcept
  {
    typedef typename boost::graph_traits<G>::vertex_iterator 
      vertex_iterator;
    void constraints() {
      function_requires< IncidenceGraphConcept<G> >();
      function_requires< AdjacencyGraphConcept<G> >();
      function_requires< MultiPassInputIteratorConcept<vertex_iterator> >();

      p = vertices(g);
      V = num_vertices(g);
      v = *p.first;
      const_constraints(g);
    }
    void const_constraints(const G& g) {
      p = vertices(g);
      V = num_vertices(g);
      v = *p.first;
    }
    std::pair<vertex_iterator, vertex_iterator> p;
    typename boost::graph_traits<G>::vertex_descriptor v;
    typename boost::graph_traits<G>::vertices_size_type V;
    G g;
  };

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