VertexListGraph
The VertexListGraph concept refines the Graph concept, and adds the requirement for efficient traversal of all the vertices in the graph.
Associated Types
|
|
|
Valid Expressions
| Name | Expression | Return Type | Description |
|---|---|---|---|
Vertex Set of the Graph |
|
|
Returns an iterator-range providing access to all the vertices in the graph`g`. |
Number of Vertices in the Graph |
|
|
Returns the number of vertices in the
graph |
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() {
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> ));
BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept<G> ));
BOOST_CONCEPT_ASSERT(( 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;
};