...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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., and the num_vertices() and num_edges() functions. 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.
G | A type that is a model of Graph. |
g | An object of type G. |
boost::graph_traits<G>::vertex_descriptorA 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_descriptorAn 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_categoryThe choices are directed_tag and undirected_tag. |
boost::graph_traits<G>::edge_parallel_categoryThis 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_categoryThis 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. |
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. |
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; };
Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |