<HTML> <!-- Copyright (c) Jeremy Siek 2000 Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> <Head> <Title>Boost Graph Library: Bandwidth</Title> <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"> <BR Clear> <H1><A NAME="sec:bandwidth"> <TT>bandwidth</TT> </H1> <pre> (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) </pre> The <b><i>bandwidth</i></b> 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 <i>G=(V,E)</i> are each assigned an index from zero to <i>|V| - 1</i> given by <i>index[v]</i>, then the bandwidth of <i>G</i> is<br> <br> <i>B(G) = max { |index[u] - index[v]| | (u,v) in E }</i><br> <h3>Defined in</h3> <a href="../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp</tt></a> <hr> <H1><A NAME="sec:ith-bandwidth"> <TT>ith_bandwidth</TT> </H1> <pre> (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) </pre> The <b><i>i-th bandwidth</i></b> a graph is the maximum distance between the <i>i-th</i> vertex and any of its neighbors.<br> <br> <i>B<sub>i</sub>(G) = max { |index[i] - index[j]| | (i,j) in E }</i><br> <br> So the bandwidth <i>B(G)</i> can be expressed as the maximum of the i-th bandwidths <i>B<sub>i</sub>(G)</i>.<br> <br> <i>B(G) = max { B<sub>i</sub>(G) | i=0...|V|-1 }</i><br> <h3>Defined in</h3> <a href="../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp</tt></a> <br> <HR> <TABLE> <TR valign=top> <TD nowrap>Copyright © 2000-2001</TD><TD> <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>) </TD></TR></TABLE> </BODY> </HTML>