3 Copyright (c) Jeremy Siek 2000
5 Distributed under the Boost Software License, Version 1.0.
6 (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
10 <Title>VertexListGraph
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
19 <H2><A NAME=
"concept:VertexListGraph">
23 The
<I>VertexListGraph
</I> concept refines the
<a
24 href=
"./Graph.html">Graph
</a> concept, and adds the requirement for
25 efficient traversal of all the vertices in the graph.
27 <H3>Refinement of
</H3>
29 <a href=
"./Graph.html">Graph
</a>
31 <H3>Associated Types
</H3>
36 <td><tt>boost::graph_traits
<G
>::traversal_category
</tt><br><br>
37 This tag type must be convertible to
<tt>vertex_list_graph_tag
</tt>.
42 <TD><tt>boost::graph_traits
<G
>::vertex_iterator
</tt><br><br>
43 A vertex iterator (obtained via
<TT>vertices(g)
</TT>) provides access
44 to all of the vertices in a graph. A vertex iterator type must meet
45 the requirements of
<a
46 href=
"../../utility/MultiPassInputIterator.html">MultiPassInputIterator
</a>. The
47 value type of the vertex iterator must be the vertex descriptor of the
53 <td><tt>boost::graph_traits
<G
>::vertices_size_type
</tt><br><br>
54 The unsigned integer type used to represent the number of vertices
61 <h3>Valid Expressions
</h3>
66 <th>Name
</th><th>Expression
</th><th>Return Type
</th><th>Description
</th>
70 <td>Vertex Set of the Graph
</td>
71 <td><a name=
"sec:vertices"><TT>vertices(g)
</TT></a></TD>
72 <TD><TT>std::pair
<vertex_iterator,
vertex_iterator
></TT></TD>
74 Returns an iterator-range providing access to all the vertices in the
80 <td>Number of Vertices in the Graph
</td>
81 <td><TT>num_vertices(g)
</TT></TD>
82 <TD><TT>vertices_size_type
</TT></TD>
83 <TD>Returns the number of vertices in the graph
<TT>g
</TT>.
</TD>
89 <H3>Complexity guarantees
</H3>
92 The
<TT>vertices()
</TT> function must return in constant time.
96 <a href=
"./graph_concepts.html">Graph concepts
</a>
99 <H3>Design Rationale
</H3>
101 One issue in the design of this concept is whether to include the
102 refinement from the
<a href=
"./IncidenceGraph.html">IncidenceGraph
</a>
103 and
<a href=
"./AdjacencyGraph.html">AdjacencyGraph
</a> concepts. The
104 ability to traverse the vertices of a graph is orthogonal to
105 traversing out-edges, so it would make sense to have a VertexListGraph
106 concept that only includes vertex traversal. However, such a concept
107 would no longer really be a graph, but would just be a set, and the
108 STL already has concepts for dealing with such things. However, there
109 are many BGL algorithms that need to traverse the vertices and
110 out-edges of a graph, so for convenience a concept is needed that
111 groups these requirements together, hence the VertexListGraph concept.
114 <H3>Concept Checking Class
</H3>
118 template
<class G
>
119 struct VertexListGraphConcept
121 typedef typename boost::graph_traits
<G
>::vertex_iterator
124 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept
<G
> ));
125 BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept
<G
> ));
126 BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept
<vertex_iterator
> ));
131 const_constraints(g);
133 void const_constraints(const G
& g) {
138 std::pair
<vertex_iterator, vertex_iterator
> p;
139 typename boost::graph_traits
<G
>::vertex_descriptor v;
140 typename boost::graph_traits
<G
>::vertices_size_type V;
149 <TD nowrap
>Copyright
© 2000-
2001</TD><TD>
150 <A HREF=
"http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek
</A>, Indiana University (
<A HREF=
"mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu
</A>)