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.

bandwidth

Computes the bandwidth of a graph, which is the maximum distance between two adjacent vertices when vertices are placed at unit intervals on a line.

Complexity: O(|E|)
Defined in: <boost/graph/bandwidth.hpp>

Example

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

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    Graph g{5};
    boost::add_edge(0, 1, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(0, 4, g);
    boost::add_edge(3, 4, g);

    auto bw = boost::bandwidth(g);
    std::cout << "Bandwidth: " << bw << "\n";
}
Bandwidth: 4

(1) Default vertex index overload

template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
bandwidth(const Graph& g)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Edge List Graph. The default vertex_index property map is used.

(2) Explicit vertex index map overload

template <typename Graph, typename VertexIndexMap>
typename graph_traits<Graph>::vertices_size_type
bandwidth(const Graph& g, VertexIndexMap index_map)
Direction Parameter Description

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Edge List Graph.

IN

VertexIndexMap index_map

This maps each vertex to an integer in the range [0, num_vertices(g)). The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Description

The bandwidth of a graph is the maximum distance between two adjacent vertices, with distance measured on a line upon which the vertices have been placed at unit intervals. To put it another way, if the vertices of a graph G=(V,E) are each assigned an index from zero to |V| - 1 given by index[v], then the bandwidth of G is

B(G) = max { |index[u] - index[v]|   | (u,v) in E }

Example

The bandwidth function is used in the following ordering examples: cuthill_mckee_ordering, king_ordering, sloan_ordering.

ith_bandwidth

Computes the bandwidth of the i-th vertex, which is the maximum distance between that vertex and any of its neighbors.

Complexity: O(out_degree(i))
Defined in: <boost/graph/bandwidth.hpp>

(1) Default vertex index overload

template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
ith_bandwidth(
    typename graph_traits<Graph>::vertex_descriptor i,
    const Graph& g)
Direction Parameter Description

IN

vertex_descriptor i

The vertex for which to compute the bandwidth.

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Incidence Graph. The default vertex_index property map is used.

(2) Explicit vertex index map overload

template <typename Graph, typename VertexIndexMap>
typename graph_traits<Graph>::vertices_size_type
ith_bandwidth(
    typename graph_traits<Graph>::vertex_descriptor i,
    const Graph& g,
    VertexIndexMap index)
Direction Parameter Description

IN

vertex_descriptor i

The vertex for which to compute the bandwidth.

IN

const Graph& g

The graph object on which the algorithm will be applied. The type Graph must be a model of Incidence Graph.

IN

VertexIndexMap index

This maps each vertex to an integer in the range [0, num_vertices(g)). The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Description

The i-th bandwidth of a graph is the maximum distance between the i-th vertex and any of its neighbors.

Bi(G) = max { |index[i] - index[j]|   | (i,j) in E }

So the bandwidth B(G) can be expressed as the maximum of the i-th bandwidths Bi(G).

B(G) = max { Bi(G)   | i=0…​|V|-1 }

Example

The ith_bandwidth function is used internally by bandwidth and by the ordering examples: cuthill_mckee_ordering, king_ordering, sloan_ordering.

Edit this Page