ceph/src/boost/libs/graph/doc/graph_traits.html

   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&lt;<a href="./Graph.html">Graph</a>&gt;
  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 &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>
  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 &copy; 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>