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
27 template < typename Graph, typename VertexIndexMap >
ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,const Graph & g,VertexIndexMap index)28 typename graph_traits< Graph >::vertices_size_type ith_wavefront(
29 typename graph_traits< Graph >::vertex_descriptor i, 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);
47 edge_it2 != edge_it2_end; ++edge_it2)
48 {
49 w = target(*edge_it2, g);
50 if ((index[w] >= index_i) && (!rows_active[index[w]]))
51 {
52 b++;
53 rows_active[index[w]] = true;
54 }
55 }
56 }
57 }
58
59 return b;
60 }
61
62 template < typename Graph >
ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,const Graph & g)63 typename graph_traits< Graph >::vertices_size_type ith_wavefront(
64 typename graph_traits< Graph >::vertex_descriptor i, const Graph& g)
65 {
66 return ith_wavefront(i, g, get(vertex_index, g));
67 }
68
69 template < typename Graph, typename VertexIndexMap >
max_wavefront(const Graph & g,VertexIndexMap index)70 typename graph_traits< Graph >::vertices_size_type max_wavefront(
71 const Graph& g, VertexIndexMap index)
72 {
73 BOOST_USING_STD_MAX();
74 typename graph_traits< Graph >::vertices_size_type b = 0;
75 typename graph_traits< Graph >::vertex_iterator i, end;
76 for (boost::tie(i, end) = vertices(g); i != end; ++i)
77 b = max BOOST_PREVENT_MACRO_SUBSTITUTION(
78 b, ith_wavefront(*i, g, index));
79 return b;
80 }
81
82 template < typename Graph >
max_wavefront(const Graph & g)83 typename graph_traits< Graph >::vertices_size_type max_wavefront(const Graph& g)
84 {
85 return max_wavefront(g, get(vertex_index, g));
86 }
87
88 template < typename Graph, typename VertexIndexMap >
aver_wavefront(const Graph & g,VertexIndexMap index)89 double aver_wavefront(const Graph& g, VertexIndexMap index)
90 {
91 double b = 0;
92 typename graph_traits< Graph >::vertex_iterator i, end;
93 for (boost::tie(i, end) = vertices(g); i != end; ++i)
94 b += ith_wavefront(*i, g, index);
95
96 b /= num_vertices(g);
97 return b;
98 }
99
aver_wavefront(const Graph & g)100 template < typename Graph > double aver_wavefront(const Graph& g)
101 {
102 return aver_wavefront(g, get(vertex_index, g));
103 }
104
105 template < typename Graph, typename VertexIndexMap >
rms_wavefront(const Graph & g,VertexIndexMap index)106 double rms_wavefront(const Graph& g, VertexIndexMap index)
107 {
108 double b = 0;
109 typename graph_traits< Graph >::vertex_iterator i, end;
110 for (boost::tie(i, end) = vertices(g); i != end; ++i)
111 b += std::pow(double(ith_wavefront(*i, g, index)), 2.0);
112
113 b /= num_vertices(g);
114
115 return std::sqrt(b);
116 }
117
rms_wavefront(const Graph & g)118 template < typename Graph > double rms_wavefront(const Graph& g)
119 {
120 return rms_wavefront(g, get(vertex_index, g));
121 }
122
123 } // namespace boost
124
125 #endif // BOOST_GRAPH_WAVEFRONT_HPP
126