<HTML> <!-- (C) Copyright David Abrahams and 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: Reverse Graph Adaptor</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:reverse-graph-adaptor"></A> </h1> <pre> reverse_graph<<a href="./BidirectionalGraph.html">BidirectionalGraph</a>, GraphReference> </pre> The <tt>reverse_graph</tt> adaptor flips the in-edges and out-edges of a <a href="./BidirectionalGraph.html">BidirectionalGraph</a>, effectively transposing the graph. The construction of the <tt>reverse_graph</tt> is constant time, providing a highly efficient way to obtain a transposed-view of a graph. <H3>Example</H3> The example from <a href="../example/reverse-graph-eg.cpp"><tt>examples/reverse-graph-eg.cpp</tt></a>. <pre> int main() { typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, > Graph; Graph G(5); boost::add_edge(0, 2, G); boost::add_edge(1, 1, G); boost::add_edge(1, 3, G); boost::add_edge(1, 4, G); boost::add_edge(2, 1, G); boost::add_edge(2, 3, G); boost::add_edge(2, 4, G); boost::add_edge(3, 1, G); boost::add_edge(3, 4, G); boost::add_edge(4, 0, G); boost::add_edge(4, 1, G); std::cout << "original graph:" << std::endl; boost::print_graph(G, boost::get(boost::vertex_index, G)); std::cout << std::endl << "reversed graph:" << std::endl; boost::print_graph(boost::make_reverse_graph(G), boost::get(boost::vertex_index, G)); return 0; } </pre> The output is: <pre> original graph: 0 --> 2 1 --> 1 3 4 2 --> 1 3 4 3 --> 1 4 4 --> 0 1 reversed graph: 0 --> 4 1 --> 1 2 3 4 2 --> 0 3 --> 1 2 4 --> 1 2 3 </pre> <H3>Template Parameters</H3> <P> <TABLE border> <TR> <th>Parameter</th><th>Description</th><th>Default</th> </tr> <TR><TD><TT>BidirectionalGraph</TT></TD> <TD>The graph type to be adapted.</TD> <TD> </TD> </TR> <TR><TD><TT>GraphReference</TT></TD> <TD>This type should be <tt>const BidirectionalGraph&</tt> if you want to create a const reverse graph, or <tt>BidirectionalGraph&</tt> if you want to create a non-const reverse graph.</TD> <TD><tt>const BidirectionalGraph&</tt></TD> </TR> </table> <H3>Model of</H3> <P> <a href="./BidirectionalGraph.html">BidirectionalGraph</a> and optionally <a href="./VertexListGraph.html">VertexListGraph</a> and <a href="./PropertyGraph.html">PropertyGraph</a> <H3>Where Defined</H3> <P> <a href="../../../boost/graph/reverse_graph.hpp"><TT>boost/graph/reverse_graph.hpp</TT></a> <H2>Associated Types</H2> <hr> <tt>graph_traits<reverse_graph>::vertex_descriptor</tt> <br><br> The type for the vertex descriptors associated with the <TT>reverse_graph</TT>. <hr> <tt>graph_traits<reverse_graph>::edge_descriptor</tt> <br><br> The type for the edge descriptors associated with the <TT>reverse_graph</TT>. <hr> <tt>graph_traits<reverse_graph>::vertex_iterator</tt> <br><br> The type for the iterators returned by <TT>vertices()</TT>. <hr> <tt>graph_traits<reverse_graph>::edge_iterator</tt> <br><br> The type for the iterators returned by <TT>edges()</TT>. <hr> <tt>graph_traits<reverse_graph>::out_edge_iterator</tt> <br><br> The type for the iterators returned by <TT>out_edges()</TT>. <hr> <tt>graph_traits<reverse_graph>::adjacency_iterator</tt> <br><br> The type for the iterators returned by <TT>adjacent_vertices()</TT>. <hr> <tt>graph_traits<reverse_graph>::directed_category</tt> <br><br> Provides information about whether the graph is directed (<TT>directed_tag</TT>) or undirected (<TT>undirected_tag</TT>). <hr> <tt>graph_traits<reverse_graph>::edge_parallel_category</tt> <br><br> This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target). The two tags are <TT>allow_parallel_edge-_tag</TT> and <TT>disallow_parallel_edge_tag</TT>. The <TT>setS</TT> and <TT>hash_setS</TT> variants disallow parallel edges while the others allow parallel edges. <hr> <tt>graph_traits<reverse_graph>::vertices_size_type</tt> <br><br> The type used for dealing with the number of vertices in the graph. <hr> <tt>graph_traits<reverse_graph>::edge_size_type</tt> <br><br> The type used for dealing with the number of edges in the graph. <hr> <tt>graph_traits<reverse_graph>::degree_size_type</tt> <br><br> The type used for dealing with the number of edges incident to a vertex in the graph. <hr> <tt>property_map<reverse_graph, PropertyTag>::type</tt><br> and<br> <tt>property_map<reverse_graph, PropertyTag>::const_type</tt> <br><br> The property 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. <hr> <H2>Member Functions</H2> <hr> <pre> reverse_graph(BidirectionalGraph& g) </pre> Constructor. Create a reversed (transposed) view of the graph <tt>g</tt>. <hr> <H2>Non-Member Functions</H2> <hr> <pre> template <class BidirectionalGraph> reverse_graph<BidirectionalGraph, BidirectionalGraph&> make_reverse_graph(BidirectionalGraph& g); template <class BidirectionalGraph> reverse_graph<BidirectionalGraph, const BidirectionalGraph&> make_reverse_graph(const BidirectionalGraph& g) </pre> Helper function for creating a <tt>reverse_graph</tt>. <hr> <pre> std::pair<vertex_iterator, vertex_iterator> vertices(const reverse_graph& g) </pre> Returns an iterator-range providing access to the vertex set of graph <tt>g</tt>. <hr> <pre> std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor v, const reverse_graph& g) </pre> Returns an iterator-range providing access to the out-edges of vertex <tt>v</tt> in graph <tt>g</tt>. These out-edges correspond to the in-edges of the adapted graph. <hr> <pre> std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor v, const reverse_graph& g) </pre> Returns an iterator-range providing access to the in-edges of vertex <tt>v</tt> in graph <tt>g</tt>. These in-edges correspond to the out edges of the adapted graph. <hr> <pre> std::pair<adjacency_iterator, adjacency__iterator> adjacent_vertices(vertex_descriptor v, const reverse_graph& g) </pre> Returns an iterator-range providing access to the adjacent vertices of vertex <tt>v</tt> in graph <tt>g</tt>. <hr> <pre> vertex_descriptor source(edge_descriptor e, const reverse_graph& g) </pre> Returns the source vertex of edge <tt>e</tt>. <hr> <pre> vertex_descriptor target(edge_descriptor e, const reverse_graph& g) </pre> Returns the target vertex of edge <tt>e</tt>. <hr> <pre> degree_size_type out_degree(vertex_descriptor u, const reverse_graph& g) </pre> Returns the number of edges leaving vertex <tt>u</tt>. <hr> <pre> degree_size_type in_degree(vertex_descriptor u, const reverse_graph& g) </pre> Returns the number of edges entering vertex <tt>u</tt>. This operation is only available if <TT>bidirectionalS</TT> was specified for the <TT>Directed</TT> template parameter. <hr> <pre> vertices_size_type num_vertices(const reverse_graph& g) </pre> Returns the number of vertices in the graph <tt>g</tt>. <hr> <pre> vertex_descriptor vertex(vertices_size_type n, const reverse_graph& g) </pre> Returns the nth vertex in the graph's vertex list. <hr> <pre> std::pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor v, const reverse_graph& g) </pre> Returns the edge connecting vertex <tt>u</tt> to vertex <tt>v</tt> in graph <tt>g</tt>. <hr> <pre> template <class <a href="./PropertyTag.html">PropertyTag</a>> property_map<reverse_graph, PropertyTag>::type get(PropertyTag, reverse_graph& g) template <class <a href="./PropertyTag.html">PropertyTag</a>> property_map<reverse_graph, Tag>::const_type get(PropertyTag, const reverse_graph& g) </pre> Returns the property map object for the vertex property specified by <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the properties specified in the graph's <TT>VertexProperty</TT> template argument. <hr> <pre> template <class <a href="./PropertyTag.html">PropertyTag</a>, class X> typename property_traits<property_map<reverse_graph, PropertyTag>::const_type>::value_type get(PropertyTag, const reverse_graph& g, X x) </pre> This returns the property value for <tt>x</tt>, which is either a vertex or edge descriptor. <hr> <pre> template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> void put(PropertyTag, const reverse_graph& g, X x, const Value& value) </pre> This sets the property value for <tt>x</tt> to <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor. <tt>Value</tt> must be convertible to <tt>typename property_traits<property_map<reverse_graph, PropertyTag>::type>::value_type</tt> <hr> <pre> template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> typename property_value<GraphProperties, GraphPropertyTag>::type& get_property(reverse_graph& g, GraphPropertyTag); </pre> Return the property specified by <tt>GraphPropertyTag</tt> that is attached to the graph object <tt>g</tt>. The <tt>property_value</tt> traits class is defined in <a href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. <hr> <pre> template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> const typename property_value<GraphProperties, GraphPropertyTag>::type& get_property(const reverse_graph& g, GraphPropertyTag); </pre> Return the property specified by <tt>GraphPropertyTag</tt> that is attached to the graph object <tt>g</tt>. The <tt>property_value</tt> traits class is defined in <a href="../../../boost/pending/property.hpp"><tt>boost/pending/property.hpp</tt></a>. <hr> <br> <HR> <TABLE> <TR valign=top> <TD nowrap>Copyright © 2000-2001</TD><TD> <a HREF="http://www.boost.org/people/dave_abrahams.htm">Dave Abrahams</a> (<A HREF="mailto:david.abrahams@rcn.com">david.abrahams@rcn.com</A>)<br> <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> </TD></TR></TABLE> </BODY> </HTML>