This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

transpose_graph

Computes the transpose of a directed graph, reversing the direction of every edge.

Complexity: O(V + E)
Defined in: <boost/graph/transpose_graph.hpp>

Example

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/transpose_graph.hpp>

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>;
    Graph g;
    boost::add_edge(0, 1, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(2, 0, g);

    std::cout << "Original edges: ";
    for (auto ep = edges(g); ep.first != ep.second; ++ep.first) {
        std::cout << source(*ep.first, g) << "->" << target(*ep.first, g) << " ";
    }

    Graph gt;
    boost::transpose_graph(g, gt);

    std::cout << "\nTransposed edges: ";
    for (auto ep = edges(gt); ep.first != ep.second; ++ep.first) {
        std::cout << source(*ep.first, gt) << "->" << target(*ep.first, gt) << " ";
    }
    std::cout << "\n";
}
Original edges: 0->1 1->2 2->0
Transposed edges: 1->0 2->1 0->2

(1) Named parameter version

template <class VertexListGraph, class MutableGraph,
          class P, class T, class R>
void transpose_graph(
    const VertexListGraph& G, MutableGraph& G_T,
    const bgl_named_params<P, T, R>& params);
Direction Parameter Description

IN

const VertexListGraph& G

A directed graph. The graph type must be a model of Vertex List Graph.

OUT

MutableGraph& G_T

The transposed graph. The graph type must be a model of Mutable Graph.

Named Parameters

Direction Parameter Description

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, adjacency_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.

(2) Positional version

template <class VertexListGraph, class MutableGraph>
void transpose_graph(const VertexListGraph& G, MutableGraph& G_T);

Equivalent to (1) with every named parameter left at its default. Uses the default vertex/edge copiers (via vertex_all / edge_all property tags) and get(vertex_index, G).

Direction Parameter Description

IN

const VertexListGraph& G

Same as (1).

OUT

MutableGraph& G_T

Same as (1).

Description

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}. That is, 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 for each edge (u,v) in G.

Example

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

Edit this Page