Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/graph/bandwidth.hpp @ 125:34e428693f5d vext

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