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 <cmath>

    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 (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)

    41       {

    42         v = *ui;

    43           if(index[v] <= index_i)

    44             {

    45               for (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 (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 (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 (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