123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256 |
- <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<<a href="./Graph.html">Graph</a>>
- </pre>
- </H1>
- Just like the <a
- href="http://www.boost.org/sgi/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 <typename Graph>
- 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.boost.org/sgi/stl/DefaultConstructible.html">DefaultConstructible</a> and
- <a href="http://www.boost.org/sgi/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 © 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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|