1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/bandwidth.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,83 @@
1.4 +// Copyright (c) Jeremy Siek 2001, Marc Wintermantel 2002
1.5 +//
1.6 +// Distributed under the Boost Software License, Version 1.0. (See
1.7 +// accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +#ifndef BOOST_GRAPH_BANDWIDTH_HPP
1.11 +#define BOOST_GRAPH_BANDWIDTH_HPP
1.12 +
1.13 +#include <algorithm> // for std::min and std::max
1.14 +#include <boost/config.hpp>
1.15 +#include <boost/graph/graph_traits.hpp>
1.16 +#include <boost/detail/numeric_traits.hpp>
1.17 +
1.18 +namespace boost {
1.19 +
1.20 + template <typename Graph, typename VertexIndexMap>
1.21 + typename graph_traits<Graph>::vertices_size_type
1.22 + ith_bandwidth(typename graph_traits<Graph>::vertex_descriptor i,
1.23 + const Graph& g,
1.24 + VertexIndexMap index)
1.25 + {
1.26 + BOOST_USING_STD_MAX();
1.27 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.28 + size_type b = 0;
1.29 + typename graph_traits<Graph>::out_edge_iterator e, end;
1.30 + for (tie(e, end) = out_edges(i, g); e != end; ++e) {
1.31 + int f_i = get(index, i);
1.32 + int f_j = get(index, target(*e, g));
1.33 + using namespace std; // to call abs() unqualified
1.34 + if(f_i > f_j)
1.35 + b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, size_type(f_i - f_j));
1.36 + }
1.37 + return b;
1.38 + }
1.39 +
1.40 + template <typename Graph>
1.41 + typename graph_traits<Graph>::vertices_size_type
1.42 + ith_bandwidth(typename graph_traits<Graph>::vertex_descriptor i,
1.43 + const Graph& g)
1.44 + {
1.45 + return ith_bandwidth(i, g, get(vertex_index, g));
1.46 + }
1.47 +
1.48 + template <typename Graph, typename VertexIndexMap>
1.49 + typename graph_traits<Graph>::vertices_size_type
1.50 + bandwidth(const Graph& g, VertexIndexMap index)
1.51 + {
1.52 + BOOST_USING_STD_MAX();
1.53 + typename graph_traits<Graph>::vertices_size_type b = 0;
1.54 + typename graph_traits<Graph>::vertex_iterator i, end;
1.55 + for (tie(i, end) = vertices(g); i != end; ++i)
1.56 + b = max BOOST_PREVENT_MACRO_SUBSTITUTION (b, ith_bandwidth(*i, g, index));
1.57 + return b;
1.58 + }
1.59 +
1.60 + template <typename Graph>
1.61 + typename graph_traits<Graph>::vertices_size_type
1.62 + bandwidth(const Graph& g)
1.63 + {
1.64 + return bandwidth(g, get(vertex_index, g));
1.65 + }
1.66 +
1.67 + template <typename Graph, typename VertexIndexMap>
1.68 + typename graph_traits<Graph>::vertices_size_type
1.69 + edgesum(const Graph& g, VertexIndexMap index_map)
1.70 + {
1.71 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.72 + typedef typename detail::numeric_traits<size_type>::difference_type diff_t;
1.73 + size_type sum = 0;
1.74 + typename graph_traits<Graph>::edge_iterator i, end;
1.75 + for (tie(i, end) = edges(g); i != end; ++i) {
1.76 + diff_t f_u = get(index_map, source(*i, g));
1.77 + diff_t f_v = get(index_map, target(*i, g));
1.78 + using namespace std; // to call abs() unqualified
1.79 + sum += abs(f_u - f_v);
1.80 + }
1.81 + return sum;
1.82 + }
1.83 +
1.84 +} // namespace boost
1.85 +
1.86 +#endif // BOOST_GRAPH_BANDWIDTH_HPP