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

   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>Boost Graph Concepts</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="chapter:graph-concepts"></A>
  20 Graph Concepts
  21 </H1>
  22
  23 <P>
  24 The heart of the Boost Graph Library (BGL) is the interface, or
  25 concepts (in the parlance of generic programming), that define how a
  26 graph can be examined and manipulated in a data-structure neutral
  27 fashion. In fact, the BGL interface need not even be implemented using
  28 a data-structure, as for some problems it is easier or more efficient
  29 to define a graph implicitly based on some functions.
  30
  31 <P>
  32 The BGL interface does not appear as a single graph concept.  Instead
  33 it is factored into much smaller pieces. The reason for this is that
  34 the purpose of a concept is to summarize the requirements for
  35 <i>particular</i> algorithms. Any one algorithm does not need every
  36 kind of graph operation, typically only a small subset.  Furthermore,
  37 there are many graph data-structures that can not provide efficient
  38 implementations of all the operations, but provide highly efficient
  39 implementations of the operations necessary for a particular algorithm.
  40 By factoring the graph interface into many smaller concepts we
  41 provide the graph algorithm writer with a good selection from which to
  42 choose the concept that is the closest match for their algorithm.
  43
  44 Note that because of the use of traits classes rather than member
  45 types, it is not safe (and often will not work) to define subclasses of BGL
  46 graph types; those types may be missing important traits and properties that
  47 were defined externally to the class definition.
  48
  49 <H2>Graph Structure Concepts Overview</H2>
  50
  51 <P>
  52 <A HREF="#fig:graph-concepts">Figure 1</A> shows the refinements
  53 relations between the graph concepts. The reason for factoring the
  54 graph interface into so many concepts is to encourage algorithm
  55 interfaces to require and use only the minimum interface of a graph,
  56 thereby increasing the reusability of the algorithm.
  57
  58
  59 <p></p>
  60 <DIV ALIGN="CENTER"><A NAME="fig:graph-concepts"></A></A>
  61 <TABLE>
  62 <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG>
  63 The graph concepts and refinement relationships.
  64 </CAPTION>
  65 <TR><TD><IMG SRC="./figs/concepts.gif"></TD></TR>
  66 </TABLE>
  67 </DIV>
  68 <p></p>
  69
  70 <A HREF="#tab:graph-concept-reqs">Table&nbsp;1</A>
  71 gives a summary of the valid expressions and associated types for the
  72 graph concepts and provides links to the detailed descriptions of
  73 each of the concepts. The notation used in the table is as follows.
  74
  75 <h3>Notation</h3>
  76
  77 <Table>
  78 <TR>
  79 <TD><tt>G</tt></TD>
  80 <TD>A type that is a model of Graph.</TD>
  81 </TR>
  82
  83 <TR>
  84 <TD><tt>g</tt></TD>
  85 <TD>An object of type <tt>G</tt>.</TD>
  86 </TR>
  87
  88 <TR>
  89 <TD><tt>e</tt></TD>
  90 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
  91 </TR>
  92
  93 <TR>
  94 <TD><tt>e_iter</tt></TD>
  95 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::out_edge_iterator</tt>.</TD>
  96 </TR>
  97
  98 <TR>
  99 <TD><tt>u,v</tt></TD>
 100 <TD>Are objects of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
 101 </TR>
 102
 103 <TR>
 104 <TD><TT>ep</TT></TD><TD>is an object of type <TT>G::edge_property_type</TT></TD>
 105 </TR>
 106
 107 <TR>
 108 <TD><TT>vp</TT></TD><TD>is an object of type <TT>G::vertex_property_type</TT></TD>
 109 </TR>
 110
 111 <TR>
 112 <TD><tt>Property</tt></TD>
 113 <TD>A type used to specify a vertex or edge property.</TD>
 114 </TR>
 115
 116 <TR>
 117 <TD><tt>property</tt></TD>
 118 <TD>An object of type <tt>Property</tt>.</td>
 119 </TR>
 120
 121 </table>
 122
 123
 124
 125
 126 <P>
 127 <BR><P></P>
 128 <DIV ALIGN="CENTER"><A NAME="tab:graph-concept-reqs"></A>
 129 <TABLE>
 130 <CAPTION ALIGN="BOTTOM"><STRONG>Table 1:</STRONG>
 131     Summary of the graph concepts.
 132     </CAPTION>
 133 <TR><TD>
 134 <TABLE border>
 135 <TR><TH ALIGN="LEFT">
 136 <B>Expression</B> </TH>
 137 <TH ALIGN="LEFT" VALIGN="TOP"> <B>Return Type or Description</B> </TH>
 138 </TR>
 139 <TR><TD ALIGN="LEFT" COLSPAN=2>
 140  <a href="./Graph.html">Graph</a> </TD>
 141 </TR>
 142 <TR><TD ALIGN="LEFT">
 143 <TT>boost::graph_traits&lt;G&gt;::vertex_descriptor</TT> </TD>
 144 <TD ALIGN="LEFT" VALIGN="TOP">  The type for
 145   vertex representative objects. </TD>
 146 </TR>
 147 <TR><TD ALIGN="LEFT">
 148 <TT>boost::graph_traits&lt;G&gt;::edge_descriptor</TT> </TD>
 149 <TD ALIGN="LEFT" VALIGN="TOP"> The type for
 150   edge representative objects. </TD>
 151 </TR>
 152 <TR><TD ALIGN="LEFT">
 153 <TT>boost::graph_traits&lt;G&gt;::directed_category</TT> </TD>
 154 <TD ALIGN="LEFT" VALIGN="TOP"> Directed or undirected? </TD>
 155 </TR>
 156 <TR><TD ALIGN="LEFT">
 157 <TT>boost::graph_traits&lt;G&gt;::edge_parallel_category</TT> </TD>
 158 <TD ALIGN="LEFT" VALIGN="TOP"> Allow parallel edges? </TD>
 159 </TR>
 160 <TR><TD ALIGN="LEFT">
 161 <TT>boost::graph_traits&lt;G&gt;::traversal_category</TT> </TD> <TD
 162 ALIGN="LEFT" VALIGN="TOP">The ways in which the vertices and edges of
 163 the graph can be visited.</TD>
 164 </TR>
 165 <!---------------------------------------------------------------->
 166 <TR><TD ALIGN="LEFT" COLSPAN=2>
 167  <a href="./IncidenceGraph.html">IncidenceGraph</a> refines Graph </TD>
 168 </TR>
 169 <TR><TD ALIGN="LEFT">
 170 <TT>boost::graph_traits&lt;G&gt;::out_edge_iterator</TT> </TD>
 171 <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through
 172   the out-edges. </TD>
 173 </TR>
 174 <TR><TD ALIGN="LEFT">
 175 <TT>boost::graph_traits&lt;G&gt;::degree_size_type</TT> </TD>
 176 <TD ALIGN="LEFT" VALIGN="TOP"> The integer type for
 177 vertex degee. </TD>
 178 </TR>
 179 <TR><TD ALIGN="LEFT">
 180 <TT>out_edges(v, g)</TT> </TD>
 181 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;out_edge_iterator, out_edge_iterator&gt;</TT> </TD>
 182 </TR>
 183 <TR><TD ALIGN="LEFT">
 184 <TT>source(e, g)</TT> </TD>
 185 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
 186 </TR>
 187 <TR><TD ALIGN="LEFT">
 188 <TT>target(e, g)</TT> </TD>
 189 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
 190 </TR>
 191 <TR><TD ALIGN="LEFT">
 192 <TT>out_degree(v, g)</TT> </TD>
 193 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
 194 </TR>
 195 <!---------------------------------------------------------------->
 196 <TR><TD ALIGN="LEFT" COLSPAN=2>
 197  <a href="./BidirectionalGraph.html">BidirectionalGraph</a> refines
 198   IncidenceGraph </TD>
 199 </TR>
 200 <TR><TD ALIGN="LEFT">
 201 <TT>boost::graph_traits&lt;G&gt;::in_edge_iterator</TT> </TD>
 202 <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the in-edges. </TD>
 203 </TR>
 204 <TR><TD ALIGN="LEFT">
 205 <TT>in_edges(v, g)</TT> </TD>
 206 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;in_edge_iterator, in_edge_iterator&gt;</TT> </TD>
 207 </TR>
 208 <TR><TD ALIGN="LEFT">
 209 <TT>in_degree(v, g)</TT> </TD>
 210 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
 211 </TR>
 212 <TR><TD ALIGN="LEFT">
 213 <TT>degree(e, g)</TT> </TD>
 214 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>degree_size_type</TT> </TD>
 215 </TR>
 216 <!---------------------------------------------------------------->
 217 <TR><TD ALIGN="LEFT" COLSPAN=2>
 218 <a href="./AdjacencyGraph.html">AdjacencyGraph</a> refines Graph</TD>
 219 </TR>
 220 <TR><TD ALIGN="LEFT">
 221 <TT>boost::graph_traits&lt;G&gt;::adjacency_iterator</TT> </TD>
 222 <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through
 223   adjacent vertices. </TD>
 224 </TR>
 225 <TR><TD ALIGN="LEFT">
 226 <TT>adjacent_vertices(v, g)</TT> </TD>
 227 <TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair&lt;adjacency_iterator, adjacency_iterator&gt;</TT> </TD>
 228 </TR>
 229 <!---------------------------------------------------------------->
 230 <TR><TD ALIGN="LEFT" COLSPAN=2>
 231 <a href="./VertexListGraph.html">VertexListGraph</a> refines
 232   Graph</TD>
 233 </TR>
 234 <TR><TD ALIGN="LEFT">
 235 <TT>boost::graph_traits&lt;G&gt;::vertex_iterator</TT> </TD>
 236 <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the
 237   graph's vertex set. </TD>
 238 </TR>
 239 <TR><TD ALIGN="LEFT">
 240 <TT>boost::graph_traits&lt;G&gt;::vertices_size_type</TT> </TD>
 241 <TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
 242 number of vertices in the graph. </TD>
 243 </TR>
 244 <TR><TD ALIGN="LEFT">
 245 <TT>vertices(g)</TT>  </TD>
 246 <TD ALIGN="LEFT" VALIGN="TOP"><TT>std::pair&lt;vertex_iterator, vertex_iterator&gt;</TT> </TD>
 247 </TR>
 248 <TR><TD ALIGN="LEFT">
 249 <TT>num_vertices(g)</TT> </TD>
 250 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertices_size_type</TT>  </TD>
 251 </TR>
 252 <!---------------------------------------------------------------->
 253 <TR><TD ALIGN="LEFT" COLSPAN=2>
 254 <a href="./EdgeListGraph.html">EdgeListGraph</a> refines Graph</TD>
 255 </TR>
 256 <TR><TD ALIGN="LEFT">
 257 <TT>boost::graph_traits&lt;G&gt;::edge_iterator</TT> </TD>
 258 <TD ALIGN="LEFT" VALIGN="TOP"> Iterate through the graph's
 259   edge set. </TD>
 260 </TR>
 261 <TR><TD ALIGN="LEFT">
 262 <TT>boost::graph_traits&lt;G&gt;::edges_size_type</TT> </TD>
 263 <TD ALIGN="LEFT" VALIGN="TOP"> The unsigned integer type for
 264 number of edges in the graph. </TD>
 265 </TR>
 266 <TR><TD ALIGN="LEFT">
 267 <TT>edges(g)</TT> </TD>
 268 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_iterator, edge_iterator&gt;</TT> </TD>
 269 </TR>
 270 <TR><TD ALIGN="LEFT">
 271 <TT>num_edges(g)</TT> </TD>
 272 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>edges_size_type</TT>  </TD>
 273 </TR>
 274 <TR><TD ALIGN="LEFT">
 275 <TT>source(e, g)</TT> </TD>
 276 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
 277 </TR>
 278 <TR><TD ALIGN="LEFT">
 279 <TT>target(e, g)</TT> </TD>
 280 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
 281 </TR>
 282 <!---------------------------------------------------------------->
 283 <TR><TD ALIGN="LEFT" COLSPAN=2>
 284 <a href="./AdjacencyMatrix.html">AdjacencyMatrix</a> refines Graph</TD>
 285 </TR>
 286 <TR><TD ALIGN="LEFT">
 287 <TT>edge(u, v, g)</TT> </TD>
 288 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_descriptor, bool&gt;</TT> </TD>
 289 </TR>
 290 <TR><TD ALIGN="LEFT" COLSPAN=2>
 291 <a href="./MutableGraph.html">MutableGraph</a> refines
 292   Graph</TD>
 293 </TR>
 294 <TR><TD ALIGN="LEFT">
 295 <TT>add_vertex(g)</TT> </TD>
 296 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
 297 </TR>
 298 <TR><TD ALIGN="LEFT">
 299 <TT>clear_vertex(v, g)</TT> </TD>
 300 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
 301 </TR>
 302 <TR><TD ALIGN="LEFT">
 303 <TT>remove_vertex(v, g)</TT> </TD>
 304 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
 305 </TR>
 306 <TR><TD ALIGN="LEFT">
 307 <TT>add_edge(u, v, g)</TT> </TD>
 308 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_descriptor, bool&gt;</TT> </TD>
 309 </TR>
 310 <TR><TD ALIGN="LEFT">
 311 <TT>remove_edge(u, v, g)</TT> </TD>
 312 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
 313 </TR>
 314 <TR><TD ALIGN="LEFT">
 315 <TT>remove_edge(e, g)</TT> </TD>
 316 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
 317 </TR>
 318 <TR><TD ALIGN="LEFT">
 319 <TT>remove_edge(e_iter, g)</TT> </TD>
 320 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>void</TT> </TD>
 321 </TR>
 322 <!---------------------------------------------------------------->
 323 <TR><TD ALIGN="LEFT" COLSPAN=2>
 324 <a href="./MutablePropertyGraph.html">MutablePropertyGraph</a> refines
 325   Graph</TD>
 326 </TR>
 327 <TR><TD ALIGN="LEFT">
 328 <TT>add_vertex(vp, g)</TT> </TD>
 329 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>vertex_descriptor</TT> </TD>
 330 </TR>
 331 <TR><TD ALIGN="LEFT">
 332 <TT>add_edge(u, v, ep, g)</TT> </TD>
 333 <TD ALIGN="LEFT" VALIGN="TOP"> <TT>std::pair&lt;edge_descriptor,
 334   bool&gt;</TT> </TD>
 335 </TR>
 336 <!---------------------------------------------------------------->
 337 <TR>
 338 <TD ALIGN="LEFT" COLSPAN=2>
 339 <a href="./PropertyGraph.html">PropertyGraph</a> refines Graph</TD>
 340 </TR>
 341 <TR><TD ALIGN="LEFT">
 342 <TT>boost::property_map&lt;G, Property&gt;::type</TT> </TD>
 343 <TD ALIGN="LEFT" VALIGN="TOP">Type for a mutable property map.</TD>
 344 </TR>
 345 <TR><TD ALIGN="LEFT">
 346 <TT>boost::property_map&lt;G, Property&gt;::const_type</TT> </TD>
 347 <TD ALIGN="LEFT" VALIGN="TOP">Type for a non-mutable property map.</TD>
 348 </TR>
 349 <TR><TD ALIGN="LEFT">
 350 <TT>get(property, g)</TT> </TD>
 351 <TD ALIGN="LEFT" VALIGN="TOP"> Function to get a property map. </TD>
 352 </TR>
 353
 354 <TR><TD ALIGN="LEFT">
 355 <TT>get(property,&nbsp;g,&nbsp;x)</TT>
 356 </TD>
 357 <TD ALIGN="LEFT" VALIGN="TOP">Get property value for vertex or edge <tt>x</tt>. </TD>
 358 </TR>
 359
 360 <TR><TD ALIGN="LEFT">
 361 <TT>put(property,&nbsp;g,&nbsp;x,&nbsp;v)</TT>
 362 </TD>
 363 <TD ALIGN="LEFT" VALIGN="TOP">Set property value for vertex or edge
 364 <tt>x</tt> to <tt>v</tt>. </TD>
 365 </TR>
 366
 367 </table>
 368 </table>
 369 </DIV><P></P>
 370 <BR>
 371
 372 <P>
 373
 374 <H2><A NAME="sec:undirected-graphs"></A>
 375 Undirected Graphs
 376 </H2>
 377
 378 <P>
 379 The interface that the BGL provides for accessing and manipulating an
 380 undirected graph is the same as the interface for directed graphs
 381 described in the following sections, however there are some
 382 differences in the behaviour and semantics.  For example, in a
 383 directed graph we can talk about out-edges and in-edges of a vertex.
 384 In an undirected graph there is no ``in'' and ``out'', there are just
 385 edges incident to a vertex. Nevertheless, in the BGL we still use the
 386 <TT>out_edges()</TT> function (or <TT>in_edges()</TT>) to access the
 387 incident edges in an undirected graph. Similarly, an undirected edge
 388 has no ``source'' and ``target'' but merely an unordered pair of
 389 vertices, but in the BGL we still use <TT>source()</TT> and
 390 <TT>target()</TT> to access these vertices.  The reason the BGL does
 391 not provide a separate interface for undirected graphs is that many
 392 algorithms on directed graphs also work on undirected graphs, and it
 393 would be inconvenient to have to duplicate the algorithms just because
 394 of an interface difference. When using undirected graphs just mentally
 395 disregard the directionality in the function names. The example below
 396 demonstrates using the <TT>out_edges()</TT>, <TT>source()</TT>, and
 397 <TT>target()</TT> with an undirected graph. The source code for this
 398 example and the following one can be found in <a
 399 href="../example/undirected_adjacency_list.cpp"><TT>example/undirected_adjacency_list.cpp</TT></a>.
 400
 401 <P>
 402 <PRE>
 403   const int V = 2;
 404   typedef ... UndirectedGraph;
 405   UndirectedGraph undigraph(V);
 406
 407   std::cout &lt;&lt; "the edges incident to v: ";
 408   boost::graph_traits&lt;UndirectedGraph&gt;::out_edge_iterator e, e_end;
 409   boost::graph_traits&lt;UndirectedGraph&gt;::vertex_descriptor
 410     s = vertex(0, undigraph);
 411   for (boost::tie(e, e_end) = out_edges(s, undigraph); e != e_end; ++e)
 412     std::cout &lt;&lt; "(" &lt;&lt; source(*e, undigraph)
 413               &lt;&lt; "," &lt;&lt; target(*e, undigraph) &lt;&lt; ")" &lt;&lt; endl;
 414 </PRE>
 415
 416 <P>
 417 Even though the interface is the same for undirected graphs, there are
 418 some behavioral differences because edge equality is defined
 419 differently. In a directed graph, edge <i>(u,v)</i> is never equal to edge
 420 <i>(v,u)</i>, but in an undirected graph they may be equal.  If the
 421 undirected graph is a multigraph then <i>(u,v)</i> and <i>(v,u)</i> might be
 422 parallel edges. If the graph is not a multigraph then <i>(u,v)</i> and
 423 <i>(v,u)</i> must be the same edge.
 424
 425 <P>
 426 In the example below the edge equality test will return <TT>false</TT>
 427 for the directed graph and <TT>true</TT> for the undirected graph. The
 428 difference also affects the meaning of <TT>add_edge()</TT>. In the
 429 example below, if we had also written <TT>add_edge(v, u,
 430 undigraph)</TT>, this would have added a parallel edge between
 431 <i>u</i> and <i>v</i> (provided the graph type allows parallel
 432 edges). The difference in edge equality also affects the association
 433 of edge properties. In the directed graph, the edges <i>(u,v)</i> and
 434 <i>(v,u)</i> can have distinct weight values, whereas in the
 435 undirected graph the weight of <i>(u,v)</i> is the same as the weight
 436 of <i>(v,u)</i> since they are the same edge.
 437
 438 <P>
 439 <PRE>
 440   typedef ... DirectedGraph;
 441   DirectedGraph digraph(V);
 442   {
 443     boost::graph_traits&lt;DirectedGraph&gt;::vertex_descriptor u, v;
 444     u = vertex(0, digraph);
 445     v = vertex(1, digraph);
 446     add_edge(digraph, u, v, Weight(1.2));
 447     add_edge(digraph, v, u, Weight(2.4));
 448     boost::graph_traits&lt;DirectedGraph&gt;::edge_descriptor e1, e2;
 449     bool found;
 450     boost::tie(e1, found) = edge(u, v, digraph);
 451     boost::tie(e2, found) = edge(v, u, digraph);
 452     std::cout &lt;&lt; "in a directed graph is ";
 453     std::cout &lt;&lt; "(u,v) == (v,u) ? " &lt;&lt; (e1 == e2) &lt;&lt; std::endl;
 454
 455     property_map&lt;DirectedGraph, edge_weight_t&gt;::type
 456       weight = get(edge_weight, digraph);
 457     cout &lt;&lt; "weight[(u,v)] = " &lt;&lt; get(weight, e1) &lt;&lt; endl;
 458     cout &lt;&lt; "weight[(v,u)] = " &lt;&lt; get(weight, e2) &lt;&lt; endl;
 459   }
 460   {
 461     boost::graph_traits&lt;UndirectedGraph&gt;::vertex_descriptor u, v;
 462     u = vertex(0, undigraph);
 463     v = vertex(1, undigraph);
 464     add_edge(undigraph, u, v, Weight(3.1));
 465     boost::graph_traits&lt;UndirectedGraph&gt;::edge_descriptor e1, e2;
 466     bool found;
 467     boost::tie(e1, found) = edge(u, v, undigraph);
 468     boost::tie(e2, found) = edge(v, u, undigraph);
 469     std::cout &lt;&lt; "in an undirected graph is ";
 470     std::cout &lt;&lt; "(u,v) == (v,u) ? " &lt;&lt; (e1 == e2) &lt;&lt; std::endl;
 471
 472     property_map&lt;UndirectedGraph, edge_weight_t&gt;::type
 473       weight = get(edge_weight, undigraph);
 474     cout &lt;&lt; "weight[(u,v)] = " &lt;&lt; get(weight, e1) &lt;&lt; endl;
 475     cout &lt;&lt; "weight[(v,u)] = " &lt;&lt; get(weight, e2) &lt;&lt; endl;
 476   }
 477 </PRE>
 478 The output is:
 479 <PRE>
 480 in a directed graph is (u,v) == (v,u) ? 0
 481 weight[(u,v)] = 1.2
 482 weight[(v,u)] = 2.4
 483 in an undirected graph is (u,v) == (v,u) ? 1
 484 weight[(u,v)] = 3.1
 485 weight[(v,u)] = 3.1
 486 </PRE>
 487
 488
 489 <br>
 490 <HR>
 491 <TABLE>
 492 <TR valign=top>
 493 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 494 <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>)
 495 </TD></TR></TABLE>
 496
 497 </BODY>
 498 </HTML>