ceph/src/boost/libs/graph/doc/edge_list.html

   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>
  21 edge_list&lt;EdgeIterator, ValueType, DiffType&gt;
  22 </PRE>
  23 </H1>
  24
  25 <P>
  26 The <TT>edge_list</TT> class is an adaptor that turns a pair of edge
  27 iterators 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
  29 at 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
  31 same and they will be used for the graph's <TT>vertex_descriptor</TT>.
  32 The <TT>ValueType</TT> and <TT>DiffType</TT> template parameters are only
  33 needed if your compiler does not support partial
  34 specialization. Otherwise they default to the correct types.
  35
  36 <P>
  37
  38 <H3>Example</H3>
  39
  40 <P>
  41 Applying 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&lt;int,int&gt; 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&lt;E*&gt; Graph;
  63   Graph g(edges, edges + sizeof(edges) / sizeof(E));
  64
  65   std::vector&lt;int&gt; distance(N, std::numeric_limits&lt;short&gt;::max());
  66   std::vector&lt;int&gt; 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 &lt; N; ++i)
  75       std::cout &lt;&lt; name[i] &lt;&lt; ": " &lt;&lt; distance[i]
  76                 &lt;&lt; " " &lt;&lt; name[parent[i]] &lt;&lt; std::endl;
  77   else
  78     std::cout &lt;&lt; "negative cycle" &lt;&lt; std::endl;
  79 </PRE>
  80 The output is the distance from the root and the parent
  81 of 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
 107 href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
 108 who'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>
 113 Default: <TT>std::iterator_traits&lt;EdgeIterator&gt;::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>
 118 Default: <TT>std::iterator_traits&lt;EdgeIterator&gt;::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&lt;edge_list&gt;::vertex_descriptor</tt>
 136 <br><br>
 137 The 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&lt;EdgeIterator&gt;::value_type::first_type</TT>.
 140
 141 <hr>
 142
 143 <tt>
 144 boost::graph_traits&lt;edge_list&gt;::edge_descriptor
 145 </tt>
 146 <br><br>
 147 The type for the edge descriptors associated with the
 148 <TT>edge_list</TT>.
 149
 150 <hr>
 151
 152 <tt>
 153 boost::graph_traits&lt;edge_list&gt;::edge_iterator
 154 </tt>
 155 <br><br>
 156 The type for the iterators returned by <TT>edges()</TT>. The iterator
 157 category 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>
 167 edge_list(EdgeIterator first, EdgeIterator last)
 168 </tt>
 169 <br><br>
 170 Creates a graph object with <TT>n</TT> vertices and with the
 171 edges 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>
 180 std::pair&lt;edge_iterator, edge_iterator&gt;<br>
 181 edges(const edge_list&amp; g)
 182 </tt>
 183 <br><br>
 184 Returns an iterator-range providing access to the edge set of graph <TT>g</TT>.
 185
 186 <hr>
 187
 188 <tt>
 189 vertex_descriptor<br>
 190 source(edge_descriptor e, const edge_list&amp; g)
 191 </tt>
 192 <br><br>
 193 Returns the source vertex of edge <TT>e</TT>.
 194
 195 <hr>
 196
 197 <tt>
 198 vertex_descriptor<br>
 199 target(edge_descriptor e, const edge_list&amp; g)
 200 </tt>
 201 <br><br>
 202 Returns 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 &copy; 2000-2001</TD><TD>
 211 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 212 Indiana University (<A
 213 HREF="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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 216 Indiana University (<A
 217 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 218 </TD></TR></TABLE>
 219
 220 </BODY>
 221 </HTML>