1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 2000 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Bandwidth</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1><A NAME="sec:bandwidth"> 19<TT>bandwidth</TT> 20</H1> 21 22<pre> 23 (1) 24 template <typename Graph> 25 typename graph_traits<Graph>::vertices_size_type 26 bandwidth(const Graph& g) 27 28 (2) 29 template <typename Graph, typename VertexIndexMap> 30 typename graph_traits<Graph>::vertices_size_type 31 bandwidth(const Graph& g, VertexIndexMap index_map) 32</pre> 33 34The <b><i>bandwidth</i></b> of a graph is the maximum 35distance between two adjacent vertices, with distance measured on a 36line upon which the vertices have been placed at unit intervals. To 37put it another way, if the vertices of a graph 38<i>G=(V,E)</i> are each assigned an index from zero to <i>|V| - 1</i> 39given by <i>index[v]</i>, then the bandwidth of <i>G</i> is<br> 40<br> 41<i>B(G) = max { |index[u] - index[v]| | (u,v) in E }</i><br> 42 43 44<h3>Defined in</h3> 45 46<a href="../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp</tt></a> 47 48 49<hr> 50 51<H1><A NAME="sec:ith-bandwidth"> 52<TT>ith_bandwidth</TT> 53</H1> 54 55<pre> 56 (1) 57 template <typename Graph> 58 typename graph_traits<Graph>::vertices_size_type 59 ith_bandwidth(typename graph_traits<Graph>::vertex_descriptor i, 60 const Graph& g) 61 62 (2) 63 template <typename Graph, typename VertexIndexMap> 64 typename graph_traits<Graph>::vertices_size_type 65 ith_bandwidth(typename graph_traits<Graph>::vertex_descriptor i, 66 const Graph& g, 67 VertexIndexMap index) 68</pre> 69 70The <b><i>i-th bandwidth</i></b> a graph is the maximum distance 71between the <i>i-th</i> vertex and any of its neighbors.<br> 72<br> 73<i>B<sub>i</sub>(G) = max { |index[i] - index[j]| | (i,j) in E }</i><br> 74<br> 75So the bandwidth <i>B(G)</i> can be expressed as the maximum 76of the i-th bandwidths <i>B<sub>i</sub>(G)</i>.<br> 77<br> 78<i>B(G) = max { B<sub>i</sub>(G) | i=0...|V|-1 }</i><br> 79 80<h3>Defined in</h3> 81 82<a href="../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp</tt></a> 83 84<br> 85<HR> 86<TABLE> 87<TR valign=top> 88<TD nowrap>Copyright © 2000-2001</TD><TD> 89<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>) 90</TD></TR></TABLE> 91 92</BODY> 93</HTML> 94
