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