• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1<HTML>
2<!--
3     Copyright (c) Jeremy Siek 2000
4
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)
8  -->
9<Head>
10<Title>VertexListGraph</Title>
11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
12        ALINK="#ff0000">
13<IMG SRC="../../../boost.png"
14     ALT="C++ Boost" width="277" height="86">
15
16<BR Clear>
17
18
19<H2><A NAME="concept:VertexListGraph">
20VertexListGraph
21</H2>
22
23The <I>VertexListGraph</I> concept refines the <a
24href="./Graph.html">Graph</a> concept, and adds the requirement for
25efficient traversal of all the vertices in the graph.
26
27<H3>Refinement of</H3>
28
29<a href="./Graph.html">Graph</a>
30
31<H3>Associated Types</H3>
32
33<Table border>
34
35<tr>
36<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
37 This tag type must be convertible to <tt>vertex_list_graph_tag</tt>.
38</td>
39</tr>
40
41<TR>
42<TD><tt>boost::graph_traits&lt;G&gt;::vertex_iterator</tt><br><br>
43A vertex iterator (obtained via <TT>vertices(g)</TT>) provides access
44to all of the vertices in a graph.  A vertex iterator type must meet
45the requirements of <a
46href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. The
47value type of the vertex iterator must be the vertex descriptor of the
48graph.
49</TD>
50</TR>
51
52<tr>
53<td><tt>boost::graph_traits&lt;G&gt;::vertices_size_type</tt><br><br>
54The unsigned integer type used to represent the number of vertices
55in the graph.
56</td>
57</tr>
58
59</table>
60
61<h3>Valid Expressions</h3>
62
63<table border>
64
65<tr>
66<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
67</tr>
68
69<tr>
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&lt;vertex_iterator,&nbsp;vertex_iterator&gt;</TT></TD>
73<TD>
74Returns an iterator-range providing access to all the vertices in the
75graph<TT>g</TT>.
76</TD>
77</TR>
78
79<tr>
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>
84</TR>
85
86</TABLE>
87
88
89<H3>Complexity guarantees</H3>
90
91<P>
92The <TT>vertices()</TT> function must return in constant time.
93
94<H3>See Also</H3>
95
96<a href="./graph_concepts.html">Graph concepts</a>
97
98
99<H3>Design Rationale</H3>
100
101One issue in the design of this concept is whether to include the
102refinement from the <a href="./IncidenceGraph.html">IncidenceGraph</a>
103and <a href="./AdjacencyGraph.html">AdjacencyGraph</a> concepts.  The
104ability to traverse the vertices of a graph is orthogonal to
105traversing out-edges, so it would make sense to have a VertexListGraph
106concept that only includes vertex traversal. However, such a concept
107would no longer really be a graph, but would just be a set, and the
108STL already has concepts for dealing with such things. However, there
109are many BGL algorithms that need to traverse the vertices and
110out-edges of a graph, so for convenience a concept is needed that
111groups these requirements together, hence the VertexListGraph concept.
112
113
114<H3>Concept Checking Class</H3>
115
116<P>
117<PRE>
118  template &lt;class G&gt;
119  struct VertexListGraphConcept
120  {
121    typedef typename boost::graph_traits&lt;G&gt;::vertex_iterator
122      vertex_iterator;
123    void constraints() {
124      BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept&lt;G&gt; ));
125      BOOST_CONCEPT_ASSERT(( AdjacencyGraphConcept&lt;G&gt; ));
126      BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept&lt;vertex_iterator&gt; ));
127
128      p = vertices(g);
129      V = num_vertices(g);
130      v = *p.first;
131      const_constraints(g);
132    }
133    void const_constraints(const G&amp; g) {
134      p = vertices(g);
135      V = num_vertices(g);
136      v = *p.first;
137    }
138    std::pair&lt;vertex_iterator, vertex_iterator&gt; p;
139    typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
140    typename boost::graph_traits&lt;G&gt;::vertices_size_type V;
141    G g;
142  };
143</PRE>
144
145<br>
146<HR>
147<TABLE>
148<TR valign=top>
149<TD nowrap>Copyright &copy; 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>)
151</TD></TR></TABLE>
152
153</BODY>
154</HTML>
155