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
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek 2000
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>VertexListGraph</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../c++boost.gif"
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="./AdjacencyGraph.html">AdjacencyGraph</a> concept, and adds the
requirement for efficient traversal of all the vertices in the graph.
<H3>Refinement of</H3>
<a href="./IncidenceGraph.html">IncidenceGraph</a>
and <a href="./AdjacencyGraph.html">AdjacencyGraph</a>
<H3>Associated Types</H3>
<Table border>
<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="../../../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>
|
