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