Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/graph_traits.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 5.7 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>Boost Graph Library: Graph Traits</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<H1><A NAME=""></A>
19<pre>
20graph_traits&lt;<a href="./Graph.html">Graph</a>&gt;
21</pre>
22</H1>
23
24Just like the <a
25href="http://www.sgi.com/tech/stl/iterator_traits.html">
26iterators</a> of STL, graphs have <b>associated types</b>.  As stated
27in the various <a href="./graph_concepts.html">graph concepts</a>, a
28graph has quite a few associated types: <tt>vertex_descriptor</tt>,
29<tt>edge_descriptor</tt>, <tt>out_edge_iterator</tt>, etc..  Any
30particular graph concepts will not require that all of the following
31associated types be defined. When implementing a graph class that
32fullfils one or more graph concepts, for associated types that are not
33required by the concepts, it is ok to use <tt>void</tt> as the type
34(when using nested typedefs inside the graph class), or to leave the
35typedef out of the <tt>graph_traits</tt> specialization for the graph
36class.
37
38<pre>
39  template &lt;typename Graph&gt;
40  struct graph_traits {
41    typedef typename Graph::vertex_descriptor      vertex_descriptor;
42    typedef typename Graph::edge_descriptor        edge_descriptor;
43    typedef typename Graph::adjacency_iterator     adjacency_iterator;
44    typedef typename Graph::out_edge_iterator      out_edge_iterator;
45    typedef typename Graph::in_edge_iterator       in_edge_iterator;
46    typedef typename Graph::vertex_iterator        vertex_iterator;
47    typedef typename Graph::edge_iterator          edge_iterator;
48
49    typedef typename Graph::directed_category      directed_category;
50    typedef typename Graph::edge_parallel_category edge_parallel_category;
51    typedef typename Graph::traversal_category     traversal_category;
52
53    typedef typename Graph::vertices_size_type     vertices_size_type;
54    typedef typename Graph::edges_size_type        edges_size_type;
55    typedef typename Graph::degree_size_type       degree_size_type;
56  };
57</pre>
58
59<h3>Where Defined</h3>
60
61<a href="../../../boost/graph/graph_traits.hpp"><tt>boost/graph/graph_traits.hpp</tt></a>
62
63<H3>Template Parameters</H3>
64
65<P>
66<TABLE border>
67<TR>
68<th>Parameter</th><th>Description</th>
69</tr>
70
71<TR><TD><TT>Graph</TT></TD>
72<TD>
73The graph type whose associated types are being accessed.
74</TD>
75</TR>
76
77</table>
78
79<h3>Model of</h3>
80
81<a
82href="http://www.sgi.com/tech/stl/DefaultConstructible.html">DefaultConstructible</a> and
83<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>
84
85<h3>Type Requirements</h3>
86
87<ul>
88  <li><tt>Graph</tt> is a model of one of the <a
89  href="./graph_concepts.html">graph concepts</a>.
90</ul>
91
92<H2>Members</H2>
93
94<p>
95
96<table border>
97<tr>
98<th>Member</th><th>Description</th>
99</tr>
100
101<tr>
102<td><tt>
103vertex_descriptor
104</tt></td>
105<td>
106The type for the objects used to identity vertices in the graph.
107</td>
108</tr>
109
110<tr>
111<td><tt>
112edge_descriptor
113</tt></td>
114<td>
115The type for the objects used to identity edges in the graph.
116</td>
117</tr>
118
119<tr>
120<td><tt>
121adjacency_iterator
122</tt></td>
123<td>
124The type for the iterators that traverse the vertices adjacent
125to a vertex.
126</td>
127</tr>
128
129<tr>
130<td><tt>
131out_edge_iterator
132</tt></td>
133<td>
134The type for the iterators that traverse through the out-edges
135of a vertex.
136</td>
137</tr>
138
139<tr>
140<td><tt>
141in_edge_iterator
142</tt></td>
143<td>
144The type for the iterators that traverse through the in-edges
145of a vertex.
146</td>
147</tr>
148
149<tr>
150<td><tt>
151vertex_iterator
152</tt></td>
153<td>
154The type for the iterators that traverse through the complete vertex
155set of the graph.
156</td>
157</tr>
158
159<tr>
160<td><tt>
161edge_iterator
162</tt></td>
163<td>
164The type for the iterators that traverse through the complete edge
165set of the graph.
166</td>
167</tr>
168
169<tr>
170<td><tt>
171directed_category
172</tt></td>
173<td>
174This says whether the graph is undirected (<tt>undirected_tag</tt>)
175or directed (<tt>directed_tag</tt>).
176</td>
177</tr>
178
179<tr>
180<td><tt>
181edge_parallel_category
182</tt></td>
183<td>
184This says whether the graph allows parallel edges to be inserted
185(<tt>allow_parallel_edge_tag</tt>) or if it automatically removes
186parallel edges (<tt>disallow_parallel_edge_tag</tt>).
187</td>
188</tr>
189
190<tr>
191<td><tt>
192traversal_category
193</tt></td>
194<td>
195The ways in which the vertices in the graph can be traversed.
196The traversal category tags are:
197<tt>incidence_graph_tag, adjacency_graph_tag,
198bidirectional_graph_tag, vertex_list_graph_tag,
199edge_list_graph_tag, vertex_and_edge_list_graph_tag,
200adjacency_matrix_tag</tt>. You can also create your own
201tag which should inherit from one of the above.
202</td>
203</tr>
204
205<tr>
206<td><tt>
207vertices_size_type
208</tt></td>
209<td>
210The unsigned integer type used for representing the number of
211vertices in the graph.
212</td>
213</tr>
214
215<tr>
216<td><tt>
217edge_size_type
218</tt></td>
219<td>
220The unsigned integer type used for representing the number of
221edge in the graph.
222</td>
223</tr>
224
225<tr>
226<td><tt>
227degree_size_type
228</tt></td>
229<td>
230The unsigned integer type used for representing the degree
231of vertices in the graph.
232</td>
233</tr>
234
235</table>
236
237<br>
238<HR>
239<TABLE>
240<TR valign=top>
241<TD nowrap>Copyright &copy 2000-2001</TD><TD>
242<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
243Indiana University (<A
244HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
245<A HREF="../../../people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
246<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
247Indiana University (<A
248HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
249</TD></TR></TABLE>
250
251</BODY>
252</HTML> 
Note: See TracBrowser for help on using the repository browser.