projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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 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<G>::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<G>::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<G>::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<G>::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<G>::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<G>::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<G>::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<G>::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<G>::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<G>::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<out_edge_iterator, out_edge_iterator></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<G>::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<in_edge_iterator, in_edge_iterator></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<G>::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<adjacency_iterator, adjacency_iterator></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<G>::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<G>::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<vertex_iterator, vertex_iterator></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<G>::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<G>::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<edge_iterator, edge_iterator></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<edge_descriptor, bool></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<edge_descriptor, bool></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<edge_descriptor, | |
| 334 | bool></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<G, Property>::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<G, Property>::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, g, 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, g, x, 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 << "the edges incident to v: "; | |
| 408 | boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end; | |
| 409 | boost::graph_traits<UndirectedGraph>::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 << "(" << source(*e, undigraph) | |
| 413 | << "," << target(*e, undigraph) << ")" << 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<DirectedGraph>::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<DirectedGraph>::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 << "in a directed graph is "; | |
| 453 | std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl; | |
| 454 | ||
| 455 | property_map<DirectedGraph, edge_weight_t>::type | |
| 456 | weight = get(edge_weight, digraph); | |
| 457 | cout << "weight[(u,v)] = " << get(weight, e1) << endl; | |
| 458 | cout << "weight[(v,u)] = " << get(weight, e2) << endl; | |
| 459 | } | |
| 460 | { | |
| 461 | boost::graph_traits<UndirectedGraph>::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<UndirectedGraph>::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 << "in an undirected graph is "; | |
| 470 | std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl; | |
| 471 | ||
| 472 | property_map<UndirectedGraph, edge_weight_t>::type | |
| 473 | weight = get(edge_weight, undigraph); | |
| 474 | cout << "weight[(u,v)] = " << get(weight, e1) << endl; | |
| 475 | cout << "weight[(v,u)] = " << get(weight, e2) << 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 © 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> |