Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

C++ Boost 

reverse_graph<BidirectionalGraph, GraphReference>
The reverse_graph adaptor flips the in-edges and out-edges of a BidirectionalGraph, effectively transposing the graph. The construction of the reverse_graph is constant time, providing a highly efficient way to obtain a transposed view of a graph.

Example

The example from example/reverse_graph.cpp. 
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;
}
The output is: 
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

Template Parameters

ParameterDescriptionDefault
BidirectionalGraph The graph type to be adapted.  
GraphReference This type should be const BidirectionalGraph& if you want to create a const reverse graph, or BidirectionalGraph& if you want to create a non-const reverse graph. const BidirectionalGraph&

Model of

BidirectionalGraph and optionally VertexListGraph and PropertyGraph

Where Defined

boost/graph/reverse_graph.hpp

Associated Types

graph_traits<reverse_graph>::vertex_descriptor

The type for the vertex descriptors associated with the reverse_graph.
graph_traits<reverse_graph>::edge_descriptor

The type for the edge descriptors associated with the reverse_graph.
graph_traits<reverse_graph>::vertex_iterator

The type for the iterators returned by vertices().
graph_traits<reverse_graph>::edge_iterator

The type for the iterators returned by edges().
graph_traits<reverse_graph>::out_edge_iterator

The type for the iterators returned by out_edges().
graph_traits<reverse_graph>::adjacency_iterator

The type for the iterators returned by adjacent_vertices().
graph_traits<reverse_graph>::directed_category

Provides information about whether the graph is directed (directed_tag) or undirected (undirected_tag).
graph_traits<reverse_graph>::edge_parallel_category

This describes whether the graph class allows the insertion of parallel edges (edges with the same source and target). The two tags are allow_parallel_edge-_tag and disallow_parallel_edge_tag. The setS and hash_setS variants disallow parallel edges while the others allow parallel edges.
graph_traits<reverse_graph>::vertices_size_type

The type used for dealing with the number of vertices in the graph.
graph_traits<reverse_graph>::edges_size_type

The type used for dealing with the number of edges in the graph.
graph_traits<reverse_graph>::degree_size_type

The type used for dealing with the number of edges incident to a vertex in the graph.
property_map<reverse_graph, PropertyTag>::type
and
property_map<reverse_graph, PropertyTag>::const_type

The property map type for vertex or edge properties in the graph. The specific property is specified by the PropertyTag template argument, and must match one of the properties specified in the VertexProperty or EdgeProperty for the graph.
property_map<reverse_graph, edge_underlying_t>::type
and
property_map<reverse_graph, edge_underlying_t>::const_type

An edge property type mapping from edge descriptors in the reverse_graph to edge descriptors in the underlying BidirectionalGraph object.

Member Functions

reverse_graph(BidirectionalGraph& g)
Constructor. Create a reversed (transposed) view of the graph g.

Non-Member Functions

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)
Helper function for creating a reverse_graph. 
std::pair<vertex_iterator, vertex_iterator>
vertices(const reverse_graph& g)
Returns an iterator-range providing access to the vertex set of graph g. 
std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor v, const reverse_graph& g)
Returns an iterator-range providing access to the out-edges of vertex v in graph g. These out-edges correspond to the in-edges of the adapted graph. 
std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const reverse_graph& g)
Returns an iterator-range providing access to the in-edges of vertex v in graph g. These in-edges correspond to the out edges of the adapted graph. 
std::pair<adjacency_iterator, adjacency__iterator>
adjacent_vertices(vertex_descriptor v, const reverse_graph& g)
Returns an iterator-range providing access to the adjacent vertices of vertex v in graph g. 
vertex_descriptor
source(edge_descriptor e, const reverse_graph& g)
Returns the source vertex of edge e. 
vertex_descriptor
target(edge_descriptor e, const reverse_graph& g)
Returns the target vertex of edge e. 
degree_size_type
out_degree(vertex_descriptor u, const reverse_graph& g)
Returns the number of edges leaving vertex u. 
degree_size_type
in_degree(vertex_descriptor u, const reverse_graph& g)
Returns the number of edges entering vertex u. This operation is only available if bidirectionalS was specified for the Directed template parameter. 
vertices_size_type
num_vertices(const reverse_graph& g)
Returns the number of vertices in the graph g. 
vertex_descriptor
vertex(vertices_size_type n, const reverse_graph& g)
Returns the nth vertex in the graph's vertex list. 
std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v,
     const reverse_graph& g)
Returns the edge connecting vertex u to vertex v in graph g. 
template <class PropertyTag>
property_map<reverse_graph, PropertyTag>::type
get(PropertyTag, reverse_graph& g)

template <class PropertyTag>
property_map<reverse_graph, Tag>::const_type
get(PropertyTag, const reverse_graph& g)
Returns the property map object for the vertex property specified by PropertyTag. The PropertyTag must match one of the properties specified in the graph's VertexProperty template argument. 
property_map<reverse_graph, edge_underlying_t>::const_type
get(PropertyTag, const reverse_graph& g)
Returns a property map object that converts from edge descriptors in the reverse_graph to edge descriptors in the underlying BidirectionalGraph object. 
template <class PropertyTag, class X>
typename property_traits<property_map<reverse_graph, PropertyTag>::const_type>::value_type
get(PropertyTag, const reverse_graph& g, X x)
This returns the property value for x, which is either a vertex or edge descriptor. 
typename graph_traits<BidirectionalGraph>::edge_descriptor
get(edge_underlying_t, const reverse_graph& g, edge_descriptor e)
This returns the underlying edge descriptor for the edge e in the reverse_graph. 
template <class PropertyTag, class X, class Value>
void
put(PropertyTag, const reverse_graph& g, X x, const Value& value)
This sets the property value for x to value. x is either a vertex or edge descriptor. Value must be convertible to typename property_traits<property_map<reverse_graph, PropertyTag>::type>::value_type 
template <class GraphProperties, class GraphPropertyTag>
typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(reverse_graph& g, GraphPropertyTag);
Return the property specified by GraphPropertyTag that is attached to the graph object g. The property_value traits class is defined in boost/pending/property.hpp. 
template <class GraphProperties, class GraphPropertyTag>
const typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(const reverse_graph& g, GraphPropertyTag);
Return the property specified by GraphPropertyTag that is attached to the graph object g. The property_value traits class is defined in boost/pending/property.hpp.

Copyright © 2000-2001 Dave Abrahams (david.abrahams@rcn.com)
Jeremy Siek, Indiana University (jsiek@osl.iu.edu)