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

Boost Graph Library: Bandwidth

bandwidth 

  (1)
  template <typename Graph>
  typename graph_traits<Graph>::vertices_size_type
  bandwidth(const Graph& g)

  (2)
  template <typename Graph, typename VertexIndexMap>
  typename graph_traits<Graph>::vertices_size_type
  bandwidth(const Graph& g, VertexIndexMap index_map)
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 }

Defined in

boost/graph/bandwidth.hpp

ith_bandwidth 

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

  (2)
  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)
The i-th bandwidth 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 }

Defined in

boost/graph/bandwidth.hpp
Copyright © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)