123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446 |
- <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>::edges_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>
- <tt>property_map<reverse_graph, edge_underlying_t>::type</tt><br>
- and<br>
- <tt>property_map<reverse_graph, edge_underlying_t>::const_type</tt>
- <br><br>
- An edge property type mapping from edge descriptors in the <tt>reverse_graph</tt> to
- edge descriptors in the underlying <tt>BidirectionalGraph</tt> object.
- <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>
- property_map<reverse_graph, edge_underlying_t>::const_type
- get(PropertyTag, const reverse_graph& g)
- </pre>
- Returns a property map object that converts from edge descriptors in the
- <tt>reverse_graph</tt> to edge descriptors in the underlying
- <tt>BidirectionalGraph</tt> object.
- <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>
- typename graph_traits<BidirectionalGraph>::edge_descriptor
- get(edge_underlying_t, const reverse_graph& g, edge_descriptor e)
- </pre>
- This returns the underlying edge descriptor for the edge <tt>e</tt> in the <tt>reverse_graph</tt>.
- <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>
|