[ceph.git] / ceph / src / boost / libs / graph / doc / graph_traits.html

<HTML>
<!--
     Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>Boost Graph Library: Graph Traits</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>

<H1><A NAME=""></A>
<pre>
graph_traits&lt;<a href="./Graph.html">Graph</a>&gt;
</pre>
</H1>

Just like the <a
href="http://www.sgi.com/tech/stl/iterator_traits.html">
iterators</a> of STL, graphs have <b>associated types</b>.  As stated
in the various <a href="./graph_concepts.html">graph concepts</a>, a
graph has quite a few associated types: <tt>vertex_descriptor</tt>,
<tt>edge_descriptor</tt>, <tt>out_edge_iterator</tt>, etc..  Any
particular graph concepts will not require that all of the following
associated types be defined. When implementing a graph class that
fullfils one or more graph concepts, for associated types that are not
required by the concepts, it is ok to use <tt>void</tt> as the type
(when using nested typedefs inside the graph class), or to leave the
typedef out of the <tt>graph_traits</tt> specialization for the graph
class.
Note that because of the use of traits classes rather than member
types, it is not safe (and often will not work) to define subclasses of BGL
graph types; those types may be missing important traits and properties that
were defined externally to the class definition.

<pre>
  template &lt;typename Graph&gt;
  struct graph_traits {
    typedef typename Graph::vertex_descriptor      vertex_descriptor;
    typedef typename Graph::edge_descriptor        edge_descriptor;
    typedef typename Graph::adjacency_iterator     adjacency_iterator;
    typedef typename Graph::out_edge_iterator      out_edge_iterator;
    typedef typename Graph::in_edge_iterator       in_edge_iterator;
    typedef typename Graph::vertex_iterator        vertex_iterator;
    typedef typename Graph::edge_iterator          edge_iterator;

    typedef typename Graph::directed_category      directed_category;
    typedef typename Graph::edge_parallel_category edge_parallel_category;
    typedef typename Graph::traversal_category     traversal_category;

    typedef typename Graph::vertices_size_type     vertices_size_type;
    typedef typename Graph::edges_size_type        edges_size_type;
    typedef typename Graph::degree_size_type       degree_size_type;
  };
</pre>

<h3>Where Defined</h3>

<a href="../../../boost/graph/graph_traits.hpp"><tt>boost/graph/graph_traits.hpp</tt></a>

<H3>Template Parameters</H3>

<P>
<TABLE border>
<TR>
<th>Parameter</th><th>Description</th>
</tr>

<TR><TD><TT>Graph</TT></TD>
<TD>
The graph type whose associated types are being accessed.
</TD>
</TR>

</table>

<h3>Model of</h3>

<a
href="http://www.sgi.com/tech/stl/DefaultConstructible.html">DefaultConstructible</a> and
<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>

<h3>Type Requirements</h3>

<ul>
  <li><tt>Graph</tt> is a model of one of the <a
  href="./graph_concepts.html">graph concepts</a>.
</ul>

<H2>Members</H2>

<p>

<table border>
<tr>
<th>Member</th><th>Description</th>
</tr>

<tr>
<td><tt>
vertex_descriptor
</tt></td>
<td>
The type for the objects used to identity vertices in the graph.
</td>
</tr>

<tr>
<td><tt>
edge_descriptor
</tt></td>
<td>
The type for the objects used to identity edges in the graph.
</td>
</tr>

<tr>
<td><tt>
adjacency_iterator
</tt></td>
<td>
The type for the iterators that traverse the vertices adjacent
to a vertex.
</td>
</tr>

<tr>
<td><tt>
out_edge_iterator
</tt></td>
<td>
The type for the iterators that traverse through the out-edges
of a vertex.
</td>
</tr>

<tr>
<td><tt>
in_edge_iterator
</tt></td>
<td>
The type for the iterators that traverse through the in-edges
of a vertex.
</td>
</tr>

<tr>
<td><tt>
vertex_iterator
</tt></td>
<td>
The type for the iterators that traverse through the complete vertex
set of the graph.
</td>
</tr>

<tr>
<td><tt>
edge_iterator
</tt></td>
<td>
The type for the iterators that traverse through the complete edge
set of the graph.
</td>
</tr>

<tr>
<td><tt>
directed_category
</tt></td>
<td>
This says whether the graph is undirected (<tt>undirected_tag</tt>)
or directed (<tt>directed_tag</tt>).
</td>
</tr>

<tr>
<td><tt>
edge_parallel_category
</tt></td>
<td>
This says whether the graph allows parallel edges to be inserted
(<tt>allow_parallel_edge_tag</tt>) or if it automatically removes
parallel edges (<tt>disallow_parallel_edge_tag</tt>).
</td>
</tr>

<tr>
<td><tt>
traversal_category
</tt></td>
<td>
The ways in which the vertices in the graph can be traversed.
The traversal category tags are: 
<tt>incidence_graph_tag, adjacency_graph_tag,
bidirectional_graph_tag, vertex_list_graph_tag,
edge_list_graph_tag, vertex_and_edge_list_graph_tag,
adjacency_matrix_tag</tt>. You can also create your own
tag which should inherit from one of the above. 
</td>
</tr>

<tr>
<td><tt>
vertices_size_type
</tt></td>
<td>
The unsigned integer type used for representing the number of
vertices in the graph.
</td>
</tr>

<tr>
<td><tt>
edges_size_type
</tt></td>
<td>
The unsigned integer type used for representing the number of
edge in the graph.
</td>
</tr>

<tr>
<td><tt>
degree_size_type
</tt></td>
<td>
The unsigned integer type used for representing the degree
of vertices in the graph.
</td>
</tr>

</table>

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 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>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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>
	20	graph_traits<<a href="./Graph.html">Graph</a>>
	21	</pre>
	22	</H1>
	23
	24	Just like the <a
	25	href="http://www.sgi.com/tech/stl/iterator_traits.html">
	26	iterators</a> of STL, graphs have <b>associated types</b>. As stated
	27	in the various <a href="./graph_concepts.html">graph concepts</a>, a
	28	graph has quite a few associated types: <tt>vertex_descriptor</tt>,
	29	<tt>edge_descriptor</tt>, <tt>out_edge_iterator</tt>, etc.. Any
	30	particular graph concepts will not require that all of the following
	31	associated types be defined. When implementing a graph class that
	32	fullfils one or more graph concepts, for associated types that are not
	33	required 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
	35	typedef out of the <tt>graph_traits</tt> specialization for the graph
	36	class.
	37	Note that because of the use of traits classes rather than member
	38	types, it is not safe (and often will not work) to define subclasses of BGL
	39	graph types; those types may be missing important traits and properties that
	40	were defined externally to the class definition.
	41
	42	<pre>
	43	template <typename Graph>
	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>
77	The graph type whose associated types are being accessed.
78	</TD>
79	</TR>
80
81	</table>
82
83	<h3>Model of</h3>
84
85	<a
86	href="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>
107	vertex_descriptor
108	</tt></td>
109	<td>
110	The type for the objects used to identity vertices in the graph.
111	</td>
112	</tr>
113
114	<tr>
115	<td><tt>
116	edge_descriptor
117	</tt></td>
118	<td>
119	The type for the objects used to identity edges in the graph.
120	</td>
121	</tr>
122
123	<tr>
124	<td><tt>
125	adjacency_iterator
126	</tt></td>
127	<td>
128	The type for the iterators that traverse the vertices adjacent
129	to a vertex.
130	</td>
131	</tr>
132
133	<tr>
134	<td><tt>
135	out_edge_iterator
136	</tt></td>
137	<td>
138	The type for the iterators that traverse through the out-edges
139	of a vertex.
140	</td>
141	</tr>
142
143	<tr>
144	<td><tt>
145	in_edge_iterator
146	</tt></td>
147	<td>
148	The type for the iterators that traverse through the in-edges
149	of a vertex.
150	</td>
151	</tr>
152
153	<tr>
154	<td><tt>
155	vertex_iterator
156	</tt></td>
157	<td>
158	The type for the iterators that traverse through the complete vertex
159	set of the graph.
160	</td>
161	</tr>
162
163	<tr>
164	<td><tt>
165	edge_iterator
166	</tt></td>
167	<td>
168	The type for the iterators that traverse through the complete edge
169	set of the graph.
170	</td>
171	</tr>
172
173	<tr>
174	<td><tt>
175	directed_category
176	</tt></td>
177	<td>
178	This says whether the graph is undirected (<tt>undirected_tag</tt>)
179	or directed (<tt>directed_tag</tt>).
180	</td>
181	</tr>
182
183	<tr>
184	<td><tt>
185	edge_parallel_category
186	</tt></td>
187	<td>
188	This says whether the graph allows parallel edges to be inserted
189	(<tt>allow_parallel_edge_tag</tt>) or if it automatically removes
190	parallel edges (<tt>disallow_parallel_edge_tag</tt>).
191	</td>
192	</tr>
193
194	<tr>
195	<td><tt>
196	traversal_category
197	</tt></td>
198	<td>
199	The ways in which the vertices in the graph can be traversed.
200	The traversal category tags are:
201	<tt>incidence_graph_tag, adjacency_graph_tag,
202	bidirectional_graph_tag, vertex_list_graph_tag,
203	edge_list_graph_tag, vertex_and_edge_list_graph_tag,
204	adjacency_matrix_tag</tt>. You can also create your own
205	tag which should inherit from one of the above.
206	</td>
207	</tr>
208
209	<tr>
210	<td><tt>
211	vertices_size_type
212	</tt></td>
213	<td>
214	The unsigned integer type used for representing the number of
215	vertices in the graph.
216	</td>
217	</tr>
218
219	<tr>
220	<td><tt>
221	edges_size_type
222	</tt></td>
223	<td>
224	The unsigned integer type used for representing the number of
225	edge in the graph.
226	</td>
227	</tr>
228
229	<tr>
230	<td><tt>
231	degree_size_type
232	</tt></td>
233	<td>
234	The unsigned integer type used for representing the degree
235	of 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 © 2000-2001</TD><TD>
246	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
247	Indiana University (<A
248	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
249	<A HREF="http://www.boost.org/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>,
251	Indiana University (<A
252	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
253	</TD></TR></TABLE>
254
255	</BODY>
256	</HTML>