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