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>Boost Graph Library: Edge List Class</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<H1><A NAME="sec:edge-list-class"></A> 20<PRE> 21edge_list<EdgeIterator, ValueType, DiffType> 22</PRE> 23</H1> 24 25<P> 26The <TT>edge_list</TT> class is an adaptor that turns a pair of edge 27iterators into a class that models <TT>EdgeListGraph</TT>. The 28<TT>value_type</TT> of the edge iterator must be a <TT>std::pair</TT> (or 29at least have <TT>first</TT> and <TT>second</TT> members). The 30<TT>first_type</TT> and <TT>second_type</TT> of the pair must be the 31same and they will be used for the graph's <TT>vertex_descriptor</TT>. 32The <TT>ValueType</TT> and <TT>DiffType</TT> template parameters are only 33needed if your compiler does not support partial 34specialization. Otherwise they default to the correct types. 35 36<P> 37 38<H3>Example</H3> 39 40<P> 41Applying the Bellman-Ford shortest paths algorithm to an 42<TT>edge_list</TT>. 43 44<P> 45<PRE> 46 enum { u, v, x, y, z, N }; 47 char name[] = { 'u', 'v', 'x', 'y', 'z' }; 48 49 typedef std::pair<int,int> E; 50 E edges[] = { E(u,y), E(u,x), E(u,v), 51 E(v,u), 52 E(x,y), E(x,v), 53 E(y,v), E(y,z), 54 E(z,u), E(z,x) }; 55 56 int weight[] = { -4, 8, 5, 57 -2, 58 9, -3, 59 7, 2, 60 6, 7 }; 61 62 typedef boost::edge_list<E*> Graph; 63 Graph g(edges, edges + sizeof(edges) / sizeof(E)); 64 65 std::vector<int> distance(N, std::numeric_limits<short>::max()); 66 std::vector<int> parent(N,-1); 67 68 distance[z] = 0; 69 parent[z] = z; 70 bool r = boost::bellman_ford_shortest_paths(g, int(N), weight, 71 distance.begin(), 72 parent.begin()); 73 if (r) 74 for (int i = 0; i < N; ++i) 75 std::cout << name[i] << ": " << distance[i] 76 << " " << name[parent[i]] << std::endl; 77 else 78 std::cout << "negative cycle" << std::endl; 79</PRE> 80The output is the distance from the root and the parent 81of each vertex in the shortest paths tree. 82<PRE> 83 u: 2 v 84 v: 4 x 85 x: 7 z 86 y: -2 u 87 z: 0 z 88</PRE> 89 90<P> 91<p> 92 93<H3>Where Defined</H3> 94 95<a href="../../../boost/graph/edge_list.hpp"><TT>boost/graph/edge_list.hpp</TT></a> 96 97<P> 98<H3>Template Parameters</H3> 99 100<P> 101<TABLE border> 102<TR> 103<th>Parameter</th><th>Description</th> 104</tr> 105 106<TR><TD><TT>EdgeIterator</TT></TD> <TD>Must be model of <a 107href="http://www.boost.org/sgi/stl/InputIterator.html">InputIterator</a> 108who's <TT>value_type</TT> must be a pair of vertex descriptors.</TD> 109</TR> 110 111<TR><TD><TT>ValueType</TT></TD> 112<TD>The <TT>value_type</TT> of the <TT>EdgeIterator</TT>.<br> 113Default: <TT>std::iterator_traits<EdgeIterator>::value_type</TT></TD> 114</TR> 115 116<TR><TD><TT>DiffType</TT></TD> 117<TD>The <TT>difference_type</TT> of the <TT>EdgeIterator</TT>.<br> 118Default: <TT>std::iterator_traits<EdgeIterator>::difference_type</TT></TD> 119</TR> 120 121</TABLE> 122<P> 123 124<H3>Model of</H3> 125 126<a href="./EdgeListGraph.html">EdgeListGraph</a> 127 128<P> 129 130 131<H3>Associated Types</H3> 132 133<hr> 134 135<tt>boost::graph_traits<edge_list>::vertex_descriptor</tt> 136<br><br> 137The type for the vertex descriptors associated with the 138<TT>edge_list</TT>. This will be the same type as 139<TT>std::iterator_traits<EdgeIterator>::value_type::first_type</TT>. 140 141<hr> 142 143<tt> 144boost::graph_traits<edge_list>::edge_descriptor 145</tt> 146<br><br> 147The type for the edge descriptors associated with the 148<TT>edge_list</TT>. 149 150<hr> 151 152<tt> 153boost::graph_traits<edge_list>::edge_iterator 154</tt> 155<br><br> 156The type for the iterators returned by <TT>edges()</TT>. The iterator 157category of the <TT>edge_iterator</TT> will be the same as that of the 158<TT>EdgeIterator</TT>. 159 160<hr> 161 162<h3>Member Functions</h3> 163 164<hr> 165 166<tt> 167edge_list(EdgeIterator first, EdgeIterator last) 168</tt> 169<br><br> 170Creates a graph object with <TT>n</TT> vertices and with the 171edges specified in the edge list given by the range <TT>[first,last)</TT>. 172 173<hr> 174 175<H3>Non-Member Functions</H3> 176 177<hr> 178 179<tt> 180std::pair<edge_iterator, edge_iterator><br> 181edges(const edge_list& g) 182</tt> 183<br><br> 184Returns an iterator-range providing access to the edge set of graph <TT>g</TT>. 185 186<hr> 187 188<tt> 189vertex_descriptor<br> 190source(edge_descriptor e, const edge_list& g) 191</tt> 192<br><br> 193Returns the source vertex of edge <TT>e</TT>. 194 195<hr> 196 197<tt> 198vertex_descriptor<br> 199target(edge_descriptor e, const edge_list& g) 200</tt> 201<br><br> 202Returns the target vertex of edge <TT>e</TT>. 203 204<hr> 205 206<br> 207<HR> 208<TABLE> 209<TR valign=top> 210<TD nowrap>Copyright © 2000-2001</TD><TD> 211<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 212Indiana University (<A 213HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 214<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> 215<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 216Indiana University (<A 217HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 218</TD></TR></TABLE> 219 220</BODY> 221</HTML> 222
