Boost Graph Library: Subgraph

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₀ and two subgraphs G₁ and G₂. The edge set for G₁ is E₁ = { (E,F), (C,F) } and the edge set for G₂ is E₂ = { (A,B) }. Edges such as (E,B) and (F,D) that cross out of a subgraph are not in the edge set of the subgraph.

**Figure 1:** A graph with nested subgraphs, maintained in a tree structure.

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.

Example

The full source code for this example is in example/subgraph.cpp. To create a graph and subgraphs, first create the root graph object. Here we use adjacency_list as the underlying graph implementation. The underlying graph type is required to have vertex_index and edge_index internal properties, so we add an edge index property to the adjacency list. We do not need to add a vertex index properety because that is built in to the adjacency_list. We will be building the graph and subgraphs in Figure 1, so we will need a total of six vertices.

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 refering to vertices in G0

Next we create two empty subgraph objects, specifying G0 as their parent.

Graph& G1 = G0.create_subgraph(), G2 = G0.create_subgraph();
enum { A1, B1, C2 }; // for conveniently refering to vertices in G1
enum { A2, B2 };     // for conveniently refering to vertices in G2

We can add vertices from the root graph to the subgraphs using the add_vertex function. Since the graph implementation is adjacency_list with VertexList=vecS, we can use the integers (or in this case enums) in the range [0,6) as vertex descriptors.

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 G2

Next we can add edges to the main graph using the usual add_edge function.

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 G1 using the add_edge function. Each subgraph has its own vertex and edge descriptors, which we call local descriptors. We refer to root graph's vertex and edge descriptors as the global descriptors. Above, we used global vertex descriptors to add vertices to the graph. However, most subgraph functions work with local descriptors. So in the following call to add_edge we add the edge (A1,C1) (or numerically (0,2)) which is the local version (for subgraph G1) of the global edge (C,F) (or numerically (2,5)). Adding an edge to a subgraph causes the edge to also be added to all of its ancestors in the subgraph tree to ensure that the subgraph property is maintained.

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

Where Defined

boost/graph/subgraph.hpp

Template Parameters

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.

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.

Model Of

subgraph is a model of VertexMutableGraph. Also, if the Graph type models VertexListGraph, EdgeListGraph and/or BidirectionalGraph, then subgraph<Graph> will also models these concepts.

Associated Types

If the graph is the root of the subgraph tree, then the vertex and edge descriptors are both the local descriptors for the root graph, and they are the global descriptors. If the graph is not the root, then the descriptors are local descriptors for the subgraph. The subgraph iterators are the same iterator types as the iterators of the underlying Graph type.

graph_traits<subgraph>::vertex_descriptor

The type for the vertex descriptors. (Required by Graph.)

graph_traits<subgraph>::edge_descriptor

The type for the edge descriptors. (Required by Graph.)

graph_traits<subgraph>::vertex_iterator

The type for the iterators returned by vertices. (Required by VertexListGraph.)

graph_traits<subgraph>::edge_iterator

The type for the iterators returned by edges. (Required by EdgeListGraph.)

graph_traits<subgraph>::out_edge_iterator

The type for the iterators returned by out_edges. (Required by IncidenceGraph.)

graph_traits<subgraph>::in_edge_iterator

The in_edge_iterator is the iterator type returned by the in_edges function. (Required by BidirectionalGraph.)

graph_traits<subgraph>::adjacency_iterator

The type for the iterators returned by adjacent_vertices. (Required by AdjacencyGraph.)

graph_traits<subgraph>::directed_category

Provides information about whether the graph is directed (directed_tag) or undirected (undirected_tag). (Required by Graph.)

graph_traits<subgraph>::edge_parallel_category

This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target), which depends on the underlying Graph class. The two tags are allow_parallel_edge_tag and disallow_parallel_edge_tag. (Required by Graph.)

graph_traits<subgraph>::vertices_size_type

The type used for dealing with the number of vertices in the graph. (Required by VertexListGraph.)

graph_traits<subgraph>::edges_size_type

The type used for dealing with the number of edges in the graph. (Required by EdgeListGraph.)

graph_traits<subgraph>::degree_size_type

The 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_type

The map type for vertex or edge properties in the graph. The specific property is specified by the PropertyTag template argument, and must match one of the properties specified in the VertexProperty or EdgeProperty for the graph. (Required by PropertyGraph.)

subgraph::children_iterator

The iterator type for accessing the children subgraphs of the graph.

Member Functions

subgraph(vertices_size_type n, const GraphProperty& p = GraphProperty())

Creates the root graph object with n vertices and zero edges.

subgraph<Graph>& create_subgraph();

Creates an empty subgraph object whose parent is this graph.

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 this graph) that connects two vertices in the subgraph will be added to the subgraph.

vertex_descriptor local_to_global(vertex_descriptor u_local) const

Converts a local vertex descriptor to the corresponding global vertex descriptor.

vertex_descriptor global_to_local(vertex_descriptor u_global) const

Converts a global vertex descriptor to the corresponding local vertex descriptor.

edge_descriptor local_to_global(edge_descriptor e_local) const

Converts a local edge descriptor to the corresponding global edge descriptor.

edge_descriptor global_to_local(edge_descriptor u_global) const

Converts a global edge descriptor to the corresponding local edge descriptor.

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

If vertex u is in this subgraph, the function returns the local vertex descriptor that corresponds to the global vertex descriptor u_global as the first part of the pair and true for the second part of the pair. If vertex u is not in the subgraph then this function returns false in the second part of the pair.

subgraph& root()

Returns the root graph of the subgraph tree.

bool is_root() const

Return true if the graph is the root of the subgraph tree, and returns false otherwise.

subgraph& parent()

Returns the parent graph.

std::pair<children_iterator, children_iterator> children() const

Return an iterator pair for accessing the children subgraphs.

Nonmember Functions

The functionality of subgraph depends on the Graph type. For example, if Graph in a BidirectionalGraph and supports in_edges, then so does subgraph. Here we list all the functions that subgraph could possibly support given a Graph type that is a model of VertexListGraph, EdgeListGraph and BidirectionalGraph. If the Graph type that you use with subgraph does not model these concepts and supports fewer functions, then the subgraph will also support fewer functions and some of the functions listed below will not be implemented.

std::pair<vertex_iterator, vertex_iterator>
vertices(const subgraph& g)

Returns an iterator range providing access to the vertex set of subgraph g. (Required by VertexListGraph.)

std::pair<edge_iterator, edge_iterator>
edges(const subgraph& g)

Returns an iterator range providing access to the edge set of subgraph g. (Required by EdgeListGraph.)

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 u in subgraph g. (Required by AdjacencyGraph.)

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 u in subgraph g. If the graph is undirected, this iterator range provides access to all edge incident on vertex u. (Required by IncidenceGraph.)

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 v in subgraph g. (Required by BidirectionalGraph.)

vertex_descriptor
source(edge_descriptor e_local, const subgraph& g)

Returns the source vertex of edge e in subgraph g. (Required by IncidenceGraph.)

vertex_descriptor
target(edge_descriptor e_local, const subgraph& g)

Returns the target vertex of edge e in subgraph g. (Required by IncidenceGraph.)

degree_size_type
out_degree(vertex_descriptor u_local, const subgraph& g)

Returns the number of edges leaving vertex u in subgraph g. (Required by IncidenceGraph.)

degree_size_type in_degree(vertex_descriptor u_local, const subgraph& g)

Returns the number of edges entering vertex u in subgraph g. (Required by BidirectionalGraph.)

vertices_size_type num_vertices(const subgraph& g)

Returns the number of vertices in the subgraph g. (Required by VertexListGraph.)

edges_size_type num_edges(const subgraph& g)

Returns the number of edges in the subgraph g. (Required by EdgeListGraph.)

vertex_descriptor vertex(vertices_size_type n, const subgraph& g)

Returns the nth vertex in the subgraph's vertex list.

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

Returns the edge connecting vertex u to vertex v in subgraph g. (Required by AdjacencyMatrix.)

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

Adds edge (u,v) to the subgraph g and to all of the subgraph's ancestors in the subgraph tree. This function returns the edge descriptor for the new edge. If the edge is already in the graph then a duplicate will not be added and the Boolean flag will be false. (Required by EdgeMutableGraph.)

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

Adds edge (u,v) to the graph and attaches p as the value of the edge's internal property storage. Also see the previous add_edge member function for more details.

void remove_edge(vertex_descriptor u_local, vertex_descriptor v_local,
                 subgraph& g)

Removes the edge (u,v) from the subgraph and from all of the ancestors of g in the subgraph tree. (Required by EdgeMutableGraph.)

void remove_edge(edge_descriptor e_local, subgraph& g)

Removes the edge e from the subgraph and from all of the ancestors of g in the subgraph tree. (Required by EdgeMutableGraph.)

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 g in the subgraph tree to maintain the subgraph property. (Required by VertexMutableGraph.)

vertex_descriptor
add_vertex(vertex_descriptor u_global, subgraph& g)

Adds the vertex u from the root graph to the subgraph g. (Required by VertexMutableGraph.)

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 PropertyTag. The PropertyTag must match one of the properties specified in the graph's PropertyTag template argument. Vertex and edge properties are shared by all subgraphs, so changes to a property through a local vertex descriptor for one subgraph will change the property for the global vertex descriptor, and therefore for all other subgraphs. However, the key type for a subgraph's property map is a subgraph-local vertex or edge descriptor. (Required by PropertyGraph.)

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 k_local, which is either a local vertex or local edge descriptor. See the above get function for more information about the propert maps. (Required by PropertyGraph.)

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 k_local to value. k_local is either a local vertex or local edge descriptor. Value must be convertible to typename property_traits<property_map<adjacency_matrix, PropertyTag>::type>::value_type. (Required by PropertyGraph.)

template <class GraphProperties, class GraphPropertyTag>
typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(subgraph& g, GraphPropertyTag);

Return the property specified by GraphPropertyTag that is attached to the subgraph object g. The property_value traits class is defined in boost/pending/property.hpp.

template <class GraphProperties, class GraphPropertyTag>
const typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(const subgraph& g, GraphPropertyTag);

Return the property specified by GraphPropertyTag that is attached to the subgraph object g. The property_value traits class is defined in boost/pending/property.hpp.

Notes

The subgraph template requires the underlying graph type to supply vertex and edge index properties. However, there is no default constructor of any adjacency list that satisfies both of these requirements. This is especially true of graphs using bundled properties, or any adjacency list whose vertex set is selected by anything other that vecS. However, this problem can be overcome by embedding your bundled (or otherwise) properties into a property that contains an appropriate index. For example:

struct my_vertex { ... };
typedef property<vertex_index_t, std::size_t, vertex_prop> vertex_prop;

struct my_edge { ... };
typedef property<edge_index_t, std::size_t, vertex_prop> edge_prop;

typedef adjacency_list<vecS, listS, undirectedS, vertex_prop, edge_prop> Graph;
typdef subgraph<Graph> Subgraph;