<HTML> <!-- -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. We make no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. --> <Head> <Title>Boost Graph Library: Graph Traits</Title> <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../c++boost.gif" 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.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. <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.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> edge_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="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> <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> <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>