| <HTML> |
| <!-- |
| Copyright (c) Jeremy Siek 2000 |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| --> |
| <Head> |
| <Title>Boost Graph Library: Subgraph</Title> |
| <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
| ALINK="#ff0000"> |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| |
| <BR Clear> |
| |
| <H1><A NAME="sec:subgraph-class"></A> |
| <pre> |
| subgraph<Graph> |
| </pre> |
| </h1> |
| |
| <!--The space consumption of the <tt>subgraph</tt> is quite high. |
| We should change subgraph from representing induced subgraphs to just |
| normal subgraphs (from talk with Steven North). --> |
| |
| <p> |
| The subgraph class provides a mechanism for keeping track of a graph |
| and its subgraphs. A graph <i>G'</i> is a <i>subgraph</i> of a graph |
| <i>G</i> if the vertex set of <i>G'</i> is a subset of the vertex set |
| of <i>G</i> and if the edge set of <i>G'</i> is a subset of the edge |
| set of <i>G</i>. That is, if <i>G'=(V',E')</i> and <i>G=(V,E)</i>, |
| then <i>G'</i> is a subgraph of <i>G</i> if <i>V'</i> is a subset of |
| <i>V</i> and <i>E</i> is a subset of <i>E'</i>. An <i>induced |
| subgraph</i> is a subgraph formed by specifying a set of vertices |
| <i>V'</i> and then selecting all of the edges from the original graph |
| that connect two vertices in <i>V'</i>. So in this case <i>E' = {(u,v) |
| in E: u,v in V'}</i>. Figure 1 shows a graph <i>G<sub>0</sub></i> and |
| two subgraphs <i>G<sub>1</sub></i> and <i>G<sub>2</sub></i>. The edge |
| set for <i>G<sub>1</sub></i> is <i>E<sub>1</sub> = { (E,F), (C,F) |
| }</i> and the edge set for <i>G<sub>2</sub></i> is <i>E<sub>2</sub> = |
| { (A,B) }</i>. Edges such as <i>(E,B)</i> and <i>(F,D)</i> that cross |
| out of a subgraph are not in the edge set of the subgraph. |
| </p> |
| |
| <P></P> |
| <DIV ALIGN="center"><A NAME="fig:subgraph-tree"></A> |
| <TABLE> |
| <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> A graph with nested subgraphs, maintained in a tree structure.</CAPTION> |
| <TR><TD><IMG SRC="./figs/subgraph.gif"></TD> |
| <TD><IMG SRC="./figs/subgraph-tree.gif"></TD></TR> |
| </TABLE> |
| </DIV><P></P> |
| |
| <p>The <tt>subgraph</tt> 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 <tt>subgraph</tt> class. The |
| <tt>subgraph</tt> implementation ensures that each node in the tree is |
| an induced subgraph of its parent. The <tt>subgraph</tt> class |
| implements the BGL graph interface, so each subgraph object can be |
| treated as a graph.</p> |
| |
| <h3>Example</h3> |
| |
| The full source code for this example is in |
| <tt>example/subgraph.cpp</tt>. To create a graph and subgraphs, first |
| create the root graph object. Here we use <tt>adjacency_list</tt> as |
| the underlying graph implementation. The underlying graph type is |
| required to have <tt>vertex_index</tt> and <tt>edge_index</tt> |
| 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 <tt>adjacency_list</tt>. We will be building the graph |
| and subgraphs in Figure 1, so we will need a total of six vertices. |
| |
| <pre> |
| 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 |
| </pre> |
| |
| Next we create two empty subgraph objects, specifying <tt>G0</tt> as |
| their parent. |
| |
| <pre> |
| 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 |
| </pre> |
| |
| We can add vertices from the root graph to the subgraphs using the |
| <tt>add_vertex</tt> function. Since the graph implementation is |
| <tt>adjacency_list</tt> with <tt>VertexList=vecS</tt>, we can use the |
| integers (or in this case enums) in the range <i>[0,6)</i> as vertex |
| descriptors. |
| |
| <pre> |
| 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 |
| </pre> |
| |
| Next we can add edges to the main graph using the usual |
| <tt>add_edge</tt> function. |
| |
| <pre> |
| 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); |
| </pre> |
| |
| We can also add edges to subgraphs such as <tt>G1</tt> using the |
| <tt>add_edge</tt> function. Each subgraph has its own vertex and edge |
| descriptors, which we call <i>local</i> descriptors. We refer to root |
| graph's vertex and edge descriptors as the <i>global</i> |
| descriptors. Above, we used global vertex descriptors to add vertices |
| to the graph. However, most <tt>subgraph</tt> functions work with |
| local descriptors. So in the following call to <tt>add_edge</tt> we |
| add the edge <tt>(A1,C1)</tt> (or numerically <tt>(0,2)</tt>) which is |
| the local version (for subgraph <tt>G1</tt>) of the global edge |
| <tt>(C,F)</tt> (or numerically <tt>(2,5)</tt>). 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. |
| |
| <pre> |
| add_edge(A1, C1, G1); // (A1,C1) is subgraph G1 local indices |
| // for the global edge (C,F). |
| </pre> |
| |
| <!-----------------------------> |
| <h3>Where Defined</h3> |
| |
| <tt>boost/graph/subgraph.hpp</tt> |
| |
| <!-----------------------------> |
| <h3>Template Parameters</h3> |
| |
| <P> |
| <TABLE border> |
| <TR> |
| <th>Parameter</th><th>Description</th> |
| </tr> |
| <tr><td><tt>Graph</tt> </td> |
| <td> A graph type modeling <a href="VertexMutableGraph.html">VertexMutableGraph</a> |
| and <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>. Also |
| the graph must have internal <tt>vertex_index</tt> and |
| <tt>edge_index</tt> properties. The vertex indices must be maintained |
| automatically by the graph, whereas the edge indices will be |
| assigned by the <tt>subgraph</tt> class implementation. </td> |
| </tr> |
| </table> |
| |
| |
| <!-----------------------------> |
| <h3>Model Of</h3> |
| |
| <tt>subgraph</tt> is a model of <a href="VertexMutableGraph.html">VertexMutableGraph</a>. Also, if |
| the <tt>Graph</tt> type models <a href="VertexListGraph.html">VertexListGraph</a>, |
| <a href="EdgeListGraph.html">EdgeListGraph</a> and/or <a href="BidirectionalGraph.html">BidirectionalGraph</a>, then |
| <tt>subgraph<Graph></tt> will also models these concepts. |
| |
| <!-----------------------------> |
| <h3>Associated Types</h3> |
| |
| 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 <tt>Graph</tt> type. |
| |
| <hr> |
| |
| <pre> |
| graph_traits<subgraph>::vertex_descriptor |
| </pre> |
| The type for the vertex descriptors. |
| (Required by <a href="Graph.html">Graph</a>.) |
| |
| <hr> |
| |
| <pre> |
| graph_traits<subgraph>::edge_descriptor |
| </pre> |
| The type for the edge descriptors. |
| (Required by <a href="Graph.html">Graph</a>.) |
| |
| <hr> |
| |
| <pre> |
| graph_traits<subgraph>::vertex_iterator |
| </pre> |
| The type for the iterators returned by <tt>vertices</tt>. |
| (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) |
| |
| <hr> |
| |
| <pre> |
| graph_traits<subgraph>::edge_iterator |
| </pre> |
| The type for the iterators returned by <tt>edges</tt>. |
| (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::out_edge_iterator |
| </pre> |
| The type for the iterators returned by <tt>out_edges</tt>. |
| (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::in_edge_iterator |
| </pre> |
| The <tt>in_edge_iterator</tt> is the |
| iterator type returned by the <tt>in_edges</tt> function. |
| (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::adjacency_iterator |
| </pre> |
| The type for the iterators returned by <tt>adjacent_vertices</tt>. |
| (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::directed_category |
| </pre> |
| Provides information about whether the graph is directed |
| (<tt>directed_tag</tt>) or undirected (<tt>undirected_tag</tt>). |
| (Required by <a href="Graph.html">Graph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::edge_parallel_category |
| </pre> |
| This describes whether the graph class allows the insertion of |
| parallel edges (edges with the same source and target), which |
| depends on the underlying <tt>Graph</tt> class. The two tags are |
| <tt>allow_parallel_edge_tag</tt> and |
| <tt>disallow_parallel_edge_tag</tt>. |
| (Required by <a href="Graph.html">Graph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::vertices_size_type |
| </pre> |
| The type used for dealing with the number of vertices in |
| the graph. |
| (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::edges_size_type |
| </pre> |
| The type used for dealing with the number of edges in the graph. |
| (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) |
| |
| <hr> |
| <pre> |
| graph_traits<subgraph>::degree_size_type |
| </pre> |
| The type used for dealing with the number of out-edges of a vertex. |
| (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) |
| |
| <hr> |
| <pre> |
| property_map<subgraph, PropertyTag>::type |
| property_map<subgraph, PropertyTag>::const_type |
| </pre> |
| The map type for vertex or edge properties in the graph. The |
| specific property is specified by the <tt>PropertyTag</tt> template |
| argument, and must match one of the properties specified in the |
| <tt>VertexProperty</tt> or <tt>EdgeProperty</tt> for the graph. |
| (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) |
| |
| <hr> |
| <pre> |
| subgraph::children_iterator |
| </pre> |
| The iterator type for accessing the children subgraphs of the graph. |
| |
| |
| |
| <!-----------------------------> |
| <h3>Member Functions</h3> |
| |
| |
| |
| <hr> |
| <pre> |
| subgraph(vertices_size_type n, const GraphProperty& p = GraphProperty()) |
| </pre> |
| Creates the root graph object with <tt>n</tt> vertices and zero edges. |
| |
| <hr> |
| <pre> |
| subgraph<Graph>& create_subgraph(); |
| </pre> |
| Creates an empty subgraph object whose parent is <i>this</i> |
| graph. |
| |
| <hr> |
| <pre> |
| template <typename VertexIterator> |
| subgraph<Graph>& |
| create_subgraph(VertexIterator first, VertexIterator last) |
| </pre> |
| 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 <i>this</i> graph) that |
| connects two vertices in the subgraph will be added to the |
| subgraph. |
| |
| <hr> |
| <pre> |
| vertex_descriptor local_to_global(vertex_descriptor u_local) const |
| </pre> |
| Converts a local vertex descriptor to the corresponding global |
| vertex descriptor. |
| |
| <hr> |
| <pre> |
| vertex_descriptor global_to_local(vertex_descriptor u_global) const |
| </pre> |
| Converts a global vertex descriptor to the corresponding local |
| vertex descriptor. |
| |
| <hr> |
| <pre> |
| edge_descriptor local_to_global(edge_descriptor e_local) const |
| </pre> |
| Converts a local edge descriptor to the corresponding global edge |
| descriptor. |
| |
| <hr> |
| <pre> |
| edge_descriptor global_to_local(edge_descriptor u_global) const |
| </pre> |
| Converts a global edge descriptor to the corresponding local edge |
| descriptor. |
| |
| <hr> |
| <pre> |
| std::pair<vertex_descriptor, bool> find_vertex(vertex_descriptor u_global) const |
| </pre> |
| If vertex <i>u</i> is in this subgraph, the function returns the local |
| vertex descriptor that corresponds to the global vertex descriptor |
| <tt>u_global</tt> as the first part of the pair and <tt>true</tt> for |
| the second part of the pair. If vertex <i>u</i> is not in the subgraph |
| then this function returns false in the second part of the |
| pair. |
| |
| <hr> |
| <pre> |
| subgraph& root() |
| </pre> |
| Returns the root graph of the subgraph tree. |
| |
| <hr> |
| <pre> |
| bool is_root() const |
| </pre> |
| Return <tt>true</tt> if the graph is the root of the subgraph tree, |
| and returns <tt>false</tt> otherwise. |
| |
| <hr> |
| <pre> |
| subgraph& parent() |
| </pre> |
| Returns the parent graph. |
| |
| <hr> |
| <pre> |
| std::pair<children_iterator, children_iterator> children() const |
| </pre> |
| Return an iterator pair for accessing the children subgraphs. |
| |
| |
| <!-----------------------------> |
| <h3>Nonmember Functions</h3> |
| |
| The functionality of <tt>subgraph</tt> depends on the |
| <tt>Graph</tt> type. For example, if <tt>Graph</tt> in a |
| <a href="BidirectionalGraph.html">BidirectionalGraph</a> and supports <tt>in_edges</tt>, then so |
| does <tt>subgraph</tt>. Here we list all the functions that |
| <tt>subgraph</tt> could possibly support given a <tt>Graph</tt> |
| type that is a model of <a href="VertexListGraph.html">VertexListGraph</a>, <a href="EdgeListGraph.html">EdgeListGraph</a> and |
| <a href="BidirectionalGraph.html">BidirectionalGraph</a>. If the <tt>Graph</tt> type that you use |
| with <tt>subgraph</tt> does not model these concepts and supports |
| fewer functions, then the <tt>subgraph</tt> will also support |
| fewer functions and some of the functions listed below will not be |
| implemented. |
| |
| |
| <hr> |
| <pre> |
| std::pair<vertex_iterator, vertex_iterator> |
| vertices(const subgraph& g) |
| </pre> |
| Returns an iterator range providing access to the vertex set of subgraph <i>g</i>. |
| (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) |
| |
| <hr> |
| <pre> |
| std::pair<edge_iterator, edge_iterator> |
| edges(const subgraph& g) |
| </pre> |
| Returns an iterator range providing access to the edge set of subgraph <i>g</i>. |
| (Required by <a href="EdgeListGraph.html">EdgeListGraph</a>.) |
| |
| <hr> |
| <pre> |
| std::pair<adjacency_iterator, adjacency_iterator> |
| adjacent_vertices(vertex_descriptor u_local, const subgraph& g) |
| </pre> |
| Returns an iterator range providing access to the vertices |
| adjacent to |
| vertex <i>u</i> in subgraph <i>g</i>. |
| (Required by <a href="AdjacencyGraph.html">AdjacencyGraph</a>.) |
| |
| <hr> |
| <pre> |
| std::pair<out_edge_iterator, out_edge_iterator> |
| out_edges(vertex_descriptor u_local, const subgraph& g) |
| </pre> |
| Returns an iterator range providing access to the out-edges of |
| vertex <i>u</i> in subgraph <i>g</i>. If the graph is undirected, this |
| iterator range provides access to all edge incident on |
| vertex <i>u</i>. |
| (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) |
| |
| <hr> |
| <pre> |
| std::pair<in_edge_iterator, in_edge_iterator> |
| in_edges(vertex_descriptor v_local, const subgraph& g) |
| </pre> |
| Returns an iterator range providing access to the in-edges of |
| vertex |
| <i>v</i> in subgraph <i>g</i>. |
| (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) |
| |
| <hr> |
| <pre> |
| vertex_descriptor |
| source(edge_descriptor e_local, const subgraph& g) |
| </pre> |
| Returns the source vertex of edge <i>e</i> in subgraph <i>g</i>. |
| (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) |
| |
| <hr> |
| <pre> |
| vertex_descriptor |
| target(edge_descriptor e_local, const subgraph& g) |
| </pre> |
| Returns the target vertex of edge <i>e</i> in subgraph <i>g</i>. |
| (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) |
| |
| <hr> |
| <pre> |
| degree_size_type |
| out_degree(vertex_descriptor u_local, const subgraph& g) |
| </pre> |
| Returns the number of edges leaving vertex <i>u</i> in subgraph <i>g</i>. |
| (Required by <a href="IncidenceGraph.html">IncidenceGraph</a>.) |
| |
| <hr> |
| <pre> |
| degree_size_type in_degree(vertex_descriptor u_local, const subgraph& g) |
| </pre> |
| Returns the number of edges entering vertex <i>u</i> in subgraph <i>g</i>. |
| (Required by <a href="BidirectionalGraph.html">BidirectionalGraph</a>.) |
| |
| <hr> |
| <pre> |
| vertices_size_type num_vertices(const subgraph& g) |
| </pre> |
| Returns the number of vertices in the subgraph <i>g</i>. |
| (Required by <a href="VertexListGraph.html">VertexListGraph</a>.) |
| |
| <hr> |
| <pre> |
| edges_size_type num_edges(const subgraph& g) |
| </pre> |
| Returns the number of edges in the subgraph <i>g</i>. (Required by |
| <a href="EdgeListGraph.html">EdgeListGraph</a>.) |
| |
| <hr> |
| <pre> |
| vertex_descriptor vertex(vertices_size_type n, const subgraph& g) |
| </pre> |
| Returns the <i>n</i>th vertex in the subgraph's vertex list. |
| |
| <hr> |
| <pre> |
| std::pair<edge_descriptor, bool> |
| edge(vertex_descriptor u_local, vertex_descriptor v_local, const subgraph& g) |
| </pre> |
| Returns the edge connecting vertex <i>u</i> to vertex <i>v</i> in subgraph <i>g</i>. |
| (Required by <a href="AdjacencyMatrix.html">AdjacencyMatrix</a>.) |
| |
| |
| |
| <hr> |
| <pre> |
| std::pair<edge_descriptor, bool> |
| add_edge(vertex_descriptor u_local, vertex_descriptor v_local, subgraph& g) |
| </pre> |
| Adds edge <i>(u,v)</i> to the subgraph <i>g</i> 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 <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>.) |
| |
| <hr> |
| <pre> |
| std::pair<edge_descriptor, bool> |
| add_edge(vertex_descriptor u_local, vertex_descriptor v_local, |
| const EdgeProperty& p, subgraph& g) |
| </pre> |
| Adds edge <i>(u,v)</i> to the graph and attaches <tt>p</tt> as the value |
| of the edge's internal property storage. Also see the previous |
| <tt>add_edge</tt> member function for more details. |
| |
| <hr> |
| <pre> |
| void remove_edge(vertex_descriptor u_local, vertex_descriptor v_local, |
| subgraph& g) |
| </pre> |
| Removes the edge <i>(u,v)</i> from the subgraph and from all of the |
| ancestors of <tt>g</tt> in the subgraph tree. |
| (Required by <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>.) |
| |
| <hr> |
| <pre> |
| void remove_edge(edge_descriptor e_local, subgraph& g) |
| </pre> |
| Removes the edge <tt>e</tt> from the subgraph and from all of the |
| ancestors of <tt>g</tt> in the subgraph tree. |
| (Required by <a href="EdgeMutableGraph.html">EdgeMutableGraph</a>.) |
| |
| <hr> |
| <pre> |
| vertex_descriptor |
| add_vertex(subgraph& g) |
| </pre> |
| Adds a vertex to the subgraph and returns the vertex descriptor |
| for the new vertex. The vertex is also added to all ancestors of |
| <tt>g</tt> in the subgraph tree to maintain the subgraph property. |
| (Required by <a href="VertexMutableGraph.html">VertexMutableGraph</a>.) |
| |
| <hr> |
| <pre> |
| vertex_descriptor |
| add_vertex(vertex_descriptor u_global, subgraph& g) |
| </pre> |
| Adds the vertex <i>u</i> from the root graph to the subgraph <tt>g</tt>. |
| (Required by <a href="VertexMutableGraph.html">VertexMutableGraph</a>.) |
| |
| |
| <hr> |
| <pre> |
| 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) |
| </pre> |
| Returns the property map object for the vertex or edge property |
| specified by <tt>PropertyTag</tt>. The <tt>PropertyTag</tt> must match one |
| of the properties specified in the graph's <tt>PropertyTag</tt> |
| 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 <a href="PropertyGraph.html">PropertyGraph</a>.) |
| |
| <hr> |
| <pre> |
| 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) |
| </pre> |
| This returns the property value for the key <tt>k_local</tt>, which |
| is either a local vertex or local edge descriptor. See the above |
| <tt>get</tt> function |
| for more information about the propert maps. |
| (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) |
| |
| <hr> |
| <pre> |
| template <class PropertyTag, class Key, class Value> |
| void |
| put(PropertyTag, const subgraph& g, Key k_local, const Value& value) |
| </pre> |
| This sets the property value for the key <tt>k_local</tt> to |
| <tt>value</tt>. <tt>k_local</tt> is either a local vertex or local |
| edge descriptor. <tt>Value</tt> must be convertible to |
| <tt>typename |
| property_traits<property_map<adjacency_matrix, |
| PropertyTag>::type>::value_type</tt>. |
| (Required by <a href="PropertyGraph.html">PropertyGraph</a>.) |
| |
| <hr> |
| <pre> |
| template <class GraphProperties, class GraphPropertyTag> |
| typename property_value<GraphProperties, GraphPropertyTag>::type& |
| get_property(subgraph& g, GraphPropertyTag); |
| </pre> |
| Return the property specified by <tt>GraphPropertyTag</tt> that is attached |
| to the subgraph object <tt>g</tt>. The <tt>property_value</tt> traits class |
| is defined in <tt>boost/pending/property.hpp</tt>. |
| |
| |
| <hr> |
| <pre> |
| template <class GraphProperties, class GraphPropertyTag> |
| const typename property_value<GraphProperties, GraphPropertyTag>::type& |
| get_property(const subgraph& g, GraphPropertyTag); |
| </pre> |
| Return the property specified by <tt>GraphPropertyTag</tt> that is |
| attached to the subgraph object <tt>g</tt>. The <tt>property_value</tt> |
| traits class is defined in <tt>boost/pending/property.hpp</tt>. |
| |
| <hr> |
| <h2>Notes</h2> |
| 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 <a href="bundles.html">bundled properties</a>, or any adjacency list whose |
| vertex set is selected by anything other that <tt>vecS</tt>. |
| |
| However, this problem can be overcome by embedding your bundled (or otherwise) |
| properties into a <tt>property</tt> that contains an appropriate index. For |
| example: |
| <pre> |
| 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; |
| </pre> |
