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>EdgeListGraph</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><A NAME="concept:EdgeListGraph"></A> 20EdgeListGraph 21</H2> 22 23The EdgeListGraph concept refines the <a href="./Graph.html">Graph</a> 24concept, and adds the requirement for efficient access to all the 25edges in the graph. 26 27 28<H3>Refinement of</H3> 29 30<a href="./Graph.html">Graph</a> 31 32 33<h3>Notation</h3> 34 35<Table> 36<TR> 37<TD><tt>G</tt></TD> 38<TD>A type that is a model of EdgeListGraph.</TD> 39</TR> 40 41<TR> 42<TD><tt>g</tt></TD> 43<TD>An object of type <tt>G</tt>.</TD> 44</TR> 45 46<TR> 47<TD><tt>e</tt></TD> 48<TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD> 49</TR> 50 51</table> 52 53<H3>Associated Types</H3> 54 55<table border> 56 57<tr> 58<td><tt>boost::graph_traits<G>::traversal_category</tt><br><br> 59 This tag type must be convertible to <tt>edge_list_graph_tag</tt>. 60</td> 61</tr> 62 63<tr> 64<td><pre>boost::graph_traits<G>::edge_iterator</pre> 65An edge iterator (obtained via <TT>edges(g)</TT>) provides access to 66all of the edges in a graph. An edge iterator type must meet the 67requirements of <a 68href="../../utility/MultiPassInputIterator.html">MultiPassInputIterator</a>. The 69value type of the edge iterator must be the same as the edge 70descriptor of the graph. 71 72<tr> 73<td><pre>boost::graph_traits<G>::edges_size_type</pre> 74The unsigned integer type used to represent the number of edges in the 75graph. 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:edges"><TT>edges(g)</TT></a></TD> 87<TD>Returns an iterator-range providing access to all 88 the edges in the graph <TT>g</TT>.<br> 89Return type: <TT>std::pair<edge_iterator, edge_iterator></TT> 90</td> 91</TR> 92 93<tr> 94<TD><TT>num_edges(g)</TT></TD> 95<TD>Returns the number of edges in the graph <TT>g</TT>.<br> 96Return type: <TT>edges_size_type</TT> 97</td> 98</TR> 99 100<tr> 101<TD><TT>source(e, g)</TT></TD> 102<TD> 103Returns the vertex descriptor for <i>u</i> of the edge <i>(u,v)</i> 104represented by <TT>e</TT>.<br> 105Return type: <TT>vertex_descriptor</TT> 106</td> 107</tr> 108 109<tr> 110<TD><TT>target(e, g)</TT></TD> 111<TD> 112Returns the vertex descriptor for 113<i>v</i> of the edge <i>(u,v)</i> represented by <TT>e</TT>.<br> 114Return type: <TT>vertex_descriptor</TT> 115</TD> 116</TR> 117 118</TABLE> 119 120 121<H3>Models</H3> 122 123<UL> 124<LI><a href="./adjacency_list.html"><TT>adjacency_list</TT></a></LI> 125<LI><a href="./edge_list.html"><TT>edge_list</TT></a></LI> 126</UL> 127 128 129<H3>Complexity guarantees</H3> 130 131The <TT>edges()</TT>, <TT>source()</TT>, and <TT>target()</TT> functions 132must all return in constant time. 133 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<P> 142<PRE> 143 template <class G> 144 struct EdgeListGraphConcept 145 { 146 typedef typename boost::graph_traits<G>::edge_iterator 147 edge_iterator; 148 void constraints() { 149 BOOST_CONCEPT_ASSERT(( GraphConcept<G> )); 150 BOOST_CONCEPT_ASSERT(( MultiPassInputIteratorConcept<edge_iterator> )); 151 152 p = edges(g); 153 E = num_edges(g); 154 e = *p.first; 155 u = source(e, g); 156 v = target(e, g); 157 const_constraints(g); 158 } 159 void const_constraints(const G& g) { 160 p = edges(g); 161 E = num_edges(g); 162 e = *p.first; 163 u = source(e, g); 164 v = target(e, g); 165 } 166 std::pair<edge_iterator,edge_iterator> p; 167 typename boost::graph_traits<G>::vertex_descriptor u, v; 168 typename boost::graph_traits<G>::edge_descriptor e; 169 typename boost::graph_traits<G>::edges_size_type E; 170 G g; 171 }; 172</PRE> 173 174 175<br> 176<HR> 177<TABLE> 178<TR valign=top> 179<TD nowrap>Copyright © 2000-2001</TD><TD> 180<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>) 181</TD></TR></TABLE> 182 183</BODY> 184</HTML> 185
