/usr/include/boost/graph/wavefront.hpp is in libboost1.55-dev 1.55.0+dfsg-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | //
//=======================================================================
// Copyright 2002 Marc Wintermantel (wintermantel@even-ag.ch)
// ETH Zurich, Center of Structure Technologies (www.imes.ethz.ch/st)
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//
#ifndef BOOST_GRAPH_WAVEFRONT_HPP
#define BOOST_GRAPH_WAVEFRONT_HPP
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/detail/numeric_traits.hpp>
#include <boost/graph/bandwidth.hpp>
#include <boost/config/no_tr1/cmath.hpp>
#include <vector>
#include <algorithm> // for std::min and std::max
namespace boost {
template <typename Graph, typename VertexIndexMap>
typename graph_traits<Graph>::vertices_size_type
ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,
const Graph& g,
VertexIndexMap index)
{
typename graph_traits<Graph>::vertex_descriptor v, w;
typename graph_traits<Graph>::vertices_size_type b = 1;
typename graph_traits<Graph>::out_edge_iterator edge_it2, edge_it2_end;
typename graph_traits<Graph>::vertices_size_type index_i = index[i];
std::vector<bool> rows_active(num_vertices(g), false);
rows_active[index_i] = true;
typename graph_traits<Graph>::vertex_iterator ui, ui_end;
for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
{
v = *ui;
if(index[v] <= index_i)
{
for (boost::tie(edge_it2, edge_it2_end) = out_edges(v, g); edge_it2 != edge_it2_end; ++edge_it2)
{
w = target(*edge_it2, g);
if( (index[w] >= index_i) && (!rows_active[index[w]]) )
{
b++;
rows_active[index[w]] = true;
}
}
}
}
return b;
}
template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
ith_wavefront(typename graph_traits<Graph>::vertex_descriptor i,
const Graph& g)
{
return ith_wavefront(i, g, get(vertex_index, g));
}
template <typename Graph, typename VertexIndexMap>
typename graph_traits<Graph>::vertices_size_type
max_wavefront(const Graph& g, VertexIndexMap index)
{
BOOST_USING_STD_MAX();
typename graph_traits<Graph>::vertices_size_type b = 0;
typename graph_traits<Graph>::vertex_iterator i, end;
for (boost::tie(i, end) = vertices(g); i != end; ++i)
b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b, ith_wavefront(*i, g, index));
return b;
}
template <typename Graph>
typename graph_traits<Graph>::vertices_size_type
max_wavefront(const Graph& g)
{
return max_wavefront(g, get(vertex_index, g));
}
template <typename Graph, typename VertexIndexMap>
double
aver_wavefront(const Graph& g, VertexIndexMap index)
{
double b = 0;
typename graph_traits<Graph>::vertex_iterator i, end;
for (boost::tie(i, end) = vertices(g); i != end; ++i)
b += ith_wavefront(*i, g, index);
b /= num_vertices(g);
return b;
}
template <typename Graph>
double
aver_wavefront(const Graph& g)
{
return aver_wavefront(g, get(vertex_index, g));
}
template <typename Graph, typename VertexIndexMap>
double
rms_wavefront(const Graph& g, VertexIndexMap index)
{
double b = 0;
typename graph_traits<Graph>::vertex_iterator i, end;
for (boost::tie(i, end) = vertices(g); i != end; ++i)
b += std::pow(double ( ith_wavefront(*i, g, index) ), 2.0);
b /= num_vertices(g);
return std::sqrt(b);
}
template <typename Graph>
double
rms_wavefront(const Graph& g)
{
return rms_wavefront(g, get(vertex_index, g));
}
} // namespace boost
#endif // BOOST_GRAPH_WAVEFRONT_HPP
|