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