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