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>Bidirectional</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<H2> 20<A NAME="concept:BidirectionalGraph"></A> 21BidirectionalGraph 22</H2> 23 24<P> 25The BidirectionalGraph concept refines <a 26href="./IncidenceGraph.html">IncidenceGraph</a> and adds the 27requirement for efficient access to the in-edges of each vertex. This 28concept is separated from <a 29href="./IncidenceGraph.html">IncidenceGraph</a> because for directed 30graphs efficient access to in-edges typically requires more storage 31space, and many algorithms do not require access to in-edges. For 32undirected graphs this is not an issue, since the <TT>in_edges()</TT> 33and <TT>out_edges()</TT> functions are the same, they both return the 34edges incident to the vertex. 35 36<H3>Refinement of</H3> 37 38<a href="./IncidenceGraph.html">IncidenceGraph</a> 39 40<h3>Notation</h3> 41 42<Table> 43<TR> 44<TD><tt>G</tt></TD> 45<TD>A type that is a model of Graph.</TD> 46</TR> 47 48<TR> 49<TD><tt>g</tt></TD> 50<TD>An object of type <tt>G</tt>.</TD> 51</TR> 52 53<TR> 54<TD><tt>v</tt></TD> 55<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD> 56</TR> 57 58</table> 59 60<H3>Associated Types</H3> 61 62<Table border> 63 64<tr> 65<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br> 66 This tag type must be convertible to <tt>bidirectional_graph_tag</tt>. 67</td> 68</tr> 69 70<TR> 71<TD><pre>boost::graph_traits<G>::in_edge_iterator</pre> 72An in-edge iterator for a vertex <i>v</i> provides access to the 73in-edges of <i>v</i>. As such, the value type of an in-edge iterator 74is the edge descriptor type of its graph. An in-edge iterator must 75meet the requirements of <a href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. 76</TD> 77</TR> 78 79</Table> 80 81<h3>Valid Expressions</h3> 82 83<Table border> 84 85<tr> 86<td><a name="sec:in-edges"><TT>in_edges(v, g)</TT></a></TD> 87<TD> 88Returns an iterator-range providing access to the 89in-edges (for directed graphs) or incident edges (for 90undirected graphs) of vertex <TT>v</TT> in graph <TT>g</TT>. 91For both directed and undirected graphs, the target of 92an out-edge is required to be vertex <tt>v</tt> and the 93source is required to be a vertex that is adjacent to <tt>v</tt>. 94<br> 95Return type: <TT>std::pair<in_edge_iterator, in_edge_iterator></TT> 96</TD> 97</TR> 98 99<tr> 100<TD><TT>in_degree(v, g)</TT></TD> 101<TD> 102Returns the number of in-edges (for directed graphs) or the 103number of incident edges (for undirected graphs) of vertex <TT>v</TT> 104in graph <TT>g</TT>.<br> 105Return type: <TT>degree_size_type</TT> 106</TD> 107</TR> 108 109<tr> 110<TD><TT>degree(v, g)</TT></TD> 111<TD>Returns the number of in-edges plus out-edges (for directed graphs) or the 112number of incident edges (for undirected graphs) of vertex <TT>v</TT> 113in graph <TT>g</TT>.<br> 114Return type: <TT>degree_size_type</TT> 115</TD> 116</TR> 117 118</Table> 119 120<H3>Models</H3> 121 122<ul> 123<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=bidirectionalS</tt></li> 124<li><a href="./adjacency_list.html"><tt>adjacency_list</tt></a> with <tt>Directed=undirectedS</tt></li> 125</ul> 126 127 128<H3>Complexity guarantees</H3> 129 130The <TT>in_edges()</TT> function is required to be constant time. The 131<tt>in_degree()</tt> and <tt>degree()</tt> functions must be linear in 132the number of in-edges (for directed graphs) or incident edges (for 133undirected graphs). 134 135<H3>See Also</H3> 136 137<a href="./graph_concepts.html">Graph concepts</a> 138 139<H3>Concept Checking Class</H3> 140 141<PRE> 142 template <class G> 143 struct BidirectionalGraphConcept 144 { 145 typedef typename boost::graph_traits<G>::in_edge_iterator 146 in_edge_iterator; 147 void constraints() { 148 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<G> )); 149 BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<in_edge_iterator> )); 150 151 p = in_edges(v, g); 152 n = in_degree(v, g); 153 n = degree(v, g); 154 e = *p.first; 155 const_constraints(g); 156 } 157 void const_constraints(const G& g) { 158 p = in_edges(v, g); 159 n = in_degree(v, g); 160 n = degree(v, g); 161 e = *p.first; 162 } 163 std::pair<in_edge_iterator, in_edge_iterator> p; 164 typename boost::graph_traits<G>::vertex_descriptor v; 165 typename boost::graph_traits<G>::edge_descriptor e; 166 typename boost::graph_traits<G>::degree_size_type n; 167 G g; 168 }; 169</PRE> 170 171<br> 172<HR> 173<TABLE> 174<TR valign=top> 175<TD nowrap>Copyright © 2000-2001</TD><TD> 176<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>) 177</TD></TR></TABLE> 178 179</BODY> 180</HTML> 181
