Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/Graph.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 4.4 KB
RevLine 
[29]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.sgi.com/tech/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&lt;G&gt;::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.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</a>,
55<a href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>, and
56<a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
57</td>
58</tr>
59
60<tr>
61<td><pre>boost::graph_traits&lt;G&gt;::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.sgi.com/tech/stl/DefaultConstructible.html">Default Constructible</I>,
65<a
66href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>,
67and <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality Comparable</a>.
68</td>
69</tr>
70
71<tr>
72<td><pre>boost::graph_traits&lt;G&gt;::directed_category</pre>
73This type shall be convertible to <TT>directed_tag</TT> or <TT>undirected_tag</TT>.
74</td>
75</tr>
76
77<tr>
78<td><pre>boost::graph_traits&lt;G&gt;::edge_parallel_category</pre>
79This describes whether the graph class allows the insertion of
80parallel edges (edges with the same source and target). The two tags
81are <TT>allow_parallel_edge_tag</TT> and <TT>disallow_parallel_edge_tag</TT>.
82</td>
83</tr>
84
85<tr>
86<td><pre>boost::graph_traits&lt;G&gt;::traversal_category</pre>
87This describes the ways in which the vertices and edges of the
88graph can be visited. The choices are <TT>incidence_graph_tag</TT>,
89<TT>adjacency_graph_tag</TT>, <TT>bidirectional_graph_tag</TT>,
90<TT>vertex_list_graph_tag</TT>, <TT>edge_list_graph_tag</TT>, and
91<TT>adjacency_matrix_tag</TT>.
92</td>
93</tr>
94
95</table>
96
97<H3>Valid Expressions</H3>
98
99<table border>
100
101<tr>
102<td><pre>boost::graph_traits&lt;G&gt;::null_vertex()</pre></td></TD>
103<td>
104Returns a special <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt> object which does not refer to
105any vertex of graph object which type is <tt>G</tt>.
106<td>
107</tr>
108</table>
109
110
111
112<H3>Concept Checking Class</H3>
113
114<PRE>
115  template &lt;class G&gt;
116  struct GraphConcept
117  {
118    typedef typename boost::graph_traits&lt;G&gt;::vertex_descriptor vertex_descriptor;
119    typedef typename boost::graph_traits&lt;G&gt;::edge_descriptor edge_descriptor;
120    typedef typename boost::graph_traits&lt;G&gt;::directed_category directed_category;
121    typedef typename boost::graph_traits&lt;G&gt;::edge_parallel_category edge_parallel_category;
122    typedef typename boost::graph_traits&lt;G&gt;::traversal_category traversal_category;
123
124    void constraints() {
125      function_requires&lt; DefaultConstructibleConcept&lt;vertex_descriptor&gt; &gt;();
126      function_requires&lt; EqualityComparableConcept&lt;vertex_descriptor&gt; &gt;();
127      function_requires&lt; AssignableConcept&lt;vertex_descriptor&gt; &gt;();
128      function_requires&lt; DefaultConstructibleConcept&lt;edge_descriptor&gt; &gt;();
129      function_requires&lt; EqualityComparableConcept&lt;edge_descriptor&gt; &gt;();
130      function_requires&lt; AssignableConcept&lt;edge_descriptor&gt; &gt;();
131    }
132    G g;
133  };
134</PRE>
135
136<H3>See Also</H3>
137
138<a href="./graph_concepts.html">Graph concepts</a>
139
140<br>
141<HR>
142<TABLE>
143<TR valign=top>
144<TD nowrap>Copyright &copy 2000-2001</TD><TD>
145<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
146</TD></TR></TABLE>
147
148</BODY>
149</HTML> 
Note: See TracBrowser for help on using the repository browser.