1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 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>IncidenceGraph</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<H1><A NAME="concept:IncidenceGraph"></A> 19IncidenceGraph 20</H1> 21 22The IncidenceGraph concept provides an interface for 23efficient access to the out-edges of each vertex in the graph. 24 25 26<H3>Refinement of</H3> 27 28<a href="./Graph.html">Graph</a> 29 30<h3>Notation</h3> 31 32<Table> 33<TR> 34<TD><tt>G</tt></TD> 35<TD>A type that is a model of IncidenceGraph.</TD> 36</TR> 37 38<TR> 39<TD><tt>g</tt></TD> 40<TD>An object of type <tt>G</tt>.</TD> 41</TR> 42 43<TR> 44<TD><tt>e</tt></TD> 45<TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD> 46</TR> 47 48<TR> 49<TD><tt>u, v</tt></TD> 50<TD>Are objects of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD> 51</TR> 52 53</table> 54 55<H3>Associated Types</H3> 56 57<Table border> 58 59<tr> 60<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br> 61 This tag type must be convertible to <tt>incidence_graph_tag</tt>. 62</td> 63</tr> 64 65 66<TR> 67<TD> 68<pre>boost::graph_traits<G>::out_edge_iterator</pre> 69An out-edge iterator for a vertex <i>v</i> provides access to the 70out-edges of the vertex. As such, the value type of an out-edge 71iterator is the edge descriptor type of its graph. An out-edge 72iterator must meet the requirements of <a 73href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. 74</TD> 75</TR> 76 77<TR> 78<TD><pre>boost::graph_traits<G>::degree_size_type</pre> 79The unsigned integral type used for representing the number 80out-edges or incident edges of a vertex. 81</TD> 82</TR> 83 84</table> 85 86<h3>Valid Expressions</h3> 87 88<Table border> 89 90<tr> 91<td><a name="sec:source"><TT>source(e, g)</TT></a></TD> 92<TD>Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i> represented by <TT>e</TT>.<br> 93Return type: <TT>vertex_descriptor</TT> 94</TD> 95</TR> 96 97 98<tr> 99<td><a name="sec:target"><TT>target(e, g)</TT></a></TD> 100<TD>Returns the vertex descriptor for <i>v</i> of the edge <i>(u,v)</i> represented by <TT>e</TT>.<br> 101Return type: <TT>vertex_descriptor</TT> 102</td></tr> 103 104<tr> 105<td><a name="sec:out-edges"><TT>out_edges(u, g)</TT></a></TD> 106<TD>Returns an iterator-range providing access to the out-edges (for 107directed graphs) or incident edges (for undirected graphs) of vertex 108<TT>u</TT> in graph <TT>g</TT>. The source vertex of an edge obtained 109via an out edge iterator is guaranteed (for both directed and 110undirected graphs) to be the vertex <tt>u</tt> used in the call to 111<tt>out_edges(u, g)</tt> and the target vertex must be a vertex 112adjacent to <tt>u</tt>.<a href="#1">[1]</a> 113<br> 114Return type: <TT>std::pair<out_edge_iterator, out_edge_iterator></TT> 115</TD> 116</tr> 117 118<tr> 119<TD><TT>out_degree(u, g)</TT></TD> 120<TD>Returns the number of out-edges (for directed graphs) or the 121number of incident edges (for undirected graphs) of vertex <TT>u</TT> 122in graph <TT>g</TT>.<br> 123Return type: <TT>degree_size_type</TT> 124</TD> 125</TR> 126 127</TABLE> 128 129<P> 130 131<H3>Complexity guarantees</H3> 132 133<P> 134The <TT>source()</TT>, <TT>target()</TT>, and <TT>out_edges()</TT> 135functions must all be constant time. The <tt>out_degree()</tt> 136function must be linear in the number of out-edges. 137 138<P> 139 140<H3>See Also</H3> 141 142<a href="./graph_concepts.html">Graph concepts</a> 143 144<H3>Notes</H3> 145 146<a name="1">[1]</a> For undirected graphs, the edge <tt>(u,v)</tt> is 147the same as edge <tt>(v,u)</tt>, so without some extra guarantee an 148implementation would be free use any ordering for the pair of vertices 149in an out-edge. For example, if you call <tt>out_edges(u, g)</tt>, and 150<tt>v</tt> is one of the vertices adjacent to <tt>u</tt>, then the 151implementation would be free to return <tt>(v,u)</tt> as an out-edge 152which would be non-intuitive and cause trouble for algorithms. 153Therefore, the extra requirement is added that the out-edge connecting 154<tt>u</tt> and <tt>v</tt> must be given as <tt>(u,v)</tt> and not 155<tt>(v,u)</tt>. 156 157<H3>Concept Checking Class</H3> 158 159<PRE> 160 template <class G> 161 struct IncidenceGraphConcept 162 { 163 typedef typename boost::graph_traits<G>::out_edge_iterator out_edge_iterator; 164 void constraints() { 165 BOOST_CONCEPT_ASSERT(( GraphConcept<G> )); 166 BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<out_edge_iterator> )); 167 168 p = out_edges(u, g); 169 e = *p.first; 170 u = source(e, g); 171 v = target(e, g); 172 } 173 void const_constraints(const G& g) { 174 p = out_edges(u, g); 175 e = *p.first; 176 u = source(e, g); 177 v = target(e, g); 178 } 179 std::pair<out_edge_iterator, out_edge_iterator> p; 180 typename boost::graph_traits<G>::vertex_descriptor u, v; 181 typename boost::graph_traits<G>::edge_descriptor e; 182 G g; 183 }; 184</PRE> 185 186 187<br> 188<HR> 189<TABLE> 190<TR valign=top> 191<TD nowrap>Copyright © 2000-2001</TD><TD> 192<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 193Indiana University (<A 194HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 195<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br> 196<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 197Indiana University (<A 198HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 199</TD></TR></TABLE> 200 201</BODY> 202</HTML> 203
