1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/graph/wavefront.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,135 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
1.7 +// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +
1.15 +#ifndef BOOST_GRAPH_WAVEFRONT_HPP
1.16 +#define BOOST_GRAPH_WAVEFRONT_HPP
1.17 +
1.18 +#include <boost/config.hpp>
1.19 +#include <boost/graph/graph_traits.hpp>
1.20 +#include <boost/detail/numeric_traits.hpp>
1.21 +#include <boost/graph/bandwidth.hpp>
1.22 +#include <cmath>
1.23 +#include <vector>
1.24 +#include <algorithm> // for std::min and std::max
1.25 +
1.26 +namespace boost {
1.27 +
1.28 + template <typename Graph, typename VertexIndexMap>
1.29 + typename graph_traits<Graph>::vertices_size_type
1.30 + ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,
1.31 + const Graph& g,
1.32 + VertexIndexMap index)
1.33 + {
1.34 + typename graph_traits<Graph>::vertex_descriptor v, w;
1.35 + typename graph_traits<Graph>::vertices_size_type b = 1;
1.36 + typename graph_traits<Graph>::out_edge_iterator edge_it2, edge_it2_end;
1.37 + typename graph_traits<Graph>::vertices_size_type index_i = index[i];
1.38 + std::vector<bool> rows_active(num_vertices(g), false);
1.39 +
1.40 + rows_active[index_i] = true;
1.41 +
1.42 + typename graph_traits<Graph>::vertex_iterator ui, ui_end;
1.43 + for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
1.44 + {
1.45 + v = *ui;
1.46 + if(index[v] <= index_i)
1.47 + {
1.48 + for (tie(edge_it2, edge_it2_end) = out_edges(v, g); edge_it2 != edge_it2_end; ++edge_it2)
1.49 + {
1.50 + w = target(*edge_it2, g);
1.51 + if( (index[w] >= index_i) && (!rows_active[index[w]]) )
1.52 + {
1.53 + b++;
1.54 + rows_active[index[w]] = true;
1.55 + }
1.56 + }
1.57 + }
1.58 + }
1.59 +
1.60 + return b;
1.61 + }
1.62 +
1.63 +
1.64 + template <typename Graph>
1.65 + typename graph_traits<Graph>::vertices_size_type
1.66 + ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,
1.67 + const Graph& g)
1.68 + {
1.69 + return ith_wavefront(i, g, get(vertex_index, g));
1.70 + }
1.71 +
1.72 +
1.73 + template <typename Graph, typename VertexIndexMap>
1.74 + typename graph_traits<Graph>::vertices_size_type
1.75 + max_wavefront(const Graph& g, VertexIndexMap index)
1.76 + {
1.77 + BOOST_USING_STD_MAX();
1.78 + typename graph_traits<Graph>::vertices_size_type b = 0;
1.79 + typename graph_traits<Graph>::vertex_iterator i, end;
1.80 + for (tie(i, end) = vertices(g); i != end; ++i)
1.81 + b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b, ith_wavefront(*i, g, index));
1.82 + return b;
1.83 + }
1.84 +
1.85 + template <typename Graph>
1.86 + typename graph_traits<Graph>::vertices_size_type
1.87 + max_wavefront(const Graph& g)
1.88 + {
1.89 + return max_wavefront(g, get(vertex_index, g));
1.90 + }
1.91 +
1.92 +
1.93 + template <typename Graph, typename VertexIndexMap>
1.94 + double
1.95 + aver_wavefront(const Graph& g, VertexIndexMap index)
1.96 + {
1.97 + double b = 0;
1.98 + typename graph_traits<Graph>::vertex_iterator i, end;
1.99 + for (tie(i, end) = vertices(g); i != end; ++i)
1.100 + b += ith_wavefront(*i, g, index);
1.101 +
1.102 + b /= num_vertices(g);
1.103 + return b;
1.104 + }
1.105 +
1.106 + template <typename Graph>
1.107 + double
1.108 + aver_wavefront(const Graph& g)
1.109 + {
1.110 + return aver_wavefront(g, get(vertex_index, g));
1.111 + }
1.112 +
1.113 +
1.114 + template <typename Graph, typename VertexIndexMap>
1.115 + double
1.116 + rms_wavefront(const Graph& g, VertexIndexMap index)
1.117 + {
1.118 + double b = 0;
1.119 + typename graph_traits<Graph>::vertex_iterator i, end;
1.120 + for (tie(i, end) = vertices(g); i != end; ++i)
1.121 + b += std::pow(double ( ith_wavefront(*i, g, index) ), 2.0);
1.122 +
1.123 + b /= num_vertices(g);
1.124 +
1.125 + return std::sqrt(b);
1.126 + }
1.127 +
1.128 + template <typename Graph>
1.129 + double
1.130 + rms_wavefront(const Graph& g)
1.131 + {
1.132 + return rms_wavefront(g, get(vertex_index, g));
1.133 + }
1.134 +
1.135 +
1.136 +} // namespace boost
1.137 +
1.138 +#endif // BOOST_GRAPH_WAVEFRONT_HPP