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

transpose_graph

template <class VertexListGraph, class MutableGraph> 
void transpose_graph(const VertexListGraph& G, MutableGraph& G_T,
    const bgl_named_params<P, T, R>& params = all defaults)

This function computes the transpose of a directed graph. The transpose of a directed graph G = (V, E)is the graph GT = (V, ET) , where ET = {(v, u) in V x V: (u, v) in E} . i.e., GT is G with all its edges reversed. Graph G_T passed into the algorithm must have no vertices and no edges. The vertices and edges will be added by transpose_graph() by calling add_vertex and add_edge as follows for each edge (u,v) in G.

Example

Here's an example of transposing a graph: example/transpose-example.cpp.

Where Defined

boost/graph/transpose_graph.hpp

Parameters

IN: const VertexListGraph& G
A directed graph. The graph type must be a model of Vertex List Graph.
OUT: const MutableGraph& G_T
The transposed graph. The graph type must be a model of Mutable Graph.

Named Parameters

IN: vertex_copy(VertexCopier vc)
This is a Binary Function that copies the properties of a vertex in the original graph into the corresponding vertex in the copy.
Default: vertex_copier<VertexListGraph, MutableGraph> which uses the property tag vertex_all to access a property map from the graph.
IN: edge_copy(EdgeCopier ec)
This is a Binary Function that copies the properties of an edge in the original graph into the corresponding edge in the copy.
Default: edge_copier<VertexListGraph, MutableGraph> which uses the property tag edge_all to access a property map from the graph.
IN: vertex_index_map(VertexIndexMap i_map)
The vertex index map type must be a model of Readable Property Map and must map the vertex descriptors of G to the integers from 0 to num_vertices(G).
Default: get(vertex_index, G) Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacenty_list with VertexList=listS does not have an internal vertex_index property.
UTIL/OUT: orig_to_copy(Orig2CopyMap c)
This maps vertices in the original graph to vertices in the copy. Default: an iterator_property_map created from a std::vector of the output graph's vertex descriptor type of size num_vertices(g) and using the i_map for the index map.

Complexity

The time complexity is O(V + E).


Copyright © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)