b0214ec131
* Fix documentation about type alias edge_size_type -> edges_size_type This replaces occurences of `edge_size_type` (sg.) in the documentation with the actual `edges_size_type` (pl.) as it is named in the implementation. There is a graph implementation (Stanford graph) that has a type alias of `edge_size_type` (sg.) --- I did not change that implementation, as it would break backwards compatibility, and therefore I also did not change its documentation. * Fix documentation on push_relabel algorithm, defined in header: preflow_push -> push_relabel
447 lines
12 KiB
HTML
447 lines
12 KiB
HTML
<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>
|