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 G0 and
two subgraphs G1 and G2. The edge
set for G1 is E1 = { (E,F), (C,F)
} and the edge set for G2 is E2 =
{ (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 Traits;
typedef subgraph< adjacency_list > > 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. |
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.
Associates 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.
|