boost/graph/wavefront.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
0004 // ETH Zurich, Center of Structure Technologies
0005 // (https://web.archive.org/web/20050307090307/http://www.structures.ethz.ch/)
0006 //
0007 // Distributed under the Boost Software License, Version 1.0. (See
0008 // accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //=======================================================================
0011 //
0012
0013 #ifndef BOOST_GRAPH_WAVEFRONT_HPP
0014 #define BOOST_GRAPH_WAVEFRONT_HPP
0015
0016 #include <boost/config.hpp>
0017 #include <boost/graph/graph_traits.hpp>
0018 #include <boost/detail/numeric_traits.hpp>
0019 #include <boost/graph/bandwidth.hpp>
0020 #include <boost/config/no_tr1/cmath.hpp>
0021 #include <vector>
0022 #include <algorithm> // for std::min and std::max
0023
0024 namespace boost
0025 {
0026
0027 template < typename Graph, typename VertexIndexMap >
0028 typename graph_traits< Graph >::vertices_size_type ith_wavefront(
0029     typename graph_traits< Graph >::vertex_descriptor i, const Graph& g,
0030     VertexIndexMap index)
0031 {
0032     typename graph_traits< Graph >::vertex_descriptor v, w;
0033     typename graph_traits< Graph >::vertices_size_type b = 1;
0034     typename graph_traits< Graph >::out_edge_iterator edge_it2, edge_it2_end;
0035     typename graph_traits< Graph >::vertices_size_type index_i = index[i];
0036     std::vector< bool > rows_active(num_vertices(g), false);
0037
0038     rows_active[index_i] = true;
0039
0040     typename graph_traits< Graph >::vertex_iterator ui, ui_end;
0041     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0042     {
0043         v = *ui;
0044         if (index[v] <= index_i)
0045         {
0046             for (boost::tie(edge_it2, edge_it2_end) = out_edges(v, g);
0047                  edge_it2 != edge_it2_end; ++edge_it2)
0048             {
0049                 w = target(*edge_it2, g);
0050                 if ((index[w] >= index_i) && (!rows_active[index[w]]))
0051                 {
0052                     b++;
0053                     rows_active[index[w]] = true;
0054                 }
0055             }
0056         }
0057     }
0058
0059     return b;
0060 }
0061
0062 template < typename Graph >
0063 typename graph_traits< Graph >::vertices_size_type ith_wavefront(
0064     typename graph_traits< Graph >::vertex_descriptor i, const Graph& g)
0065 {
0066     return ith_wavefront(i, g, get(vertex_index, g));
0067 }
0068
0069 template < typename Graph, typename VertexIndexMap >
0070 typename graph_traits< Graph >::vertices_size_type max_wavefront(
0071     const Graph& g, VertexIndexMap index)
0072 {
0073     BOOST_USING_STD_MAX();
0074     typename graph_traits< Graph >::vertices_size_type b = 0;
0075     typename graph_traits< Graph >::vertex_iterator i, end;
0076     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0077         b = max BOOST_PREVENT_MACRO_SUBSTITUTION(
0078             b, ith_wavefront(*i, g, index));
0079     return b;
0080 }
0081
0082 template < typename Graph >
0083 typename graph_traits< Graph >::vertices_size_type max_wavefront(const Graph& g)
0084 {
0085     return max_wavefront(g, get(vertex_index, g));
0086 }
0087
0088 template < typename Graph, typename VertexIndexMap >
0089 double aver_wavefront(const Graph& g, VertexIndexMap index)
0090 {
0091     double b = 0;
0092     typename graph_traits< Graph >::vertex_iterator i, end;
0093     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0094         b += ith_wavefront(*i, g, index);
0095
0096     b /= num_vertices(g);
0097     return b;
0098 }
0099
0100 template < typename Graph > double aver_wavefront(const Graph& g)
0101 {
0102     return aver_wavefront(g, get(vertex_index, g));
0103 }
0104
0105 template < typename Graph, typename VertexIndexMap >
0106 double rms_wavefront(const Graph& g, VertexIndexMap index)
0107 {
0108     double b = 0;
0109     typename graph_traits< Graph >::vertex_iterator i, end;
0110     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0111         b += std::pow(double(ith_wavefront(*i, g, index)), 2.0);
0112
0113     b /= num_vertices(g);
0114
0115     return std::sqrt(b);
0116 }
0117
0118 template < typename Graph > double rms_wavefront(const Graph& g)
0119 {
0120     return rms_wavefront(g, get(vertex_index, g));
0121 }
0122
0123 } // namespace boost
0124
0125 #endif // BOOST_GRAPH_WAVEFRONT_HPP