1 // 2 //======================================================================= 3 // Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch) 4 // ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st) 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 // 11 12 #ifndef BOOST_GRAPH_WAVEFRONT_HPP 13 #define BOOST_GRAPH_WAVEFRONT_HPP 14 15 #include <boost/config.hpp> 16 #include <boost/graph/graph_traits.hpp> 17 #include <boost/detail/numeric_traits.hpp> 18 #include <boost/graph/bandwidth.hpp> 19 #include <boost/config/no_tr1/cmath.hpp> 20 #include <vector> 21 #include <algorithm> // for std::min and std::max 22 23 namespace boost { 24 25 template <typename Graph, typename VertexIndexMap> 26 typename graph_traits<Graph>::vertices_size_type ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,const Graph & g,VertexIndexMap index)27 ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i, 28 const Graph& g, 29 VertexIndexMap index) 30 { 31 typename graph_traits<Graph>::vertex_descriptor v, w; 32 typename graph_traits<Graph>::vertices_size_type b = 1; 33 typename graph_traits<Graph>::out_edge_iterator edge_it2, edge_it2_end; 34 typename graph_traits<Graph>::vertices_size_type index_i = index[i]; 35 std::vector<bool> rows_active(num_vertices(g), false); 36 37 rows_active[index_i] = true; 38 39 typename graph_traits<Graph>::vertex_iterator ui, ui_end; 40 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) 41 { 42 v = *ui; 43 if(index[v] <= index_i) 44 { 45 for (boost::tie(edge_it2, edge_it2_end) = out_edges(v, g); edge_it2 != edge_it2_end; ++edge_it2) 46 { 47 w = target(*edge_it2, g); 48 if( (index[w] >= index_i) && (!rows_active[index[w]]) ) 49 { 50 b++; 51 rows_active[index[w]] = true; 52 } 53 } 54 } 55 } 56 57 return b; 58 } 59 60 61 template <typename Graph> 62 typename graph_traits<Graph>::vertices_size_type ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,const Graph & g)63 ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i, 64 const Graph& g) 65 { 66 return ith_wavefront(i, g, get(vertex_index, g)); 67 } 68 69 70 template <typename Graph, typename VertexIndexMap> 71 typename graph_traits<Graph>::vertices_size_type max_wavefront(const Graph & g,VertexIndexMap index)72 max_wavefront(const Graph& g, VertexIndexMap index) 73 { 74 BOOST_USING_STD_MAX(); 75 typename graph_traits<Graph>::vertices_size_type b = 0; 76 typename graph_traits<Graph>::vertex_iterator i, end; 77 for (boost::tie(i, end) = vertices(g); i != end; ++i) 78 b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b, ith_wavefront(*i, g, index)); 79 return b; 80 } 81 82 template <typename Graph> 83 typename graph_traits<Graph>::vertices_size_type max_wavefront(const Graph & g)84 max_wavefront(const Graph& g) 85 { 86 return max_wavefront(g, get(vertex_index, g)); 87 } 88 89 90 template <typename Graph, typename VertexIndexMap> 91 double aver_wavefront(const Graph & g,VertexIndexMap index)92 aver_wavefront(const Graph& g, VertexIndexMap index) 93 { 94 double b = 0; 95 typename graph_traits<Graph>::vertex_iterator i, end; 96 for (boost::tie(i, end) = vertices(g); i != end; ++i) 97 b += ith_wavefront(*i, g, index); 98 99 b /= num_vertices(g); 100 return b; 101 } 102 103 template <typename Graph> 104 double aver_wavefront(const Graph & g)105 aver_wavefront(const Graph& g) 106 { 107 return aver_wavefront(g, get(vertex_index, g)); 108 } 109 110 111 template <typename Graph, typename VertexIndexMap> 112 double rms_wavefront(const Graph & g,VertexIndexMap index)113 rms_wavefront(const Graph& g, VertexIndexMap index) 114 { 115 double b = 0; 116 typename graph_traits<Graph>::vertex_iterator i, end; 117 for (boost::tie(i, end) = vertices(g); i != end; ++i) 118 b += std::pow(double ( ith_wavefront(*i, g, index) ), 2.0); 119 120 b /= num_vertices(g); 121 122 return std::sqrt(b); 123 } 124 125 template <typename Graph> 126 double rms_wavefront(const Graph & g)127 rms_wavefront(const Graph& g) 128 { 129 return rms_wavefront(g, get(vertex_index, g)); 130 } 131 132 133 } // namespace boost 134 135 #endif // BOOST_GRAPH_WAVEFRONT_HPP 136