123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666 |
- <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 property 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 referring 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, C1 }; // for conveniently referring to vertices in G1
- enum { A2, B2 }; // for conveniently referring 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 property 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, 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;
- </pre>
|