]>
Commit | Line | Data |
---|---|---|
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 |