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<G>::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<G>::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<G>::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, 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<adjacency_iterator, adjacency_iterator></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 <class G> 110 struct AdjacencyGraphConcept 111 { 112 typedef typename boost::graph_traits<G>::adjacency_iterator 113 adjacency_iterator; 114 void constraints() { 115 BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<adjacency_iterator> )); 116 117 p = adjacent_vertices(v, g); 118 v = *p.first; 119 const_constraints(g); 120 } 121 void const_constraints(const G& g) { 122 p = adjacent_vertices(v, g); 123 } 124 std::pair<adjacency_iterator,adjacency_iterator> p; 125 typename boost::graph_traits<G>::vertex_descriptor v; 126 G g; 127 }; 128</PRE> 129 130<h3>Design Rationale</h3> 131 132The AdjacencyGraph concept is somewhat frivolous since <a 133href="./IncidenceGraph.html">IncidenceGraph</a> really covers the same 134functionality (and more). The AdjacencyGraph concept exists because 135there are situations when <tt>adjacent_vertices()</tt> is more 136convenient to use than <tt>out_edges()</tt>. If you are constructing a 137graph class and do not want to put in the extra work of creating an 138adjacency iterator, have no fear. There is an adaptor class named <a 139href="./adjacency_iterator.html"> <tt>adjacency_iterator</tt></a> that 140you can use to create an adjacency iterator out of an out-edge 141iterator. 142 143<h3>Notes</h3> 144 145<a name="1">[1]</a> The case of a 146<I>multigraph</I> (where multiple edges can connect the same two 147vertices) brings up an issue as to whether the iterators returned by 148the <TT>adjacent_vertices()</TT> function access a range that 149includes each adjacent vertex once, or whether it should match the 150behavior of the <TT>out_edges()</TT> function, and access a 151range that may include an adjacent vertex more than once. For now the 152behavior is defined to match that of <TT>out_edges()</TT>, 153though this decision may need to be reviewed in light of more 154experience with graph algorithm implementations. 155 156 157 158<br> 159<HR> 160<TABLE> 161<TR valign=top> 162<TD nowrap>Copyright © 2000-2001</TD><TD> 163<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>) 164</TD></TR></TABLE> 165 166</BODY> 167</HTML> 168
