Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/AdjacencyGraph.html @ 45

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

updated boost from 1_33_1 to 1_34_1
File size: 4.6 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>AdjacencyGraph</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
19
20<H2><A NAME="concept:AdjacencyGraph"></A>
21AdjacencyGraph
22</H2>
23
24The AdjacencyGraph concept provides and interface for efficient access
25of the adjacent vertices to a vertex in a graph. This is quite similar
26to the <a href="./IncidenceGraph.html">IncidenceGraph</a> concept (the
27target of an out-edge is an adjacent vertex). Both concepts are
28provided because in some contexts there is only concern for the
29vertices, whereas in other contexts the edges are also important.
30
31<H3>Refinement of</H3>
32
33<a href="Graph.html">Graph</a>
34
35<h3>Notation</h3>
36
37<Table>
38<TR>
39<TD><tt>G</tt></TD>
40<TD>A type that is a model of Graph.</TD>
41</TR>
42
43<TR>
44<TD><tt>g</tt></TD>
45<TD>An object of type <tt>G</tt>.</TD>
46</TR>
47
48<TR>
49<TD><tt>v</tt></TD>
50<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
51</TR>
52
53</table>
54
55
56<H3>Associated Types</H3>
57
58<Table border>
59
60<tr>
61<td><tt>boost::graph_traits&lt;G&gt;::traversal_category</tt><br><br>
62 This tag type must be convertible to <tt>adjacency_graph_tag</tt>.
63</td>
64</tr>
65
66<TR>
67<TD><pre>boost::graph_traits&lt;G&gt;::adjacency_iterator</pre>
68An adjacency iterator for a vertex <i>v</i> provides access to the
69vertices adjacent to <i>v</i>.  As such, the value type of an
70adjacency iterator is the vertex descriptor type of its graph. An
71adjacency iterator must meet the requirements of <a
72href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>.
73</TD>
74</TR>
75
76</table>
77
78<h3>Valid Expressions</h3>
79
80
81<table border>
82
83<tr>
84<td><a name="sec:adjacent-vertices"><TT>adjacent_vertices(v,&nbsp;g)</TT></a></TD>
85<TD>
86Returns an iterator-range providing access to the vertices adjacent to
87vertex <TT>v</TT> in graph <TT>g</TT>.<a
88href="#1">[1]</a>
89
90<br> Return type:
91<TT>std::pair&lt;adjacency_iterator,&nbsp;adjacency_iterator&gt;</TT>
92</TD>
93</TR>
94
95</table>
96
97<H3>Complexity guarantees</H3>
98
99The <TT>adjacent_vertices()</TT> function must return in constant time.
100
101<H3>See Also</H3>
102
103<a href="./graph_concepts.html">Graph concepts</a>,
104<a href="./adjacency_iterator.html"><tt>adjacency_iterator</tt></a>
105
106<H3>Concept Checking Class</H3>
107
108<PRE>
109  template &lt;class G&gt;
110  struct AdjacencyGraphConcept
111  {
112    typedef typename boost::graph_traits&lt;G&gt;::adjacency_iterator
113      adjacency_iterator;
114    void constraints() {
115      function_requires&lt; IncidenceGraphConcept&lt;G&gt; &gt;();
116      function_requires&lt; MultiPassInputIteratorConcept&lt;adjacency_iterator&gt; &gt;();
117
118      p = adjacent_vertices(v, g);
119      v = *p.first;
120      const_constraints(g);
121    }
122    void const_constraints(const G&amp; g) {
123      p = adjacent_vertices(v, g);
124    }
125    std::pair&lt;adjacency_iterator,adjacency_iterator&gt; p;
126    typename boost::graph_traits&lt;G&gt;::vertex_descriptor v;
127    G g;
128  };
129</PRE>
130
131<h3>Design Rationale</h3>
132
133The AdjacencyGraph concept is somewhat frivolous since <a
134href="./IncidenceGraph.html">IncidenceGraph</a> really covers the same
135functionality (and more).  The AdjacencyGraph concept exists because
136there are situations when <tt>adjacent_vertices()</tt> is more
137convenient to use than <tt>out_edges()</tt>. If you are constructing a
138graph class and do not want to put in the extra work of creating an
139adjacency iterator, have no fear. There is an adaptor class named <a
140href="./adjacency_iterator.html"> <tt>adjacency_iterator</tt></a> that
141you can use to create an adjacency iterator out of an out-edge
142iterator.
143
144<h3>Notes</h3>
145
146<a name="1">[1]</a>  The case of a
147<I>multigraph</I> (where multiple edges can connect the same two
148vertices) brings up an issue as to whether the iterators returned by
149the <TT>adjacent_vertices()</TT> function access a range that
150includes each adjacent vertex once, or whether it should match the
151behavior of the <TT>out_edges()</TT> function, and access a
152range that may include an adjacent vertex more than once. For now the
153behavior is defined to match that of <TT>out_edges()</TT>,
154though this decision may need to be reviewed in light of more
155experience with graph algorithm implementations.
156
157
158
159<br>
160<HR>
161<TABLE>
162<TR valign=top>
163<TD nowrap>Copyright &copy 2000-2001</TD><TD>
164<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
165</TD></TR></TABLE>
166
167</BODY>
168</HTML> 
Note: See TracBrowser for help on using the repository browser.