1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek 2000
--
-- Distributed under the Boost Software License, Version 1.0.
-- (See accompanying file LICENSE_1_0.txt or copy at
-- http://www.boost.org/LICENSE_1_0.txt)
-->
<Head>
<Title>VertexListGraph</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../boost.png"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H2><A NAME="concept:VertexListGraph">
VertexListGraph
</H2>
The <I>VertexListGraph</I> concept refines the <a
href="./Graph.html">Graph</a> concept, and adds the requirement for
efficient traversal of all the vertices in the graph.
<H3>Refinement of</H3>
<a href="./Graph.html">Graph</a>
<H3>Associated Types</H3>
<Table border>
<tr>
<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br>
This tag type must be convertible to <tt>vertex_list_graph_tag</tt>.
</td>
</tr>
<TR>
<TD><tt>boost::graph_traits<G>::vertex_iterator</tt><br><br>
A vertex iterator (obtained via <TT>vertices(g)</TT>) provides access
to all of the vertices in a graph. A vertex iterator type must meet
the requirements of <a
href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. The
value type of the vertex iterator must be the vertex descriptor of the
graph.
</TD>
</TR>
<tr>
<td><tt>boost::graph_traits<G>::vertices_size_type</tt><br><br>
The unsigned integer type used to represent the number of vertices
in the graph.
</td>
</tr>
</table>
<h3>Valid Expressions</h3>
<table border>
<tr>
<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
</tr>
<tr>
<td>Vertex Set of the Graph</td>
<td><a name="sec:vertices"><TT>vertices(g)</TT></a></TD>
<TD><TT>std::pair<vertex_iterator, vertex_iterator></TT></TD>
<TD>
Returns an iterator-range providing access to all the vertices in the
graph<TT>g</TT>.
</TD>
</TR>
<tr>
<td>Number of Vertices in the Graph </td>
<td><TT>num_vertices(g)</TT></TD>
<TD><TT>vertices_size_type</TT></TD>
<TD>Returns the number of vertices in the graph <TT>g</TT>.</TD>
</TR>
</TABLE>
<H3>Complexity guarantees</H3>
<P>
The <TT>vertices()</TT> function must return in constant time.
<H3>See Also</H3>
<a href="./graph_concepts.html">Graph concepts</a>
<H3>Design Rationale</H3>
One issue in the design of this concept is whether to include the
refinement from the <a href="./IncidenceGraph.html">IncidenceGraph</a>
and <a href="./AdjacencyGraph.html">AdjacencyGraph</a> 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.
<H3>Concept Checking Class</H3>
<P>
<PRE>
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;
};
</PRE>
<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000-2001</TD><TD>
<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>)
</TD></TR></TABLE>
</BODY>
</HTML>
|
