## Graph

The Graph concept contains a few requirements that are common to all the graph concepts. These include some associated types for `vertex_descriptor`, `edge_descriptor`, etc. One should note that a model of Graph is not required to be a model of Assignable, so algorithms should pass graph objects by reference.

### Notation

`G` | A type that is a model of Graph.
`g` | An object of type `G`.

### Associated Types

    boost::graph_traits<G>::vertex_descriptor

A vertex descriptor corresponds to a unique vertex in an abstract graph instance. A vertex descriptor must be Default Constructible, Assignable, and Equality Comparable.

    boost::graph_traits<G>::edge_descriptor

An edge descriptor corresponds to a unique edge (u,v) in a graph. An edge descriptor must be Default Constructible, Assignable, and Equality Comparable.

    boost::graph_traits<G>::directed_category

The choices are `directed_tag` and `undirected_tag`.

    boost::graph_traits<G>::edge_parallel_category

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

    boost::graph_traits<G>::traversal_category

This describes the ways in which the vertices and edges of the graph can be visited. The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`, `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.

### Valid Expressions

    boost::graph_traits<G>::null_vertex()

Returns a special `vertex_descriptor` object which does not refer to any vertex of graph object which type is `G`.

### Concept Checking Class

      template <class G>
      struct GraphConcept
      {
        typedef typename boost::graph_traits<G>::vertex_descriptor vertex_descriptor;
        typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor;
        typedef typename boost::graph_traits<G>::directed_category directed_category;
        typedef typename boost::graph_traits<G>::edge_parallel_category edge_parallel_category;
        typedef typename boost::graph_traits<G>::traversal_category traversal_category;

        void constraints() {
          function_requires< DefaultConstructibleConcept<vertex_descriptor> >();
          function_requires< EqualityComparableConcept<vertex_descriptor> >();
          function_requires< AssignableConcept<vertex_descriptor> >();
          function_requires< DefaultConstructibleConcept<edge_descriptor> >();
          function_requires< EqualityComparableConcept<edge_descriptor> >();
          function_requires< AssignableConcept<edge_descriptor> >();
        }
        G g;
      };

### See Also

Graph concepts

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