ceph/src/boost/libs/graph/doc/subgraph.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 Library: Subgraph</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="sec:subgraph-class"></A>
  19 <pre>
  20 subgraph&lt;Graph&gt;
  21 </pre>
  22 </h1>
  23
  24 <!--The space consumption of the <tt>subgraph</tt> is quite high.
  25 We should change subgraph from representing induced subgraphs to just
  26 normal subgraphs (from talk with Steven North). -->
  27
  28 <p>
  29 The subgraph class provides a mechanism for keeping track of a graph
  30 and its subgraphs. A graph <i>G'</i> is a <i>subgraph</i> of a graph
  31 <i>G</i> if the vertex set of <i>G'</i> is a subset of the vertex set
  32 of <i>G</i> and if the edge set of <i>G'</i> is a subset of the edge
  33 set of <i>G</i>. That is, if <i>G'=(V',E')</i> and <i>G=(V,E)</i>,
  34 then <i>G'</i> is a subgraph of <i>G</i> if <i>V'</i> is a subset of
  35 <i>V</i> and <i>E</i> is a subset of <i>E'</i>. An <i>induced
  36 subgraph</i> is a subgraph formed by specifying a set of vertices
  37 <i>V'</i> and then selecting all of the edges from the original graph
  38 that connect two vertices in <i>V'</i>. So in this case <i>E' = {(u,v)
  39 in E: u,v in V'}</i>.  Figure 1 shows a graph <i>G<sub>0</sub></i> and
  40 two subgraphs <i>G<sub>1</sub></i> and <i>G<sub>2</sub></i>. The edge
  41 set for <i>G<sub>1</sub></i> is <i>E<sub>1</sub> = { (E,F), (C,F)
  42 }</i> and the edge set for <i>G<sub>2</sub></i> is <i>E<sub>2</sub> =
  43 { (A,B) }</i>. Edges such as <i>(E,B)</i> and <i>(F,D)</i> that cross
  44 out of a subgraph are not in the edge set of the subgraph.
  45 </p>
  46
  47 <P></P>
  48 <DIV ALIGN="center"><A NAME="fig:subgraph-tree"></A>
  49 <TABLE>
  50 <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> A graph with nested subgraphs, maintained in a tree structure.</CAPTION>
  51 <TR><TD><IMG SRC="./figs/subgraph.gif"></TD>
  52 <TD><IMG SRC="./figs/subgraph-tree.gif"></TD></TR>
  53 </TABLE>
  54 </DIV><P></P>
  55
  56 <p>The <tt>subgraph</tt> class implements induced subgraphs. The main graph
  57 and its subgraphs are maintained in a tree data structure. The main
  58 graph is the root, and subgraphs are either children of the root or of
  59 other subgraphs. All of the nodes in this tree, including the root
  60 graph, are instances of the <tt>subgraph</tt> class.  The
  61 <tt>subgraph</tt> implementation ensures that each node in the tree is
  62 an induced subgraph of its parent. The <tt>subgraph</tt> class
  63 implements the BGL graph interface, so each subgraph object can be
  64 treated as a graph.</p>
  65
  66 <h3>Example</h3>
  67
  68 The full source code for this example is in
  69 <tt>example/subgraph.cpp</tt>. To create a graph and subgraphs, first
  70 create the root graph object.  Here we use <tt>adjacency_list</tt> as
  71 the underlying graph implementation. The underlying graph type is
  72 required to have <tt>vertex_index</tt> and <tt>edge_index</tt>
  73 internal properties, so we add an edge index property to the adjacency
  74 list. We do not need to add a vertex index properety because that is
  75 built in to the <tt>adjacency_list</tt>. We will be building the graph
  76 and subgraphs in Figure 1, so we will need a total of six vertices.
  77
  78 <pre>
  79 typedef adjacency_list_traits&lt; vecS, vecS, directedS &gt; Traits;
  80 typedef subgraph&lt; adjacency_list&lt; vecS, vecS, directedS,
  81   no_property, property&lt; edge_index_t, int &gt; &gt; &gt; Graph;
  82
  83 const int N = 6;
  84 Graph G0(N);
  85
  86 enum { A, B, C, D, E, F};  // for conveniently refering to vertices in G0
  87 </pre>
  88
  89 Next we create two empty subgraph objects, specifying <tt>G0</tt> as
  90 their parent.
  91
  92 <pre>
  93 Graph& G1 = G0.create_subgraph(), G2 = G0.create_subgraph();
  94 enum { A1, B1, C2 }; // for conveniently refering to vertices in G1
  95 enum { A2, B2 };     // for conveniently refering to vertices in G2
  96 </pre>
  97
  98 We can add vertices from the root graph to the subgraphs using the
  99 <tt>add_vertex</tt> function. Since the graph implementation is
 100 <tt>adjacency_list</tt> with <tt>VertexList=vecS</tt>, we can use the
 101 integers (or in this case enums) in the range <i>[0,6)</i> as vertex
 102 descriptors.
 103
 104 <pre>
 105 add_vertex(C, G1); // global vertex C becomes local A1 for G1
 106 add_vertex(E, G1); // global vertex E becomes local B1 for G1
 107 add_vertex(F, G1); // global vertex F becomes local C1 for G1
 108
 109 add_vertex(A, G2); // global vertex A becomes local A2 for G2
 110 add_vertex(B, G2); // global vertex B becomes local B2 for G2
 111 </pre>
 112
 113 Next we can add edges to the main graph using the usual
 114 <tt>add_edge</tt> function.
 115
 116 <pre>
 117 add_edge(A, B, G0);
 118 add_edge(B, C, G0);
 119 add_edge(B, D, G0);
 120 add_edge(E, B, G0);
 121 add_edge(E, F, G0);
 122 add_edge(F, D, G0);
 123 </pre>
 124
 125 We can also add edges to subgraphs such as <tt>G1</tt> using the
 126 <tt>add_edge</tt> function. Each subgraph has its own vertex and edge
 127 descriptors, which we call <i>local</i> descriptors. We refer to root
 128 graph's vertex and edge descriptors as the <i>global</i>
 129 descriptors. Above, we used global vertex descriptors to add vertices
 130 to the graph. However, most <tt>subgraph</tt> functions work with
 131 local descriptors. So in the following call to <tt>add_edge</tt> we
 132 add the edge <tt>(A1,C1)</tt> (or numerically <tt>(0,2)</tt>) which is
 133 the local version (for subgraph <tt>G1</tt>) of the global edge
 134 <tt>(C,F)</tt> (or numerically <tt>(2,5)</tt>).  Adding an edge to a
 135 subgraph causes the edge to also be added to all of its ancestors in
 136 the subgraph tree to ensure that the subgraph property is maintained.
 137
 138 <pre>
 139 add_edge(A1, C1, G1); // (A1,C1) is subgraph G1 local indices
 140                       // for the global edge (C,F).
 141 </pre>
 142
 143 <!----------------------------->
 144 <h3>Where Defined</h3>
 145
 146 <tt>boost/graph/subgraph.hpp</tt>
 147
 148 <!----------------------------->
 149 <h3>Template Parameters</h3>
 150
 151 <P>
 152 <TABLE border>
 153 <TR>
 154 <th>Parameter</th><th>Description</th>
 155 </tr>
 156 <tr><td><tt>Graph</tt> </td>
 157 <td> A graph type modeling <a href="VertexMutableGraph.html">VertexMutableGraph</a>
 158   and <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>. Also
 159   the graph must have internal <tt>vertex_index</tt> and
 160   <tt>edge_index</tt> properties. The vertex indices must be maintained
 161   automatically by the graph, whereas the edge indices will be
 162   assigned by the <tt>subgraph</tt> class implementation. </td>
 163 </tr>
 164 </table>
 165
 166
 167 <!----------------------------->
 168 <h3>Model Of</h3>
 169
 170 <tt>subgraph</tt> is a model of <a href="VertexMutableGraph.html">VertexMutableGraph</a>. Also, if
 171 the <tt>Graph</tt> type models <a href="VertexListGraph.html">VertexListGraph</a>,
 172 <a href="EdgeListGraph.html">EdgeListGraph</a> and/or <a href="BidirectionalGraph.html">BidirectionalGraph</a>, then
 173 <tt>subgraph&lt;Graph&gt;</tt> will also models these concepts.
 174
 175 <!----------------------------->
 176 <h3>Associated Types</h3>
 177
 178 If the graph is the root of the subgraph tree, then the vertex and
 179 edge descriptors are both the local descriptors for the root graph,
 180 and they are the global descriptors. If the graph is not the root,
 181 then the descriptors are local descriptors for the subgraph.
 182 The subgraph iterators are the same iterator types as the iterators of
 183 the underlying <tt>Graph</tt> type.
 184
 185 <hr>
 186
 187 <pre>
 188 graph_traits&lt;subgraph&gt;::vertex_descriptor
 189 </pre>
 190     The type for the vertex descriptors.
 191  (Required by <a href="Graph.html">Graph</a>.)
 192
 193 <hr>
 194
 195 <pre>
 196 graph_traits&lt;subgraph&gt;::edge_descriptor
 197 </pre>
 198     The type for the edge descriptors.
 199     (Required by <a href="Graph.html">Graph</a>.)
 200
 201 <hr>
 202
 203 <pre>
 204 graph_traits&lt;subgraph&gt;::vertex_iterator
 205 </pre>
 206     The type for the iterators returned by <tt>vertices</tt>.
 207     (Required by <a href="VertexListGraph.html">VertexListGraph</a>.)
 208
 209 <hr>
 210
 211 <pre>
 212 graph_traits&lt;subgraph&gt;::edge_iterator
 213 </pre>
 214     The type for the iterators returned by <tt>edges</tt>.
 215     (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)
 216
 217 <hr>
 218 <pre>
 219 graph_traits&lt;subgraph&gt;::out_edge_iterator
 220 </pre>
 221     The type for the iterators returned by <tt>out_edges</tt>.
 222     (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)
 223
 224 <hr>
 225 <pre>
 226 graph_traits&lt;subgraph&gt;::in_edge_iterator
 227 </pre>
 228     The <tt>in_edge_iterator</tt> is the
 229     iterator type returned by the <tt>in_edges</tt> function.
 230     (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.)
 231
 232 <hr>
 233 <pre>
 234 graph_traits&lt;subgraph&gt;::adjacency_iterator
 235 </pre>
 236     The type for the iterators returned by <tt>adjacent_vertices</tt>.
 237     (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.)
 238
 239 <hr>
 240 <pre>
 241 graph_traits&lt;subgraph&gt;::directed_category
 242 </pre>
 243     Provides information about whether the graph is directed
 244     (<tt>directed_tag</tt>) or undirected (<tt>undirected_tag</tt>).
 245     (Required by <a href="Graph.html">Graph</a>.)
 246
 247 <hr>
 248 <pre>
 249 graph_traits&lt;subgraph&gt;::edge_parallel_category
 250 </pre>
 251     This describes whether the graph class allows the insertion of
 252     parallel edges (edges with the same source and target), which
 253     depends on the underlying <tt>Graph</tt> class. The two tags are
 254     <tt>allow_parallel_edge_tag</tt> and
 255     <tt>disallow_parallel_edge_tag</tt>.
 256     (Required by <a href="Graph.html">Graph</a>.)
 257
 258 <hr>
 259 <pre>
 260 graph_traits&lt;subgraph&gt;::vertices_size_type
 261 </pre>
 262   The type used for dealing with the number of vertices in
 263   the graph.
 264   (Required by <a href="VertexListGraph.html">VertexListGraph</a>.)
 265
 266 <hr>
 267 <pre>
 268 graph_traits&lt;subgraph&gt;::edges_size_type
 269 </pre>
 270   The type used for dealing with the number of edges in the graph.
 271   (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)
 272
 273 <hr>
 274 <pre>
 275 graph_traits&lt;subgraph&gt;::degree_size_type
 276 </pre>
 277   The type used for dealing with the number of out-edges of a vertex.
 278   (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)
 279
 280 <hr>
 281 <pre>
 282 property_map&lt;subgraph, PropertyTag&gt;::type
 283 property_map&lt;subgraph, PropertyTag&gt;::const_type
 284 </pre>
 285   The map type for vertex or edge properties in the graph. The
 286   specific property is specified by the <tt>PropertyTag</tt> template
 287   argument, and must match one of the properties specified in the
 288   <tt>VertexProperty</tt> or <tt>EdgeProperty</tt> for the graph.
 289   (Required by <a href="PropertyGraph.html">PropertyGraph</a>.)
 290
 291 <hr>
 292 <pre>
 293 subgraph::children_iterator
 294 </pre>
 295   The iterator type for accessing the children subgraphs of the graph.
 296
 297
 298
 299 <!----------------------------->
 300 <h3>Member Functions</h3>
 301
 302
 303
 304 <hr>
 305 <pre>
 306 subgraph(vertices_size_type n, const GraphProperty&amp; p = GraphProperty())
 307 </pre>
 308     Creates the root graph object with <tt>n</tt> vertices and zero edges.
 309
 310 <hr>
 311 <pre>
 312 subgraph&lt;Graph&gt;& create_subgraph();
 313 </pre>
 314     Creates an empty subgraph object whose parent is <i>this</i>
 315     graph.
 316
 317 <hr>
 318 <pre>
 319 template &lt;typename VertexIterator&gt;
 320 subgraph&lt;Graph&gt;&amp;
 321 create_subgraph(VertexIterator first, VertexIterator last)
 322 </pre>
 323     Creates a subgraph object with the specified vertex set.  The
 324     edges of the subgraph are induced by the vertex set. That is,
 325     every edge in the parent graph (which is <i>this</i> graph) that
 326     connects two vertices in the subgraph will be added to the
 327     subgraph.
 328
 329 <hr>
 330 <pre>
 331 vertex_descriptor local_to_global(vertex_descriptor u_local) const
 332 </pre>
 333     Converts a local vertex descriptor to the corresponding global
 334     vertex descriptor.
 335
 336 <hr>
 337 <pre>
 338 vertex_descriptor global_to_local(vertex_descriptor u_global) const
 339 </pre>
 340     Converts a global vertex descriptor to the corresponding local
 341     vertex descriptor.
 342
 343 <hr>
 344 <pre>
 345 edge_descriptor local_to_global(edge_descriptor e_local) const
 346 </pre>
 347     Converts a local edge descriptor to the corresponding global edge
 348     descriptor.
 349
 350 <hr>
 351 <pre>
 352 edge_descriptor global_to_local(edge_descriptor u_global) const
 353 </pre>
 354     Converts a global edge descriptor to the corresponding local edge
 355     descriptor.
 356
 357 <hr>
 358 <pre>
 359 std::pair&lt;vertex_descriptor, bool&gt; find_vertex(vertex_descriptor u_global) const
 360 </pre>
 361     If vertex <i>u</i> is in this subgraph, the function returns the local
 362     vertex descriptor that corresponds to the global vertex descriptor
 363     <tt>u_global</tt> as the first part of the pair and <tt>true</tt> for
 364     the second part of the pair. If vertex <i>u</i> is not in the subgraph
 365     then this function returns false in the second part of the
 366     pair.
 367
 368 <hr>
 369 <pre>
 370 subgraph& root()
 371 </pre>
 372     Returns the root graph of the subgraph tree.
 373
 374 <hr>
 375 <pre>
 376 bool is_root() const
 377 </pre>
 378     Return <tt>true</tt> if the graph is the root of the subgraph tree,
 379     and returns <tt>false</tt> otherwise.
 380
 381 <hr>
 382 <pre>
 383 subgraph& parent()
 384 </pre>
 385     Returns the parent graph.
 386
 387 <hr>
 388 <pre>
 389 std::pair&lt;children_iterator, children_iterator&gt; children() const
 390 </pre>
 391 Return an iterator pair for accessing the children subgraphs.
 392
 393
 394 <!----------------------------->
 395 <h3>Nonmember Functions</h3>
 396
 397 The functionality of <tt>subgraph</tt> depends on the
 398 <tt>Graph</tt> type. For example, if <tt>Graph</tt> in a
 399 <a href="BidirectionalGraph.html">BidirectionalGraph</a> and supports <tt>in_edges</tt>, then so
 400 does <tt>subgraph</tt>. Here we list all the functions that
 401 <tt>subgraph</tt> could possibly support given a <tt>Graph</tt>
 402 type that is a model of <a href="VertexListGraph.html">VertexListGraph</a>, <a href="EdgeListGraph.html">EdgeListGraph</a> and
 403 <a href="BidirectionalGraph.html">BidirectionalGraph</a>. If the <tt>Graph</tt> type that you use
 404 with <tt>subgraph</tt> does not model these concepts and supports
 405 fewer functions, then the <tt>subgraph</tt> will also support
 406 fewer functions and some of the functions listed below will not be
 407 implemented.
 408
 409
 410 <hr>
 411 <pre>
 412 std::pair&lt;vertex_iterator, vertex_iterator&gt;
 413 vertices(const subgraph&amp; g)
 414 </pre>
 415     Returns an iterator range providing access to the vertex set of subgraph <i>g</i>.
 416     (Required by <a href="VertexListGraph.html">VertexListGraph</a>.)
 417
 418 <hr>
 419 <pre>
 420 std::pair&lt;edge_iterator, edge_iterator&gt;
 421 edges(const subgraph&amp; g)
 422 </pre>
 423     Returns an iterator range providing access to the edge set of subgraph <i>g</i>.
 424     (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.)
 425
 426 <hr>
 427 <pre>
 428 std::pair&lt;adjacency_iterator, adjacency_iterator&gt;
 429 adjacent_vertices(vertex_descriptor u_local, const subgraph&amp; g)
 430 </pre>
 431     Returns an iterator range providing access to the vertices
 432     adjacent to
 433     vertex <i>u</i> in subgraph <i>g</i>.
 434     (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.)
 435
 436 <hr>
 437 <pre>
 438 std::pair&lt;out_edge_iterator, out_edge_iterator&gt;
 439 out_edges(vertex_descriptor u_local, const subgraph&amp; g)
 440 </pre>
 441     Returns an iterator range providing access to the out-edges of
 442     vertex <i>u</i> in subgraph <i>g</i>. If the graph is undirected, this
 443     iterator range provides access to all edge incident on
 444     vertex <i>u</i>.
 445     (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)
 446
 447 <hr>
 448 <pre>
 449 std::pair&lt;in_edge_iterator, in_edge_iterator&gt;
 450 in_edges(vertex_descriptor v_local, const subgraph&amp; g)
 451 </pre>
 452     Returns an iterator range providing access to the in-edges of
 453     vertex
 454     <i>v</i> in subgraph <i>g</i>.
 455     (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.)
 456
 457 <hr>
 458 <pre>
 459 vertex_descriptor
 460 source(edge_descriptor e_local, const subgraph&amp; g)
 461 </pre>
 462     Returns the source vertex of edge <i>e</i> in subgraph <i>g</i>.
 463     (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)
 464
 465 <hr>
 466 <pre>
 467 vertex_descriptor
 468 target(edge_descriptor e_local, const subgraph&amp; g)
 469 </pre>
 470     Returns the target vertex of edge <i>e</i> in subgraph <i>g</i>.
 471     (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)
 472
 473 <hr>
 474 <pre>
 475 degree_size_type
 476 out_degree(vertex_descriptor u_local, const subgraph&amp; g)
 477 </pre>
 478     Returns the number of edges leaving vertex <i>u</i> in subgraph <i>g</i>.
 479     (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.)
 480
 481 <hr>
 482 <pre>
 483 degree_size_type in_degree(vertex_descriptor u_local, const subgraph&amp; g)
 484 </pre>
 485     Returns the number of edges entering vertex <i>u</i> in subgraph <i>g</i>.
 486     (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.)
 487
 488 <hr>
 489 <pre>
 490 vertices_size_type num_vertices(const subgraph&amp; g)
 491 </pre>
 492     Returns the number of vertices in the subgraph <i>g</i>.
 493     (Required by <a href="VertexListGraph.html">VertexListGraph</a>.)
 494
 495 <hr>
 496 <pre>
 497 edges_size_type num_edges(const subgraph&amp; g)
 498 </pre>
 499     Returns the number of edges in the subgraph <i>g</i>.  (Required by
 500     <a href="EdgeListGraph.html">EdgeListGraph</a>.)
 501
 502 <hr>
 503 <pre>
 504 vertex_descriptor vertex(vertices_size_type n, const subgraph&amp; g)
 505 </pre>
 506     Returns the <i>n</i>th vertex in the subgraph's vertex list.
 507
 508 <hr>
 509 <pre>
 510 std::pair&lt;edge_descriptor, bool&gt;
 511 edge(vertex_descriptor u_local, vertex_descriptor v_local, const subgraph&amp; g)
 512 </pre>
 513     Returns the edge connecting vertex <i>u</i> to vertex <i>v</i> in subgraph <i>g</i>.
 514     (Required by <a href="AdjacencyMatrix.html">AdjacencyMatrix</a>.)
 515
 516
 517
 518 <hr>
 519 <pre>
 520 std::pair&lt;edge_descriptor, bool&gt;
 521 add_edge(vertex_descriptor u_local, vertex_descriptor v_local, subgraph&amp; g)
 522 </pre>
 523     Adds edge <i>(u,v)</i> to the subgraph <i>g</i> and to all of the subgraph's
 524     ancestors in the subgraph tree. This function returns the edge
 525     descriptor for the new edge. If the edge is already in the graph
 526     then a duplicate will not be added and the Boolean flag will be
 527     false.
 528     (Required by <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>.)
 529
 530 <hr>
 531 <pre>
 532 std::pair&lt;edge_descriptor, bool&gt;
 533 add_edge(vertex_descriptor u_local, vertex_descriptor v_local,
 534          const EdgeProperty&amp; p, subgraph&amp; g)
 535 </pre>
 536     Adds edge <i>(u,v)</i> to the graph and attaches <tt>p</tt> as the value
 537     of the edge's internal property storage.  Also see the previous
 538     <tt>add_edge</tt> member function for more details.
 539
 540 <hr>
 541 <pre>
 542 void remove_edge(vertex_descriptor u_local, vertex_descriptor v_local,
 543                  subgraph&amp; g)
 544 </pre>
 545     Removes the edge <i>(u,v)</i> from the subgraph and from all of the
 546     ancestors of <tt>g</tt> in the subgraph tree.
 547     (Required by <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>.)
 548
 549 <hr>
 550 <pre>
 551 void remove_edge(edge_descriptor e_local, subgraph&amp; g)
 552 </pre>
 553     Removes the edge <tt>e</tt> from the subgraph and from all of the
 554     ancestors of <tt>g</tt> in the subgraph tree.
 555     (Required by <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>.)
 556
 557 <hr>
 558 <pre>
 559 vertex_descriptor
 560 add_vertex(subgraph&amp; g)
 561 </pre>
 562     Adds a vertex to the subgraph and returns the vertex descriptor
 563     for the new vertex. The vertex is also added to all ancestors of
 564     <tt>g</tt> in the subgraph tree to maintain the subgraph property.
 565     (Required by <a href="VertexMutableGraph.html">VertexMutableGraph</a>.)
 566
 567 <hr>
 568 <pre>
 569 vertex_descriptor
 570 add_vertex(vertex_descriptor u_global, subgraph&amp; g)
 571 </pre>
 572 Adds the vertex <i>u</i> from the root graph to the subgraph <tt>g</tt>.
 573 (Required by <a href="VertexMutableGraph.html">VertexMutableGraph</a>.)
 574
 575
 576 <hr>
 577 <pre>
 578 template &lt;class PropertyTag&gt;
 579 property_map&lt;subgraph, PropertyTag&gt;::type
 580 get(PropertyTag, subgraph&amp; g)
 581
 582 template &lt;class PropertyTag&gt;
 583 property_map&lt;subgraph, PropertyTag&gt;::const_type
 584 get(PropertyTag, const subgraph&amp; g)
 585 </pre>
 586     Returns the property map object for the vertex or edge property
 587     specified by <tt>PropertyTag</tt>. The <tt>PropertyTag</tt> must match one
 588     of the properties specified in the graph's <tt>PropertyTag</tt>
 589     template argument.  Vertex and edge properties are shared by all
 590     subgraphs, so changes to a property through a local vertex
 591     descriptor for one subgraph will change the property for the
 592     global vertex descriptor, and therefore for all other subgraphs.
 593     However, the key type for a subgraph's property map is a subgraph-local
 594     vertex or  edge descriptor.
 595     (Required by <a href="PropertyGraph.html">PropertyGraph</a>.)
 596
 597 <hr>
 598 <pre>
 599 template &lt;class PropertyTag, class Key&gt;
 600 typename property_traits&lt;
 601   typename property_map&lt;subgraph, PropertyTag&gt;::const_type
 602 &gt;::value_type
 603 get(PropertyTag, const subgraph&amp; g, Key k_local)
 604 </pre>
 605     This returns the property value for the key <tt>k_local</tt>, which
 606     is either a local vertex or local edge descriptor. See the above
 607     <tt>get</tt> function
 608     for more information about the propert maps.
 609     (Required by <a href="PropertyGraph.html">PropertyGraph</a>.)
 610
 611 <hr>
 612 <pre>
 613 template &lt;class PropertyTag, class Key, class Value&gt;
 614 void
 615 put(PropertyTag, const subgraph&amp; g, Key k_local, const Value& value)
 616 </pre>
 617     This sets the property value for the key <tt>k_local</tt> to
 618     <tt>value</tt>.  <tt>k_local</tt> is either a local vertex or local
 619     edge descriptor.  <tt>Value</tt> must be convertible to
 620     <tt>typename
 621       property_traits&lt;property_map&lt;adjacency_matrix,
 622       PropertyTag&gt;::type&gt;::value_type</tt>.
 623     (Required by <a href="PropertyGraph.html">PropertyGraph</a>.)
 624
 625 <hr>
 626 <pre>
 627 template &lt;class GraphProperties, class GraphPropertyTag&gt;
 628 typename property_value&lt;GraphProperties, GraphPropertyTag&gt;::type&amp;
 629 get_property(subgraph&amp; g, GraphPropertyTag);
 630 </pre>
 631 Return the property specified by <tt>GraphPropertyTag</tt> that is attached
 632 to the subgraph object <tt>g</tt>. The <tt>property_value</tt> traits class
 633 is defined in <tt>boost/pending/property.hpp</tt>.
 634
 635
 636 <hr>
 637 <pre>
 638 template &lt;class GraphProperties, class GraphPropertyTag&gt;
 639 const typename property_value&lt;GraphProperties, GraphPropertyTag&gt;::type&amp;
 640 get_property(const subgraph&amp; g, GraphPropertyTag);
 641 </pre>
 642 Return the property specified by <tt>GraphPropertyTag</tt> that is
 643 attached to the subgraph object <tt>g</tt>.  The <tt>property_value</tt>
 644 traits class is defined in <tt>boost/pending/property.hpp</tt>.
 645
 646 <hr>
 647 <h2>Notes</h2>
 648 The subgraph template requires the underlying graph type to supply vertex and
 649 edge index properties. However, there is no default constructor of any adjacency
 650 list that satisfies both of these requirements. This is especially true of graphs
 651 using <a href="bundles.html">bundled properties</a>, or any adjacency list whose
 652 vertex set is selected by anything other that <tt>vecS</tt>.
 653
 654 However, this problem can be overcome by embedding your bundled (or otherwise)
 655 properties into a <tt>property</tt> that contains an appropriate index. For
 656 example:
 657 <pre>
 658 struct my_vertex { ... };
 659 typedef property&lt;vertex_index_t, std::size_t, my_vertex&gt; vertex_prop;
 660
 661 struct my_edge { ... };
 662 typedef property&lt;edge_index_t, std::size_t, my_edge&gt; edge_prop;
 663
 664 typedef adjacency_list&lt;vecS, listS, undirectedS, vertex_prop, edge_prop&gt; Graph;
 665 typedef subgraph&lt;Graph&gt; Subgraph;
 666 </pre>