ceph/src/boost/boost/graph/wavefront.hpp

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