1 #ifndef GRAPHUTIL_H
2 #define GRAPHUTIL_H 1
3
4 #include "Histogram.h"
5 #include <boost/graph/graph_traits.hpp>
6 #include <iomanip>
7 #include <ostream>
8
9 using boost::graph_traits;
10
11 /** Return the number of vertices that have been marked as removed. */
12 template <typename Graph>
13 typename graph_traits<Graph>::vertices_size_type
num_vertices_removed(const Graph & g)14 num_vertices_removed(const Graph& g)
15 {
16 typedef graph_traits<Graph> GTraits;
17 typedef typename GTraits::vertices_size_type vertices_size_type;
18 typedef typename GTraits::vertex_iterator vertex_iterator;
19 vertices_size_type n = 0;
20 std::pair<vertex_iterator, vertex_iterator> vit = vertices(g);
21 for (vertex_iterator u = vit.first; u != vit.second; ++u)
22 if (get(vertex_removed, g, *u))
23 n++;
24 return n;
25 }
26
27 /** Print a histogram of the degree. */
28 template <typename Graph>
printHistogram(const Graph & g)29 Histogram printHistogram(const Graph& g)
30 {
31 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
32 Histogram h;
33 std::pair<vertex_iterator, vertex_iterator> vit = vertices(g);
34 for (vertex_iterator u = vit.first; u != vit.second; ++u) {
35 if (get(vertex_removed, g, *u))
36 continue;
37 h.insert(out_degree(*u, g));
38 }
39 return h;
40 }
41
42 /** Print statistics of the number of vertices and edges. */
43 template <typename Graph>
printGraphStats(std::ostream & out,const Graph & g)44 std::ostream& printGraphStats(std::ostream& out, const Graph& g)
45 {
46 using std::setprecision;
47 unsigned v = num_vertices(g) - num_vertices_removed(g);
48 unsigned e = num_edges(g);
49 out << "V=" << v << " E=" << e
50 << " E/V=" << setprecision(3) << (float)e / v << std::endl;
51
52 Histogram h = printHistogram(g);
53 unsigned n = h.size();
54 unsigned n0 = h.count(0), n1 = h.count(1), n234 = h.count(2, 4);
55 unsigned n5 = n - (n0 + n1 + n234);
56 return out <<
57 "Degree: " << h.barplot(h.maximum() + 1) << "\n"
58 " 01234\n"
59 "0: " << setprecision(2) << (float)100 * n0 / n << "% "
60 "1: " << setprecision(2) << (float)100 * n1 / n << "% "
61 "2-4: " << setprecision(2) << (float)100 * n234 / n << "% "
62 "5+: " << setprecision(2) << (float)100 * n5 / n << "% "
63 "max: " << h.maximum() << std::endl;
64 }
65
66 /** Pass graph statistics -- values only . */
67 template <typename Graph>
passGraphStatsVal(const Graph & g)68 std::vector<int> passGraphStatsVal(const Graph& g)
69 {
70 #if _SQL
71 Histogram h = printHistogram(g);
72 unsigned n = h.size(),
73 n0 = h.count(0),
74 n1 = h.count(1),
75 n234 = h.count(2, 4),
76 n5 = n - (n0 + n1 + n234);
77
78 return make_vector<int>()
79 << num_vertices(g) - num_vertices_removed(g)
80 << num_edges(g)
81 << (int)round(100.0 * n0 / n)
82 << (int)round(100.0 * n1 / n)
83 << (int)round(100.0 * n234 / n)
84 << (int)round(100.0 * n5 / n)
85 << h.maximum();
86 #else
87 (void)g;
88 return make_vector<int>();
89 #endif
90 }
91 #endif
92