1 // Copyright (c) Jeremy Siek 2001, Marc Wintermantel 2002
3 // Distributed under the Boost Software License, Version 1.0. (See
4 // accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
7 #ifndef BOOST_GRAPH_BANDWIDTH_HPP
8 #define BOOST_GRAPH_BANDWIDTH_HPP
10 #include <algorithm> // for std::min and std::max
11 #include <boost/config.hpp>
12 #include <boost/graph/graph_traits.hpp>
13 #include <boost/detail/numeric_traits.hpp>
17 template <typename Graph
, typename VertexIndexMap
>
18 typename graph_traits
<Graph
>::vertices_size_type
19 ith_bandwidth(typename graph_traits
<Graph
>::vertex_descriptor i
,
23 BOOST_USING_STD_MAX();
24 typedef typename graph_traits
<Graph
>::vertices_size_type size_type
;
26 typename graph_traits
<Graph
>::out_edge_iterator e
, end
;
27 for (tie(e
, end
) = out_edges(i
, g
); e
!= end
; ++e
) {
28 int f_i
= get(index
, i
);
29 int f_j
= get(index
, target(*e
, g
));
30 using namespace std
; // to call abs() unqualified
32 b
= max
BOOST_PREVENT_MACRO_SUBSTITUTION (b
, size_type(f_i
- f_j
));
37 template <typename Graph
>
38 typename graph_traits
<Graph
>::vertices_size_type
39 ith_bandwidth(typename graph_traits
<Graph
>::vertex_descriptor i
,
42 return ith_bandwidth(i
, g
, get(vertex_index
, g
));
45 template <typename Graph
, typename VertexIndexMap
>
46 typename graph_traits
<Graph
>::vertices_size_type
47 bandwidth(const Graph
& g
, VertexIndexMap index
)
49 BOOST_USING_STD_MAX();
50 typename graph_traits
<Graph
>::vertices_size_type b
= 0;
51 typename graph_traits
<Graph
>::vertex_iterator i
, end
;
52 for (tie(i
, end
) = vertices(g
); i
!= end
; ++i
)
53 b
= max
BOOST_PREVENT_MACRO_SUBSTITUTION (b
, ith_bandwidth(*i
, g
, index
));
57 template <typename Graph
>
58 typename graph_traits
<Graph
>::vertices_size_type
59 bandwidth(const Graph
& g
)
61 return bandwidth(g
, get(vertex_index
, g
));
64 template <typename Graph
, typename VertexIndexMap
>
65 typename graph_traits
<Graph
>::vertices_size_type
66 edgesum(const Graph
& g
, VertexIndexMap index_map
)
68 typedef typename graph_traits
<Graph
>::vertices_size_type size_type
;
69 typedef typename
detail::numeric_traits
<size_type
>::difference_type diff_t
;
71 typename graph_traits
<Graph
>::edge_iterator i
, end
;
72 for (tie(i
, end
) = edges(g
); i
!= end
; ++i
) {
73 diff_t f_u
= get(index_map
, source(*i
, g
));
74 diff_t f_v
= get(index_map
, target(*i
, g
));
75 using namespace std
; // to call abs() unqualified
76 sum
+= abs(f_u
- f_v
);
83 #endif // BOOST_GRAPH_BANDWIDTH_HPP