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