1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 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>Graph</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<H2><A NAME="concept:Graph"></A> 19Graph 20</H2> 21 22<P> 23The Graph concept contains a few requirements that are common to all 24the graph concepts. These include some associated types for 25<tt>vertex_descriptor</tt>, <tt>edge_descriptor</tt>, etc. One should 26note that a model of Graph is <B>not</B> required to be a model of <a 27href="http://www.boost.org/sgi/stl/Assignable.html">Assignable</a>, 28so algorithms should pass graph objects by reference. 29 30<P> 31 32<h3>Notation</h3> 33 34<Table> 35<TR> 36<TD><tt>G</tt></TD> 37<TD>A type that is a model of Graph.</TD> 38</TR> 39 40<TR> 41<TD><tt>g</tt></TD> 42<TD>An object of type <tt>G</tt>.</TD> 43</TR> 44</table> 45 46<H3>Associated Types</H3> 47 48<table border> 49<tr> 50<td><pre>boost::graph_traits<G>::vertex_descriptor</pre> 51A vertex descriptor corresponds to a unique vertex in an abstract 52graph instance. A vertex descriptor must be 53<a 54href="http://www.boost.org/sgi/stl/DefaultConstructible.html">Default Constructible</a>, 55<a href="http://www.boost.org/sgi/stl/Assignable.html">Assignable</a>, and 56<a href="http://www.boost.org/sgi/stl/EqualityComparable.html">Equality Comparable</a>. 57</td> 58</tr> 59 60<tr> 61<td><pre>boost::graph_traits<G>::edge_descriptor</pre> 62An edge descriptor corresponds to a unique edge <i>(u,v)</i> in a 63graph. An edge descriptor must be <a 64href="http://www.boost.org/sgi/stl/DefaultConstructible.html">Default Constructible</I>, 65<a href="http://www.boost.org/sgi/stl/Assignable.html">Assignable</a>, and 66<a href="http://www.boost.org/sgi/stl/EqualityComparable.html">Equality Comparable</a>. 67</td> 68</tr> 69 70<tr> 71<td><pre>boost::graph_traits<G>::directed_category</pre> 72This type shall be convertible to <TT>directed_tag</TT> or <TT>undirected_tag</TT>. 73</td> 74</tr> 75 76<tr> 77<td><pre>boost::graph_traits<G>::edge_parallel_category</pre> 78This describes whether the graph class allows the insertion of 79parallel edges (edges with the same source and target). The two tags 80are <TT>allow_parallel_edge_tag</TT> and <TT>disallow_parallel_edge_tag</TT>. 81</td> 82</tr> 83 84<tr> 85<td><pre>boost::graph_traits<G>::traversal_category</pre> 86This describes the ways in which the vertices and edges of the 87graph can be visited. The choices are <TT>incidence_graph_tag</TT>, 88<TT>adjacency_graph_tag</TT>, <TT>bidirectional_graph_tag</TT>, 89<TT>vertex_list_graph_tag</TT>, <TT>edge_list_graph_tag</TT>, and 90<TT>adjacency_matrix_tag</TT>. 91</td> 92</tr> 93 94</table> 95 96<H3>Valid Expressions</H3> 97 98<table border> 99 100<tr> 101<td><pre>boost::graph_traits<G>::null_vertex()</pre></td></TD> 102<td> 103Returns a special <tt>boost::graph_traits<G>::vertex_descriptor</tt> object which does not refer to 104any vertex of graph object which type is <tt>G</tt>. 105<td> 106</tr> 107</table> 108 109 110 111<H3>Concept Checking Class</H3> 112 113<PRE> 114 template <class G> 115 struct GraphConcept 116 { 117 typedef typename boost::graph_traits<G>::vertex_descriptor vertex_descriptor; 118 typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; 119 typedef typename boost::graph_traits<G>::directed_category directed_category; 120 typedef typename boost::graph_traits<G>::edge_parallel_category edge_parallel_category; 121 typedef typename boost::graph_traits<G>::traversal_category traversal_category; 122 123 void constraints() { 124 BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept<vertex_descriptor> )); 125 BOOST_CONCEPT_ASSERT(( EqualityComparableConcept<vertex_descriptor> )); 126 BOOST_CONCEPT_ASSERT(( AssignableConcept<vertex_descriptor> )); 127 BOOST_CONCEPT_ASSERT(( DefaultConstructibleConcept<edge_descriptor> )); 128 BOOST_CONCEPT_ASSERT(( EqualityComparableConcept<edge_descriptor> )); 129 BOOST_CONCEPT_ASSERT(( AssignableConcept<edge_descriptor> )); 130 } 131 G g; 132 }; 133</PRE> 134 135<H3>See Also</H3> 136 137<a href="./graph_concepts.html">Graph concepts</a> 138 139<br> 140<HR> 141<TABLE> 142<TR valign=top> 143<TD nowrap>Copyright © 2000-2001</TD><TD> 144<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>) 145</TD></TR></TABLE> 146 147</BODY> 148</HTML> 149
