00001
00009 #ifndef __estimate
00010 #define __estimate
00011
00012 #include<algorithm>
00013 #include<ostream>
00014 #include<vector>
00015
00016 #include"graph.hpp"
00017 #include"util.hpp"
00018
00019 namespace graphgen{
00020
00025
00026 typedef unsigned long long histint;
00027
00029 typedef std::vector<histint> histogram;
00030
00032 typedef symmetric_matrix<histint> histomatrix;
00033
00034
00035
00039 qint estimate_degree_distribution( const undirected_graph& G, histogram& H );
00040
00044 qint estimate_degree_distribution( const undirected_graph& G, histogram& H, qint&qmax );
00045
00049 double calc_average_degree( const histogram& H );
00050
00051
00056 histogram& estimate_distance_distribution_local( const undirected_graph& G,
00057 vertex_type root, histogram& H );
00058
00063 histogram& estimate_distance_distribution( const undirected_graph& G, double density, histogram& H );
00064
00065
00069 histogram& estimate_distance_distribution( const undirected_graph& G, histogram& H );
00070
00071
00075 histogram& estimate_distance_distribution( const undirected_graph& G, histogram& H, unsigned int& diam );
00076
00077
00086 double estimate_clustering_coeff_local( const undirected_graph& G,
00087 const vertex_type v );
00088
00089
00095 double estimate_clustering_coeff( const undirected_graph& G );
00096
00097
00102 histomatrix& estimate_degree_correlation( const undirected_graph& G, histomatrix& H );
00103
00104
00118 double estimate_assortativity( const histogram& Pi, const histomatrix& Epsilon );
00119
00120
00121
00129 unsigned int estimate_number_triangles( const undirected_graph& );
00130
00134 void estimate_average_neighbor_degrees( const histomatrix&, std::vector<double>& );
00135
00139 void estimate_average_neighbor_degrees( const undirected_graph&, std::vector<double>& );
00140
00141
00142
00148 class estimator{
00149 protected:
00150
00151 int count;
00152
00158 virtual std::ostream& print( std::ostream& )const=0;
00159
00160 public:
00161 estimator() : count(0) {};
00162 virtual ~estimator(){};
00163
00168 virtual void measure( const undirected_graph& )=0;
00169
00171 int measurements(){ return count; }
00172
00178 estimator& operator<<( const undirected_graph& graph )
00179 {
00180 measure( graph );
00181 return *this;
00182 }
00183
00184 friend std::ostream&operator<<( std::ostream&, const estimator& );
00185 };
00186
00187 std::ostream&operator<<( std::ostream& out, const estimator& est );
00188
00189
00194 class degreedist : public estimator{
00196 histogram H;
00197
00199 histogram Hmax;
00200
00202 qint max_degree;
00203
00205 std::ostream&print( std::ostream& ) const;
00206
00207 public:
00215 degreedist( qint qmax ) : H(qmax+1, 0), Hmax(qmax+1, 0) {}
00216
00218 void measure( const undirected_graph& G ){
00219 qint qmax=0;
00220
00221 estimate_degree_distribution(G, H, qmax);
00222
00223 if( qmax>=Hmax.size() ) Hmax.resize(qmax+1);
00224
00225 Hmax[qmax]++;
00226 max_degree = std::max(qmax,max_degree);
00227
00228 count++;
00229 }
00230
00231 void operator()( const undirected_graph&G ){
00232 measure(G);
00233 }
00234
00236 const histogram& Hist() const{ return H; }
00237
00239 const histogram& MaxH() const{ return Hmax; }
00240
00242 const histint& operator[](qint q) const{ return H[q]; }
00243
00245 qint kmax() const{ return max_degree; }
00246 };
00247
00248
00256 class distancedist : public estimator{
00258 histogram D;
00260 histogram Diam;
00261
00263 std::ostream&print( std::ostream& ) const;
00264
00265 public:
00267 distancedist( int lmax )
00268 : D(lmax,0), Diam(lmax,0) {};
00269
00271 histint operator[]( unsigned int d ){ return D[d]; }
00272
00274 void measure( const undirected_graph& graph ){
00275 unsigned int diam = 0;
00276
00277 estimate_distance_distribution(graph, D, diam);
00278 if(diam>=Diam.size()) Diam.resize(diam+1);
00279 Diam[diam]++;
00280
00281 count++;
00282 }
00283 };
00284
00285
00289 class clusteringlocal : public estimator{
00290 double mean;
00291
00292 public:
00293 clusteringlocal();
00294
00295 void measure( const undirected_graph& graph, vertex_type vertex ){
00296 count++;
00297
00298 mean += estimate_clustering_coeff_local(graph, vertex);
00299 }
00300 };
00301
00302
00304 class clusteringglobal : protected clusteringlocal{
00305 double mean;
00306
00307 public:
00308 void measure( const undirected_graph& graph ){
00309 estimate_clustering_coeff(graph);
00310 }
00311 };
00312
00313
00314 int connected_components( const undirected_graph&G );
00315
00319 }
00320 #endif
00321