3 Copyright (c) Jeremy Siek 2000
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)
10 <Title>Boost Graph Library: Subgraph
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><A NAME=
"sec:subgraph-class"></A>
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). -->
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.
48 <DIV ALIGN=
"center"><A NAME=
"fig:subgraph-tree"></A>
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>
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>
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.
79 typedef adjacency_list_traits
< vecS, vecS, directedS
> Traits;
80 typedef subgraph
< adjacency_list
< vecS, vecS, directedS,
81 no_property, property
< edge_index_t, int
> > > Graph;
86 enum { A, B, C, D, E, F}; // for conveniently refering to vertices in G0
89 Next we create two empty subgraph objects, specifying
<tt>G0
</tt> as
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
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
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
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
113 Next we can add edges to the main graph using the usual
114 <tt>add_edge
</tt> function.
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.
139 add_edge(A1, C1, G1); // (A1,C1) is subgraph G1 local indices
140 // for the global edge (C,F).
143 <!----------------------------->
144 <h3>Where Defined
</h3>
146 <tt>boost/graph/subgraph.hpp
</tt>
148 <!----------------------------->
149 <h3>Template Parameters
</h3>
154 <th>Parameter
</th><th>Description
</th>
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>
167 <!----------------------------->
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
<Graph
></tt> will also models these concepts.
175 <!----------------------------->
176 <h3>Associated Types
</h3>
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.
188 graph_traits
<subgraph
>::vertex_descriptor
190 The type for the vertex descriptors.
191 (Required by
<a href=
"Graph.html">Graph
</a>.)
196 graph_traits
<subgraph
>::edge_descriptor
198 The type for the edge descriptors.
199 (Required by
<a href=
"Graph.html">Graph
</a>.)
204 graph_traits
<subgraph
>::vertex_iterator
206 The type for the iterators returned by
<tt>vertices
</tt>.
207 (Required by
<a href=
"VertexListGraph.html">VertexListGraph
</a>.)
212 graph_traits
<subgraph
>::edge_iterator
214 The type for the iterators returned by
<tt>edges
</tt>.
215 (Required by
<a href=
"EdgeListGraph.html">EdgeListGraph
</a>.)
219 graph_traits
<subgraph
>::out_edge_iterator
221 The type for the iterators returned by
<tt>out_edges
</tt>.
222 (Required by
<a href=
"IncidenceGraph.html">IncidenceGraph
</a>.)
226 graph_traits
<subgraph
>::in_edge_iterator
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>.)
234 graph_traits
<subgraph
>::adjacency_iterator
236 The type for the iterators returned by
<tt>adjacent_vertices
</tt>.
237 (Required by
<a href=
"AdjacencyGraph.html">AdjacencyGraph
</a>.)
241 graph_traits
<subgraph
>::directed_category
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>.)
249 graph_traits
<subgraph
>::edge_parallel_category
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>.)
260 graph_traits
<subgraph
>::vertices_size_type
262 The type used for dealing with the number of vertices in
264 (Required by
<a href=
"VertexListGraph.html">VertexListGraph
</a>.)
268 graph_traits
<subgraph
>::edges_size_type
270 The type used for dealing with the number of edges in the graph.
271 (Required by
<a href=
"EdgeListGraph.html">EdgeListGraph
</a>.)
275 graph_traits
<subgraph
>::degree_size_type
277 The type used for dealing with the number of out-edges of a vertex.
278 (Required by
<a href=
"IncidenceGraph.html">IncidenceGraph
</a>.)
282 property_map
<subgraph, PropertyTag
>::type
283 property_map
<subgraph, PropertyTag
>::const_type
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>.)
293 subgraph::children_iterator
295 The iterator type for accessing the children subgraphs of the graph.
299 <!----------------------------->
300 <h3>Member Functions
</h3>
306 subgraph(vertices_size_type n, const GraphProperty
& p = GraphProperty())
308 Creates the root graph object with
<tt>n
</tt> vertices and zero edges.
312 subgraph
<Graph
>& create_subgraph();
314 Creates an empty subgraph object whose parent is
<i>this
</i>
319 template
<typename VertexIterator
>
320 subgraph
<Graph
>&
321 create_subgraph(VertexIterator first, VertexIterator last)
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
331 vertex_descriptor local_to_global(vertex_descriptor u_local) const
333 Converts a local vertex descriptor to the corresponding global
338 vertex_descriptor global_to_local(vertex_descriptor u_global) const
340 Converts a global vertex descriptor to the corresponding local
345 edge_descriptor local_to_global(edge_descriptor e_local) const
347 Converts a local edge descriptor to the corresponding global edge
352 edge_descriptor global_to_local(edge_descriptor u_global) const
354 Converts a global edge descriptor to the corresponding local edge
359 std::pair
<vertex_descriptor, bool
> find_vertex(vertex_descriptor u_global) const
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
372 Returns the root graph of the subgraph tree.
378 Return
<tt>true
</tt> if the graph is the root of the subgraph tree,
379 and returns
<tt>false
</tt> otherwise.
385 Returns the parent graph.
389 std::pair
<children_iterator, children_iterator
> children() const
391 Return an iterator pair for accessing the children subgraphs.
394 <!----------------------------->
395 <h3>Nonmember Functions
</h3>
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
412 std::pair
<vertex_iterator, vertex_iterator
>
413 vertices(const subgraph
& g)
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>.)
420 std::pair
<edge_iterator, edge_iterator
>
421 edges(const subgraph
& g)
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>.)
428 std::pair
<adjacency_iterator, adjacency_iterator
>
429 adjacent_vertices(vertex_descriptor u_local, const subgraph
& g)
431 Returns an iterator range providing access to the vertices
433 vertex
<i>u
</i> in subgraph
<i>g
</i>.
434 (Required by
<a href=
"AdjacencyGraph.html">AdjacencyGraph
</a>.)
438 std::pair
<out_edge_iterator, out_edge_iterator
>
439 out_edges(vertex_descriptor u_local, const subgraph
& g)
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
445 (Required by
<a href=
"IncidenceGraph.html">IncidenceGraph
</a>.)
449 std::pair
<in_edge_iterator, in_edge_iterator
>
450 in_edges(vertex_descriptor v_local, const subgraph
& g)
452 Returns an iterator range providing access to the in-edges of
454 <i>v
</i> in subgraph
<i>g
</i>.
455 (Required by
<a href=
"BidirectionalGraph.html">BidirectionalGraph
</a>.)
460 source(edge_descriptor e_local, const subgraph
& g)
462 Returns the source vertex of edge
<i>e
</i> in subgraph
<i>g
</i>.
463 (Required by
<a href=
"IncidenceGraph.html">IncidenceGraph
</a>.)
468 target(edge_descriptor e_local, const subgraph
& g)
470 Returns the target vertex of edge
<i>e
</i> in subgraph
<i>g
</i>.
471 (Required by
<a href=
"IncidenceGraph.html">IncidenceGraph
</a>.)
476 out_degree(vertex_descriptor u_local, const subgraph
& g)
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>.)
483 degree_size_type in_degree(vertex_descriptor u_local, const subgraph
& g)
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>.)
490 vertices_size_type num_vertices(const subgraph
& g)
492 Returns the number of vertices in the subgraph
<i>g
</i>.
493 (Required by
<a href=
"VertexListGraph.html">VertexListGraph
</a>.)
497 edges_size_type num_edges(const subgraph
& g)
499 Returns the number of edges in the subgraph
<i>g
</i>. (Required by
500 <a href=
"EdgeListGraph.html">EdgeListGraph
</a>.)
504 vertex_descriptor vertex(vertices_size_type n, const subgraph
& g)
506 Returns the
<i>n
</i>th vertex in the subgraph's vertex list.
510 std::pair
<edge_descriptor, bool
>
511 edge(vertex_descriptor u_local, vertex_descriptor v_local, const subgraph
& g)
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>.)
520 std::pair
<edge_descriptor, bool
>
521 add_edge(vertex_descriptor u_local, vertex_descriptor v_local, subgraph
& g)
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
528 (Required by
<a href=
"EdgeMutableGraph.html">EdgeMutableGraph
</a>.)
532 std::pair
<edge_descriptor, bool
>
533 add_edge(vertex_descriptor u_local, vertex_descriptor v_local,
534 const EdgeProperty
& p, subgraph
& g)
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.
542 void remove_edge(vertex_descriptor u_local, vertex_descriptor v_local,
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>.)
551 void remove_edge(edge_descriptor e_local, subgraph
& g)
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>.)
560 add_vertex(subgraph
& g)
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>.)
570 add_vertex(vertex_descriptor u_global, subgraph
& g)
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>.)
578 template
<class PropertyTag
>
579 property_map
<subgraph, PropertyTag
>::type
580 get(PropertyTag, subgraph
& g)
582 template
<class PropertyTag
>
583 property_map
<subgraph, PropertyTag
>::const_type
584 get(PropertyTag, const subgraph
& g)
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>.)
599 template
<class PropertyTag, class Key
>
600 typename property_traits
<
601 typename property_map
<subgraph, PropertyTag
>::const_type
603 get(PropertyTag, const subgraph
& g, Key k_local)
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>.)
613 template
<class PropertyTag, class Key, class Value
>
615 put(PropertyTag, const subgraph
& g, Key k_local, const Value& value)
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
621 property_traits
<property_map
<adjacency_matrix,
622 PropertyTag
>::type
>::value_type
</tt>.
623 (Required by
<a href=
"PropertyGraph.html">PropertyGraph
</a>.)
627 template
<class GraphProperties, class GraphPropertyTag
>
628 typename property_value
<GraphProperties, GraphPropertyTag
>::type
&
629 get_property(subgraph
& g, GraphPropertyTag);
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>.
638 template
<class GraphProperties, class GraphPropertyTag
>
639 const typename property_value
<GraphProperties, GraphPropertyTag
>::type
&
640 get_property(const subgraph
& g, GraphPropertyTag);
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>.
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>.
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
658 struct my_vertex { ... };
659 typedef property
<vertex_index_t, std::size_t, my_vertex
> vertex_prop;
661 struct my_edge { ... };
662 typedef property
<edge_index_t, std::size_t, my_edge
> edge_prop;
664 typedef adjacency_list
<vecS, listS, undirectedS, vertex_prop, edge_prop
> Graph;
665 typedef subgraph
<Graph
> Subgraph;