3 Copyright (c) Jeremy Siek 2000
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)
10 <Title>Boost Graph Library: Bandwidth
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><A NAME=
"sec:bandwidth">
24 template
<typename Graph
>
25 typename graph_traits
<Graph
>::vertices_size_type
26 bandwidth(const Graph& g)
29 template
<typename Graph, typename VertexIndexMap
>
30 typename graph_traits
<Graph
>::vertices_size_type
31 bandwidth(const Graph& g, VertexIndexMap index_map)
34 The
<b><i>bandwidth
</i></b> of a graph is the maximum
35 distance between two adjacent vertices, with distance measured on a
36 line upon which the vertices have been placed at unit intervals. To
37 put 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>
39 given by
<i>index[v]
</i>, then the bandwidth of
<i>G
</i> is
<br>
41 <i>B(G) = max { |index[u] - index[v]|
| (u,v) in E }
</i><br>
46 <a href=
"../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp
</tt></a>
51 <H1><A NAME=
"sec:ith-bandwidth">
52 <TT>ith_bandwidth
</TT>
57 template
<typename Graph
>
58 typename graph_traits
<Graph
>::vertices_size_type
59 ith_bandwidth(typename graph_traits
<Graph
>::vertex_descriptor i,
63 template
<typename Graph, typename VertexIndexMap
>
64 typename graph_traits
<Graph
>::vertices_size_type
65 ith_bandwidth(typename graph_traits
<Graph
>::vertex_descriptor i,
70 The
<b><i>i-th bandwidth
</i></b> a graph is the maximum distance
71 between the
<i>i-th
</i> vertex and any of its neighbors.
<br>
73 <i>B
<sub>i
</sub>(G) = max { |index[i] - index[j]|
| (i,j) in E }
</i><br>
75 So the bandwidth
<i>B(G)
</i> can be expressed as the maximum
76 of the i-th bandwidths
<i>B
<sub>i
</sub>(G)
</i>.
<br>
78 <i>B(G) = max { B
<sub>i
</sub>(G)
| i=
0...|V|-
1 }
</i><br>
82 <a href=
"../../../boost/graph/bandwidth.hpp"><tt>boost/graph/bandwidth.hpp
</tt></a>
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>)