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>IteratorConstructibleGraph</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:IteratorConstructibleGraph"></A> 19IteratorConstructibleGraph 20</H1> 21 22The IteratorConstructibleGraph concept describes the interface for 23graph types that can be constructed using a kind of edge iterator. The 24edge iterator can be any <a 25href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 26that dereferences to a pair of integers <i>(i,j)</i>, which represent 27an edge that should be in the graph. The two integers <i>i</i> and 28<i>j</i> represent vertices where <i>0 <= i < |V|</i> and <i>0 <= j < 29|V|</i>. The edge iterator's value type should be 30<tt>std::pair<T,T></tt> (or at least be a structure that has 31members <tt>first</tt> and <tt>second</tt>) and the value type 32<tt>T</tt> of the pair must be convertible to the 33<tt>vertices_size_type</tt> of the graph (an integer). 34 35There are two valid expressions required by this concept, both of 36which are constructors. The first creates a graph object from a 37first/last iterator range. The second constructor also takes a 38first/last iterator range and in addition requires the number of 39vertices and number of edges. For some graph and edge iterator types 40the second constructor can be more efficient than the first. 41 42<h3>Example</h3> 43 44The following exampe creates two graph objects from an array of edges 45(vertex pairs). The type <tt>Edge*</tt> satisfies the requirements for 46an <a 47href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 48and can therefore be used to construct a graph. 49 50<pre> 51 typedef ... IteratorConstructibleGraph; 52 typedef boost::graph_traits<IteratorConstructibleGraph> Traits; 53 54 typedef std::pair<Traits::vertices_size_type, 55 Traits::vertices_size_type> Edge; 56 Edge edge_array[] = 57 { Edge(0,1), Edge(0,2), Edge(0,3), Edge(0,4), Edge(0,5), 58 Edge(1, 2), Edge(1,5), Edge(1,3), 59 Edge(2, 4), Edge(2,5), 60 Edge(3, 2), 61 Edge(4, 3), Edge(4,1), 62 Edge(5, 4) }; 63 Edge* first = edge_array, 64 last = edge_array + sizeof(edge_array)/sizeof(Edge); 65 66 IteratorConstructibleGraph G1(first, last); 67 // do something with G1 ... 68 69 Traits::vertices_size_type size_V = 6; 70 Traits::edges_size_type size_E = sizeof(edge_array)/sizeof(Edge); 71 IteratorConstructibleGraph G2(first, last, size_V, size_E); 72 // do something with G2 ... 73</pre> 74 75<h3>Refinement of</h3> 76 77<a href="Graph.html">Graph</a> 78 79<h3>Notation</h3> 80 81<Table> 82<tr> 83<td><tt>G</tt></td> 84<td>is a graph type that models IteratorConstructibleGraph.</td> 85<tr> 86 87<tr> 88<td><tt>g</tt></td> 89<td>is an object of type <tt>G</tt>.</td> 90</tr> 91 92<tr> 93<td><tt>first, last</tt></td> 94<td>are edge iterators (see above).</td> 95</tr> 96 97<tr> 98<td><tt>Tr</tt></td> 99<td>is an object of type <tt>graph_traits<G></tt>.</td> 100</tr> 101 102<tr> 103<td><tt>n_vertices</tt></td> 104<td>is an object of type <tt>Tr::vertices_size_type</tt>.</td> 105</tr> 106 107<tr> 108<td><tt>n_edges</tt></td> 109<td>is an object of type <tt>Tr::edges_size_type</tt>.</td> 110</tr> 111 112</Table> 113 114 115<h3>Valid Expressions</h3> 116 117<Table border> 118 119<tr> 120<td> 121<pre>G g(first, last);</pre> 122Construct graph object <tt>g</tt> given an edge range <tt>[first,last)</tt>. 123</td> 124<tr> 125 126<tr> 127<td> 128<pre>G g(first, last, n_vertices, n_edges);</pre> 129Construct graph object <tt>g</tt> given an edge range 130<tt>[first,last)</tt>, the number of vertices, and the number of 131edges. Sometimes this constructor is more efficient than the 132constructor lacking the graph size information. 133</td> 134</tr> 135 136</Table> 137 138 139<!-- 140<H3>Concept Checking Class</H3> 141 142<PRE> 143</PRE> 144--> 145 146<br> 147<HR> 148<TABLE> 149<TR valign=top> 150<TD nowrap>Copyright © 2000-2001</TD><TD> 151<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 152Indiana University (<A 153HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 154<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> 155<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 156Indiana University (<A 157HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 158</TD></TR></TABLE> 159 160</BODY> 161</HTML> 162
