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   template <typename Graph, typename VertexIndexMap>
  27   typename graph_traits<Graph>::vertices_size_type
  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
  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
  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
  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
  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
 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
 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
 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