(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 an undirected 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 an undirected 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
(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