Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/graph_traits.html @ 14

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

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