File: wavefront.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (135 lines) | stat: -rw-r--r-- 3,947 bytes parent folder | download | duplicates (11)
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