Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/AdjacencyGraph.html @ 12

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

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