...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

subgraph<Graph>

The subgraph class provides a mechanism for keeping track of a graph
and its subgraphs. A graph *G'* is a *subgraph* of a graph
*G* if the vertex set of *G'* is a subset of the vertex set
of *G* and if the edge set of *G'* is a subset of the edge
set of *G*. That is, if *G'=(V',E')* and *G=(V,E)*,
then *G'* is a subgraph of *G* if *V'* is a subset of
*V* and *E* is a subset of *E'*. An *induced
subgraph* is a subgraph formed by specifying a set of vertices
*V'* and then selecting all of the edges from the original graph
that connect two vertices in *V'*. So in this case *E' = {(u,v)
in E: u,v in V'}*. Figure 1 shows a graph *G _{0}* and
two subgraphs

The `subgraph` class implements induced subgraphs. The main graph
and its subgraphs are maintained in a tree data structure. The main
graph is the root, and subgraphs are either children of the root or of
other subgraphs. All of the nodes in this tree, including the root
graph, are instances of the `subgraph` class. The
`subgraph` implementation ensures that each node in the tree is
an induced subgraph of its parent. The `subgraph` class
implements the BGL graph interface, so each subgraph object can be
treated as a graph.

typedef adjacency_list_traits< vecS, vecS, directedS > Traits; typedef subgraph< adjacency_list< vecS, vecS, directedS, no_property, property< edge_index_t, int > > > Graph; const int N = 6; Graph G0(N); enum { A, B, C, D, E, F}; // for conveniently referring to vertices in G0Next we create two empty subgraph objects, specifying

Graph& G1 = G0.create_subgraph(), G2 = G0.create_subgraph(); enum { A1, B1, C1 }; // for conveniently referring to vertices in G1 enum { A2, B2 }; // for conveniently referring to vertices in G2We can add vertices from the root graph to the subgraphs using the

add_vertex(C, G1); // global vertex C becomes local A1 for G1 add_vertex(E, G1); // global vertex E becomes local B1 for G1 add_vertex(F, G1); // global vertex F becomes local C1 for G1 add_vertex(A, G2); // global vertex A becomes local A2 for G2 add_vertex(B, G2); // global vertex B becomes local B2 for G2Next we can add edges to the main graph using the usual

add_edge(A, B, G0); add_edge(B, C, G0); add_edge(B, D, G0); add_edge(E, B, G0); add_edge(E, F, G0); add_edge(F, D, G0);We can also add edges to subgraphs such as

add_edge(A1, C1, G1); // (A1,C1) is subgraph G1 local indices // for the global edge (C,F).

Parameter | Description |
---|---|

Graph |
A graph type modeling VertexMutableGraph
and EdgeMutableGraph. Also
the graph must have internal vertex_index and
edge_index properties. The vertex indices must be maintained
automatically by the graph, whereas the edge indices will be
assigned by the subgraph class implementation. |

graph_traits<subgraph>::vertex_descriptorThe type for the vertex descriptors. (Required by Graph.)

graph_traits<subgraph>::edge_descriptorThe type for the edge descriptors. (Required by Graph.)

graph_traits<subgraph>::vertex_iteratorThe type for the iterators returned by

graph_traits<subgraph>::edge_iteratorThe type for the iterators returned by

graph_traits<subgraph>::out_edge_iteratorThe type for the iterators returned by

graph_traits<subgraph>::in_edge_iteratorThe

graph_traits<subgraph>::adjacency_iteratorThe type for the iterators returned by

graph_traits<subgraph>::directed_categoryProvides information about whether the graph is directed (

graph_traits<subgraph>::edge_parallel_categoryThis describes whether the graph class allows the insertion of parallel edges (edges with the same source and target), which depends on the underlying

graph_traits<subgraph>::vertices_size_typeThe type used for dealing with the number of vertices in the graph. (Required by VertexListGraph.)

graph_traits<subgraph>::edges_size_typeThe type used for dealing with the number of edges in the graph. (Required by EdgeListGraph.)

graph_traits<subgraph>::degree_size_typeThe type used for dealing with the number of out-edges of a vertex. (Required by IncidenceGraph.)

property_map<subgraph, PropertyTag>::type property_map<subgraph, PropertyTag>::const_typeThe map type for vertex or edge properties in the graph. The specific property is specified by the

subgraph::children_iteratorThe iterator type for accessing the children subgraphs of the graph.

subgraph(vertices_size_type n, const GraphProperty& p = GraphProperty())Creates the root graph object with

subgraph<Graph>& create_subgraph();Creates an empty subgraph object whose parent is

template <typename VertexIterator> subgraph<Graph>& create_subgraph(VertexIterator first, VertexIterator last)Creates a subgraph object with the specified vertex set. The edges of the subgraph are induced by the vertex set. That is, every edge in the parent graph (which is

vertex_descriptor local_to_global(vertex_descriptor u_local) constConverts a local vertex descriptor to the corresponding global vertex descriptor.

vertex_descriptor global_to_local(vertex_descriptor u_global) constConverts a global vertex descriptor to the corresponding local vertex descriptor.

edge_descriptor local_to_global(edge_descriptor e_local) constConverts a local edge descriptor to the corresponding global edge descriptor.

edge_descriptor global_to_local(edge_descriptor u_global) constConverts a global edge descriptor to the corresponding local edge descriptor.

std::pair<vertex_descriptor, bool> find_vertex(vertex_descriptor u_global) constIf vertex

subgraph& root()Returns the root graph of the subgraph tree.

bool is_root() constReturn

subgraph& parent()Returns the parent graph.

std::pair<children_iterator, children_iterator> children() constReturn an iterator pair for accessing the children subgraphs.

std::pair<vertex_iterator, vertex_iterator> vertices(const subgraph& g)Returns an iterator range providing access to the vertex set of subgraph

std::pair<edge_iterator, edge_iterator> edges(const subgraph& g)Returns an iterator range providing access to the edge set of subgraph

std::pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor u_local, const subgraph& g)Returns an iterator range providing access to the vertices adjacent to vertex

std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor u_local, const subgraph& g)Returns an iterator range providing access to the out-edges of vertex

std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v_local, const subgraph& g)Returns an iterator range providing access to the in-edges of vertex

vertex_descriptor source(edge_descriptor e_local, const subgraph& g)Returns the source vertex of edge

vertex_descriptor target(edge_descriptor e_local, const subgraph& g)Returns the target vertex of edge

degree_size_type out_degree(vertex_descriptor u_local, const subgraph& g)Returns the number of edges leaving vertex

degree_size_type in_degree(vertex_descriptor u_local, const subgraph& g)Returns the number of edges entering vertex

vertices_size_type num_vertices(const subgraph& g)Returns the number of vertices in the subgraph

edges_size_type num_edges(const subgraph& g)Returns the number of edges in the subgraph

vertex_descriptor vertex(vertices_size_type n, const subgraph& g)Returns the

std::pair<edge_descriptor, bool> edge(vertex_descriptor u_local, vertex_descriptor v_local, const subgraph& g)Returns the edge connecting vertex

std::pair<edge_descriptor, bool> add_edge(vertex_descriptor u_local, vertex_descriptor v_local, subgraph& g)Adds edge

std::pair<edge_descriptor, bool> add_edge(vertex_descriptor u_local, vertex_descriptor v_local, const EdgeProperty& p, subgraph& g)Adds edge

void remove_edge(vertex_descriptor u_local, vertex_descriptor v_local, subgraph& g)Removes the edge

void remove_edge(edge_descriptor e_local, subgraph& g)Removes the edge

vertex_descriptor add_vertex(subgraph& g)Adds a vertex to the subgraph and returns the vertex descriptor for the new vertex. The vertex is also added to all ancestors of

vertex_descriptor add_vertex(vertex_descriptor u_global, subgraph& g)Adds the vertex

template <class PropertyTag> property_map<subgraph, PropertyTag>::type get(PropertyTag, subgraph& g) template <class PropertyTag> property_map<subgraph, PropertyTag>::const_type get(PropertyTag, const subgraph& g)Returns the property map object for the vertex or edge property specified by

template <class PropertyTag, class Key> typename property_traits< typename property_map<subgraph, PropertyTag>::const_type >::value_type get(PropertyTag, const subgraph& g, Key k_local)This returns the property value for the key

template <class PropertyTag, class Key, class Value> void put(PropertyTag, const subgraph& g, Key k_local, const Value& value)This sets the property value for the key

template <class GraphProperties, class GraphPropertyTag> typename property_value<GraphProperties, GraphPropertyTag>::type& get_property(subgraph& g, GraphPropertyTag);Return the property specified by

template <class GraphProperties, class GraphPropertyTag> const typename property_value<GraphProperties, GraphPropertyTag>::type& get_property(const subgraph& g, GraphPropertyTag);Return the property specified by

struct my_vertex { ... }; typedef property<vertex_index_t, std::size_t, my_vertex> vertex_prop; struct my_edge { ... }; typedef property<edge_index_t, std::size_t, my_edge> edge_prop; typedef adjacency_list<vecS, listS, undirectedS, vertex_prop, edge_prop> Graph; typedef subgraph<Graph> Subgraph;