SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
gstat.h
Go to the documentation of this file.
1 // Graph Statistics
3 // statistics of a single snapshot of a graph
4 class TGStat;
5 typedef TPt<TGStat> PGStat;
7 
8 // statistics of a sequence of graph snapshots
9 class TGStatVec;
11 
13 // Statistics of a Sigle Graph
14 // Scalar statistics of the graph
15 typedef enum TGStatVal_ {
24 } TGStatVal;
25 
26 // Distribution statistics of the graph
27 typedef enum TGStatDistr_ {
30  gsdTriadPart, // triad participation
32 } TGStatDistr;
33 
36 class TGStat {
37 public:
38  static int NDiamRuns;
39  static int TakeSngVals;
40  typedef TQuad<TStr, TStr, TStr, TGpScaleTy> TPlotInfo; // file prefix, x label, y label, scale
41 public:
42  class TCmpByVal {
43  private:
45  bool SortAsc;
46  public:
47  TCmpByVal(TGStatVal SortBy, bool Asc) : ValCmp(SortBy), SortAsc(Asc) { }
48  bool operator () (const TGStat& GS1, const TGStat& GS2) const;
49  bool operator () (const PGStat& GS1, const PGStat& GS2) const;
50  };
51 private:
52  static const TFltPrV EmptyV;
54 public:
57  TIntFltH ValStatH; // scalar statistics
58  THash<TInt, TFltPrV> DistrStatH; // distribution statistics
59 public:
60  TGStat(const TSecTm& GraphTm = TSecTm(), const TStr& GraphName=TStr());
61  TGStat(const PNGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(), const TStr& GraphName=TStr());
62  TGStat(const PUNGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(), const TStr& GraphName=TStr());
63  TGStat(const PNEGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(), const TStr& GraphName=TStr());
64  template <class PGraph> TGStat(const PGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(), const TStr& GraphName=TStr()) {
65  TakeStat(Graph, Time, StatFSet, GraphName); }
66  TGStat(const TGStat& GStat);
67  TGStat(TSIn& SIn);
68  void Save(TSOut& SOut) const;
69  static PGStat New(const TSecTm& Time=TSecTm(), const TStr& GraphName=TStr()) {
70  return new TGStat(Time, GraphName); }
71  static PGStat New(const PNGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(),
72  const TStr& GraphNm=TStr()) { return new TGStat(Graph, Time, StatFSet, GraphNm); }
73  static PGStat New(const PUNGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(),
74  const TStr& GraphNm=TStr()) { return new TGStat(Graph, Time, StatFSet, GraphNm); }
75  static PGStat New(const PNEGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(),
76  const TStr& GraphNm=TStr()) { return new TGStat(Graph, Time, StatFSet, GraphNm); }
77  template <class PGraph> PGStat New(const PGraph& Graph, const TSecTm& Time, TFSet StatFSet=TFSet(),
78  const TStr& GraphNm=TStr()) { return new TGStat(Graph, Time, StatFSet, GraphNm); }
79  static PGStat Load(TSIn& SIn) { return new TGStat(SIn); }
80  PGStat Clone() const { return new TGStat(*this); }
81  TGStat& operator = (const TGStat& GStat);
82  bool operator == (const TGStat& GStat) const;
83  bool operator < (const TGStat& GStat) const;
84 
85  int GetYear() const { return Time.GetYearN(); }
86  int GetMonth() const { return Time.GetMonthN(); }
87  int GetDay() const { return Time.GetDayN(); }
88  int GetHour() const { return Time.GetHourN(); }
89  int GetMin() const { return Time.GetMinN(); }
90  int GetSec() const { return Time.GetSecN(); }
91  TStr GetTmStr() const { return Time.GetStr(); }
92  void SetTm(const TSecTm& GraphTm) { Time = GraphTm; }
93  TStr GetNm() const { return GraphNm; }
94  void SetNm(const TStr& GraphName) { GraphNm=GraphName; }
95  int GetTime(const TTmUnit& TimeUnit) const { return Time.GetInUnits(TimeUnit); }
96 
97  int GetVals() const { return ValStatH.Len(); }
98  bool HasVal(const TGStatVal& StatVal) const;
99  double GetVal(const TGStatVal& StatVal) const;
100  void SetVal(const TGStatVal& StatVal, const double& Val);
101  int GetDistrs() const { return DistrStatH.Len(); }
102  bool HasDistr(const TGStatDistr& Distr) const { return DistrStatH.IsKey(Distr); }
103  const TFltPrV& GetDistr(const TGStatDistr& Distr) const;
104  void GetDistr(const TGStatDistr& Distr, TFltPrV& FltPrV) const;
105  void SetDistr(const TGStatDistr& Distr, const TFltPrV& FltPrV);
106 
107  int GetNodes() const { return (int) GetVal(gsvNodes); }
108  int GetEdges() const { return (int) GetVal(gsvEdges); }
109 
110  void TakeStat(const PNGraph& Graph, const TSecTm& Time, TFSet StatFSet, const TStr& GraphName);
111  void TakeStat(const PUNGraph& Graph, const TSecTm& Time, TFSet StatFSet, const TStr& GraphName);
112  template <class PGraph> void TakeStat(const PGraph& Graph, const TSecTm& Time, TFSet StatFSet, const TStr& GraphName);
113  template <class PGraph> void TakeBasicStat(const PGraph& Graph, const bool& IsMxWcc=false);
114  template <class PGraph> void TakeBasicStat(const PGraph& Graph, TFSet FSet, const bool& IsMxWcc=false);
115  template <class PGraph> void TakeSccStat(const PGraph& Graph, TFSet StatFSet);
116  template <class PGraph> void TakeBccStat(const PGraph& Graph, TFSet StatFSet);
117  template <class PGraph> void TakeDegDistr(const PGraph& Graph);
118  template <class PGraph> void TakeDegDistr(const PGraph& Graph, TFSet StatFSet);
119  template <class PGraph> void TakeDiam(const PGraph& Graph, const bool& IsMxWcc=false);
120  template <class PGraph> void TakeDiam(const PGraph& Graph, TFSet StatFSet, const bool& IsMxWcc=false);
121  template <class PGraph> void TakeConnComp(const PGraph& Graph);
122  template <class PGraph> void TakeConnComp(const PGraph& Graph, TFSet StatFSet);
123  template <class PGraph> void TakeClustCf(const PGraph& Graph, const int& SampleNodes=-1);
124  template <class PGraph> void TakeTriadPart(const PGraph& Graph);
125  void TakeSpectral(const PNGraph& Graph, const int _TakeSngVals = -1);
126  void TakeSpectral(const PNGraph& Graph, TFSet StatFSet, int _TakeSngVals = -1);
127 
128  void Plot(const TGStatDistr& Distr, const TStr& FNmPref, TStr Desc=TStr(), bool PowerFit=false) const;
129  void Plot(const TFSet& FSet, const TStr& FNmPref, const TStr& Desc=TStr(), bool PowerFit=false) const;
130  void PlotAll(const TStr& FNmPref, TStr Desc=TStr(), bool PowerFit=false) const;
131  void DumpValStat();
132 
133  void AvgGStat(const PGStatVec& GStatVec, const bool& ClipAt1=false);
134  void AvgGStat(const TGStatV& GStatV, const bool& ClipAt1=false);
135 
136  // take graph statistics (see TTakeGStat)
137  static TStr GetDistrStr(const TGStatDistr& Distr);
138  static TStr GetValStr(const TGStatVal& Val);
139  static TPlotInfo GetPlotInfo(const TGStatVal& Val);
140  static TPlotInfo GetPlotInfo(const TGStatDistr& Distr);
141  static TFSet NoStat();
142  static TFSet BasicStat();
143  static TFSet DegDStat();
144  static TFSet NoDiamStat();
145  static TFSet NoDistrStat();
146  static TFSet NoSvdStat();
147  static TFSet AllStat();
148 
149  friend class TCmpByVal;
150  friend class TPt<TGStat>;
151 };
152 
153 //#//////////////////////////////////////////////
155 class TGStatVec {
156 public:
158 private:
162  TGStatV GStatV; // each snapshot (TVec<PGStat>)
163 public:
164  TGStatVec(const TTmUnit& _TmUnit=tmu1Sec);
165  TGStatVec(const TTmUnit& _TmUnit, const TFSet& TakeGrowthStat);
166  TGStatVec(const TGStatVec& GStat);
167  static PGStatVec New(const TTmUnit& _TmUnit=tmu1Sec);
168  static PGStatVec New(const TTmUnit& _TmUnit, const TFSet& TakeGrowthStat);
169  static PGStatVec Load(TSIn& SIn) { return new TGStatVec(SIn); }
170  TGStatVec(TSIn& SIn);
171  void Save(TSOut& SOut) const;
172  TGStatVec& operator = (const TGStatVec& GStat);
173 
174  PGStat Add();
175  PGStat Add(const TSecTm& Time, const TStr& GraphNm=TStr());
176  void Add(const PGStat& Growth) { GStatV.Add(Growth); }
177  void Add(const PNGraph& Graph, const TSecTm& Time, const TStr& GraphNm=TStr());
178  void Add(const PUNGraph& Graph, const TSecTm& Time, const TStr& GraphNm=TStr());
179  void Add(const PNEGraph& Graph, const TSecTm& Time, const TStr& GraphNm=TStr());
180  void Clr() { GStatV.Clr(); }
181  void Sort(const TGStatVal& SortBy=gsvNodes, const bool& Asc=true);
182 
183  int Len() const { return GStatV.Len(); }
184  bool Empty() const { return GStatV.Empty(); }
185  PGStat operator[](const int& ValN) const { return GStatV[ValN]; }
186  PGStat At(const int& ValN) const { return GStatV[ValN]; }
187  PGStat Last() const { return GStatV.Last(); }
188  const TGStatV& GetGStatV() const { return GStatV; }
189  int GetTime(const int& ValN) const { return At(ValN)->GetTime(TmUnit); }
190 
191  void Del(const int& ValN) { GStatV.Del(ValN); }
192  void DelLast() { GStatV.DelLast(); }
193  void DelBefore(const TSecTm& Tm);
194  void DelAfter(const TSecTm& Tm);
195  void DelSmallNodes(const int& MinNodes);
196 
197  void SetTmUnit(const TTmUnit& TimeUnit) { TmUnit = TimeUnit; }
198  TTmUnit GetTmUnit() const { return TmUnit; }
199  void SetTakeStat(const TFSet& TakeStatSet) { StatFSet = TakeStatSet; }
200  bool HasVal(const TGStatVal& Stat) const { return StatFSet.In(Stat); }
201  bool HasDistr(const TGStatDistr& Stat) const { return StatFSet.In(Stat); }
202 
203  void GetValV(const TGStatVal& XVal, const TGStatVal& YVal, TFltPrV& ValV) const;
204  PGStat GetAvgGStat(const bool& ClipAt1=false);
205 
206  void Plot(const TGStatVal& XVal, const TGStatVal& YVal, const TStr& OutFNm, TStr& Desc,
207  const TGpScaleTy& Scale=gpsAuto, const bool& PowerFit=false) const;
208  void PlotAllVsX(const TGStatVal& XVal, const TStr& OutFNm, TStr Desc=TStr(), const TGpScaleTy& Scale=gpsAuto, const bool& PowerFit=false) const;
209  void ImposeDistr(const TGStatDistr& Distr, const TStr& FNmPref, TStr Desc=TStr(), const bool& ExpBin=false,
210  const bool& PowerFit=false, const TGpSeriesTy& PlotWith=gpwLinesPoints, const TStr& Style="") const;
211 
212  void SaveTxt(const TStr& FNmPref, const TStr& Desc) const;
213  friend class TPt<TGStatVec>;
214 };
215 
217 // Implementation
218 template <class PGraph>
219 void TGStat::TakeStat(const PGraph& Graph, const TSecTm& _Time, TFSet StatFSet, const TStr& GraphName) {
220  printf("**TakeStat: G(%u, %u)\n", Graph->GetNodes(), Graph->GetEdges());
221  TExeTm ExeTm, FullTm;
222  Time = _Time;
223  GraphNm = GraphName;
224  if (StatFSet.In(gsvNone)) { return; }
225  TakeBasicStat(Graph, false);
226  TakeSccStat(Graph, StatFSet);
227  TakeBccStat(Graph, StatFSet);
228  if (StatFSet.In(gsdWcc)) {
229  PGraph WccG = TSnap::GetMxWcc(Graph);
230  TakeBasicStat(WccG, true);
231  SetVal(gsvWccSize, WccG->GetNodes()/double(Graph->GetNodes()));
232  }
233  // degrees
234  TakeDegDistr(Graph, StatFSet);
235  if (StatFSet.In(gsvFullDiam) || StatFSet.In(gsvEffDiam) || StatFSet.In(gsdHops) ||
236  StatFSet.In(gsvEffWccDiam) || StatFSet.In(gsdWccHops) || StatFSet.In(gsdWcc) || StatFSet.In(gsdScc) ||
237  StatFSet.In(gsdClustCf) || StatFSet.In(gsvClustCf) || StatFSet.In(gsdTriadPart)) {
238  PNGraph NGraph = TSnap::ConvertGraph<PNGraph>(Graph, true);
239  // diameter
240  TakeDiam(NGraph, StatFSet, false);
241  // components
242  TakeConnComp(NGraph, StatFSet);
243  // spectral
244  TakeSpectral(NGraph, StatFSet, -1);
245  // clustering coeffient
246  if (StatFSet.In(gsdClustCf) || StatFSet.In(gsvClustCf)) {
247  TakeClustCf(NGraph); }
248  if (StatFSet.In(gsdTriadPart)) {
249  TakeTriadPart(NGraph); }
250  if (StatFSet.In(gsvFullDiam) || StatFSet.In(gsvEffWccDiam)) {
251  TakeDiam(TSnap::GetMxWcc(NGraph), StatFSet, true); }
252  printf("**[%s]\n", FullTm.GetTmStr());
253  }
254 }
255 
256 template <class PGraph>
257 void TGStat::TakeBasicStat(const PGraph& Graph, const bool& IsMxWcc) {
258  TakeBasicStat(Graph, TFSet() | gsvBiDirEdges | gsvWccBiDirEdges, IsMxWcc);
259 }
260 
261 template <class PGraph>
262 void TGStat::TakeBasicStat(const PGraph& Graph, TFSet FSet, const bool& IsMxWcc) {
263  TExeTm ExeTm;
264  if (! IsMxWcc) {
265  // gsvNodes, gsvZeroNodes, gsvNonZNodes, gsvSrcNodes, gsvDstNodes,
266  // gsvEdges, gsvUniqEdges, gsvBiDirEdges
267  printf("basic...");
268  const int Nodes = Graph->GetNodes();
269  SetVal(gsvNodes, Nodes);
272  SetVal(gsvSrcNodes, Nodes - TSnap::CntOutDegNodes(Graph, 0));
273  SetVal(gsvDstNodes, Nodes - TSnap::CntInDegNodes(Graph, 0));
274  SetVal(gsvEdges, Graph->GetEdges());
275  if (! Graph->HasFlag(gfMultiGraph)) { SetVal(gsvUniqEdges, Graph->GetEdges()); }
276  else { SetVal(gsvUniqEdges, TSnap::CntUniqDirEdges(Graph)); }
277  if (FSet.In(gsvBiDirEdges)) {
278  if (Graph->HasFlag(gfDirected)) { SetVal(gsvBiDirEdges, TSnap::CntUniqBiDirEdges(Graph)); }
279  else { SetVal(gsvUniqEdges, GetVal(gsvEdges)); }
280  }
281  printf("[%s] ", ExeTm.GetTmStr());
282  } else {
283  // gsvWccNodes, gsvWccSrcNodes, gsvWccDstNodes, gsvWccEdges, gsvWccUniqEdges, gsvWccBiDirEdges
284  printf("basic wcc...");
285  const int Nodes = Graph->GetNodes();
286  SetVal(gsvWccNodes, Nodes);
287  SetVal(gsvWccSrcNodes, Nodes - TSnap::CntOutDegNodes(Graph, 0));
288  SetVal(gsvWccDstNodes, Nodes - TSnap::CntInDegNodes(Graph, 0));
289  SetVal(gsvWccEdges, Graph->GetEdges());
290  if (! Graph->HasFlag(gfMultiGraph)) { SetVal(gsvWccUniqEdges, Graph->GetEdges()); }
292  if (FSet.In(gsvBiDirEdges)) {
293  if (Graph->HasFlag(gfDirected)) { SetVal(gsvWccBiDirEdges, TSnap::CntUniqBiDirEdges(Graph)); }
294  else { SetVal(gsvUniqEdges, GetVal(gsvEdges)); }
295  }
296  printf("[%s] ", ExeTm.GetTmStr());
297  }
298 }
299 
300 template <class PGraph>
301 void TGStat::TakeDegDistr(const PGraph& Graph) {
302  TakeDegDistr(Graph, TFSet() | gsdInDeg | gsdOutDeg);
303 }
304 
305 template <class PGraph>
306 void TGStat::TakeDegDistr(const PGraph& Graph, TFSet StatFSet) {
307  TExeTm ExeTm;
308  // degree distribution
309  if (StatFSet.In(gsdOutDeg) || StatFSet.In(gsdOutDeg)) {
310  printf("deg:"); }
311  if (StatFSet.In(gsdInDeg)) {
312  printf("-in");
313  TFltPrV& InDegV = DistrStatH.AddDat(gsdInDeg);
314  TSnap::GetInDegCnt(Graph, InDegV);
315  }
316  if (StatFSet.In(gsdOutDeg)) {
317  printf("-out");
318  TFltPrV& OutDegV = DistrStatH.AddDat(gsdOutDeg);
319  TSnap::GetOutDegCnt(Graph, OutDegV);
320  }
321  if (StatFSet.In(gsdOutDeg) || StatFSet.In(gsdOutDeg)) {
322  printf("[%s] ", ExeTm.GetTmStr()); }
323 }
324 
325 template <class PGraph>
326 void TGStat::TakeDiam(const PGraph& Graph, const bool& IsMxWcc) {
327  TakeDiam(Graph, TFSet() | gsvFullDiam | gsvEffDiam | gsdHops |
328  gsvEffWccDiam| gsdWccHops, IsMxWcc);
329 }
330 
331 template <class PGraph>
332 void TGStat::TakeDiam(const PGraph& Graph, TFSet StatFSet, const bool& IsMxWcc) {
333  TExeTm ExeTm;
334  if (! IsMxWcc) {
335  if (StatFSet.In(gsvFullDiam) || StatFSet.In(gsvEffDiam) || StatFSet.In(gsdHops)) {
336  printf("anf:%druns...", NDiamRuns); }
337  //bool Line=false;
338  if (StatFSet.In(gsvEffDiam) || StatFSet.In(gsdHops)) {
339  TMom DiamMom; ExeTm.Tick();
340  TIntFltKdV DistNbrsV;
341  for (int r = 0; r < NDiamRuns; r++) {
342  TSnap::GetAnf(Graph, DistNbrsV, -1, false, 32);
343  DiamMom.Add(TSnap::TSnapDetail::CalcEffDiam(DistNbrsV, 0.9));
344  printf(".");
345  }
346  DiamMom.Def();
347  SetVal(gsvEffDiam, DiamMom.GetMean());
348  SetVal(gsvEffDiamDev, DiamMom.GetSDev());
349  TFltPrV& HopsV = DistrStatH.AddDat(gsdHops);
350  HopsV.Gen(DistNbrsV.Len(), 0);
351  for (int i = 0; i < DistNbrsV.Len(); i++) {
352  HopsV.Add(TFltPr(DistNbrsV[i].Key(), DistNbrsV[i].Dat)); }
353  printf(" anf-eff %.1f[%s]", DiamMom.GetMean(), ExeTm.GetTmStr());
354  //Line=true;
355  }
356  } else {
357  if (StatFSet.In(gsvEffWccDiam) || StatFSet.In(gsdWccHops)) { printf("wcc diam..."); }
358  //bool Line=false;
359  if (StatFSet.In(gsvFullDiam)) {
360  TMom DiamMom; ExeTm.Tick();
361  for (int r = 0; r < NDiamRuns; r++) {
362  DiamMom.Add(TSnap::GetBfsFullDiam(Graph, 1, false));
363  printf("."); }
364  DiamMom.Def();
365  SetVal(gsvFullDiam, DiamMom.GetMean());
366  SetVal(gsvFullDiamDev, DiamMom.GetSDev());
367  printf(" bfs-full %g[%s]", DiamMom.GetMean(), ExeTm.GetTmStr());
368  //Line=true;
369  }
370  if (StatFSet.In(gsvEffWccDiam) || StatFSet.In(gsdWccHops)) {
371  TMom DiamMom; ExeTm.Tick();
372  TIntFltKdV DistNbrsV;
373  for (int r = 0; r < NDiamRuns; r++) {
374  TSnap::GetAnf(Graph, DistNbrsV, -1, false, 32);
375  DiamMom.Add(TSnap::TSnapDetail::CalcEffDiam(DistNbrsV, 0.9));
376  printf(".");
377  }
378  DiamMom.Def();
379  SetVal(gsvEffWccDiam, DiamMom.GetMean());
380  SetVal(gsvEffWccDiamDev, DiamMom.GetSDev());
381  TFltPrV& WccHopsV = DistrStatH.AddDat(gsdWccHops);
382  WccHopsV.Gen(DistNbrsV.Len(), 0);
383  for (int i = 0; i < DistNbrsV.Len(); i++) {
384  WccHopsV.Add(TFltPr(DistNbrsV[i].Key(), DistNbrsV[i].Dat)); }
385  printf(" anf-wcceff %.1f[%s]", DiamMom.GetMean(), ExeTm.GetTmStr());
386  //Line=true;
387  }
388  }
389 }
390 
391 template <class PGraph>
392 void TGStat::TakeConnComp(const PGraph& Graph) {
393  TakeConnComp(Graph, TFSet() | gsdWcc | gsdScc);
394 }
395 
396 template <class PGraph>
397 void TGStat::TakeConnComp(const PGraph& Graph, TFSet StatFSet) {
398  TExeTm ExeTm;
399  if (StatFSet.In(gsdWcc)) {
400  printf("wcc...");
401  TIntPrV WccSzCntV1;
402  TSnap::GetWccSzCnt(Graph, WccSzCntV1);
403  TFltPrV& WccSzCntV = DistrStatH.AddDat(gsdWcc);
404  WccSzCntV.Gen(WccSzCntV1.Len(), 0);
405  for (int i = 0; i < WccSzCntV1.Len(); i++)
406  WccSzCntV.Add(TFltPr(WccSzCntV1[i].Val1(), WccSzCntV1[i].Val2()));
407  }
408  if (StatFSet.In(gsdScc)) {
409  printf("scc...");
410  TIntPrV SccSzCntV1;
411  TSnap::GetSccSzCnt(Graph, SccSzCntV1);
412  TFltPrV& SccSzCntV = DistrStatH.AddDat(gsdScc);
413  SccSzCntV.Gen(SccSzCntV1.Len(), 0);
414  for (int i = 0; i < SccSzCntV1.Len(); i++)
415  SccSzCntV.Add(TFltPr(SccSzCntV1[i].Val1(), SccSzCntV1[i].Val2()));
416  }
417  if (StatFSet.In(gsdWcc) || StatFSet.In(gsdScc)) { printf("[%s] ", ExeTm.GetTmStr()); }
418 }
419 
420 template <class PGraph>
421 void TGStat::TakeSccStat(const PGraph& Graph, TFSet StatFSet) {
422  TExeTm ExeTm;
423  if (StatFSet.In(gsvSccNodes) || StatFSet.In(gsvSccEdges) || StatFSet.In(gsvSccSize)) {
424  printf("scc...");
425  PGraph SccG = TSnap::GetMxScc(Graph);
426  SetVal(gsvSccNodes, SccG->GetNodes());
427  SetVal(gsvSccEdges, SccG->GetEdges());
428  SetVal(gsvSccSize, SccG->GetNodes()/double(Graph->GetNodes()));
429  printf("[%s] ", ExeTm.GetTmStr());
430  }
431 }
432 
433 template <class PGraph>
434 void TGStat::TakeBccStat(const PGraph& Graph, TFSet StatFSet) {
435  TExeTm ExeTm;
436  if (StatFSet.In(gsvBccNodes) || StatFSet.In(gsvBccEdges) || StatFSet.In(gsvBccSize)) {
437  printf("bcc...");
438  PGraph BccG = TSnap::GetMxBiCon(Graph);
439  SetVal(gsvBccNodes, BccG->GetNodes());
440  SetVal(gsvBccEdges, BccG->GetEdges());
441  SetVal(gsvBccSize, BccG->GetNodes()/double(Graph->GetNodes()));
442  printf("[%s] ", ExeTm.GetTmStr());
443  }
444 }
445 
446 template <class PGraph>
447 void TGStat::TakeClustCf(const PGraph& Graph, const int& SampleNodes) {
448  TExeTm ExeTm;
449  printf("clustcf...");
450  TFltPrV& ClustCfV = DistrStatH.AddDat(gsdClustCf);
451  int64 Open, Close;
452  const double ClustCf = TSnap::GetClustCf(Graph, ClustCfV, Close, Open, SampleNodes);
453  SetVal(gsvClustCf, ClustCf);
454  SetVal(gsvOpenTriads, static_cast<double>(Open));
455  SetVal(gsvClosedTriads, static_cast<double>(Close));
456  printf("[%s] ", ExeTm.GetTmStr());
457 }
458 
459 template <class PGraph>
460 void TGStat::TakeTriadPart(const PGraph& Graph) {
461  TExeTm ExeTm;
462  printf("triadparticip...");
463  TFltPrV& TriadCntV = DistrStatH.AddDat(gsdTriadPart);
464  TIntPrV CntV;
465  TSnap::GetTriadParticip(Graph, CntV);
466  TriadCntV.Gen(CntV.Len(), 0);
467  for (int i = 0; i < CntV.Len(); i++) {
468  TriadCntV.Add(TFltPr(CntV[i].Val1(), CntV[i].Val2()));
469  }
470  printf("[%s] ", ExeTm.GetTmStr());
471 }
Definition: bd.h:440
bool HasVal(const TGStatVal &Stat) const
Definition: gstat.h:200
PGStat GetAvgGStat(const bool &ClipAt1=false)
Definition: gstat.cpp:523
static const TFltPrV EmptyV
Definition: gstat.h:52
PUNGraph GetMxBiCon(const PUNGraph &Graph, const bool &RenumberNodes)
Returns a graph representing the largest bi-connected component on an undirected Graph.
Definition: cncom.cpp:126
TStr GetNm() const
Definition: gstat.h:93
PGStat Add()
Definition: gstat.cpp:449
int GetMinN() const
Definition: tm.cpp:602
static TStr GetValStr(const TGStatVal &Val)
Definition: gstat.cpp:307
Definition: tm.h:355
static PGStat New(const PNGraph &Graph, const TSecTm &Time, TFSet StatFSet=TFSet(), const TStr &GraphNm=TStr())
Definition: gstat.h:71
void ImposeDistr(const TGStatDistr &Distr, const TStr &FNmPref, TStr Desc=TStr(), const bool &ExpBin=false, const bool &PowerFit=false, const TGpSeriesTy &PlotWith=gpwLinesPoints, const TStr &Style="") const
Definition: gstat.cpp:559
void GetOutDegCnt(const PGraph &Graph, TIntPrV &DegToCntV)
Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree) ...
Definition: alg.h:201
int GetBfsFullDiam(const PGraph &Graph, const int &NTestNodes, const bool &IsDir=false)
Returns the (approximation of the) Diameter (maximum shortest path length) of a graph (by performing ...
Definition: bfsdfs.h:407
TStr GraphNm
Definition: gstat.h:56
int GetYearN() const
Definition: tm.cpp:560
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
PGraph GetMxWcc(const PGraph &Graph)
Returns a graph representing the largest weakly connected component on an input Graph.
Definition: cncom.h:452
bool Empty() const
Definition: gstat.h:184
unsigned int uint
Definition: bd.h:11
static TFSet AllStat()
Definition: gstat.cpp:401
void TakeSpectral(const PNGraph &Graph, const int _TakeSngVals=-1)
Definition: gstat.cpp:169
void Save(TSOut &SOut) const
Definition: gstat.cpp:434
static PGStat New(const PNEGraph &Graph, const TSecTm &Time, TFSet StatFSet=TFSet(), const TStr &GraphNm=TStr())
Definition: gstat.h:75
bool operator==(const TGStat &GStat) const
Definition: gstat.cpp:57
Definition: gstat.h:28
static TFSet NoDiamStat()
Definition: gstat.cpp:388
enum TGStatDistr_ TGStatDistr
Definition: bits.h:119
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void TakeConnComp(const PGraph &Graph)
Definition: gstat.h:392
void PlotAllVsX(const TGStatVal &XVal, const TStr &OutFNm, TStr Desc=TStr(), const TGpScaleTy &Scale=gpsAuto, const bool &PowerFit=false) const
Definition: gstat.cpp:548
void GetAnf(const PGraph &Graph, const int &SrcNId, TIntFltKdV &DistNbrsV, const int &MxDist, const bool &IsDir, const int &NApprox=32)
Definition: anf.h:204
static TFSet NoDistrStat()
Definition: gstat.cpp:392
TTmUnit TmUnit
Definition: gstat.h:160
void AvgGStat(const PGStatVec &GStatVec, const bool &ClipAt1=false)
Definition: gstat.cpp:243
TGStatVec & operator=(const TGStatVec &GStat)
Definition: gstat.cpp:440
TCRef CRef
Definition: gstat.h:159
uint GetInUnits(const TTmUnit &TmUnit) const
Definition: tm.cpp:650
TSecTm Time
Definition: gstat.h:55
TVec< PGStat > TGStatV
Definition: gstat.h:6
static TStr GetDistrStr(const TGStatDistr &Distr)
Definition: gstat.cpp:289
Definition: xmath.h:129
int GetTime(const TTmUnit &TimeUnit) const
Definition: gstat.h:95
int CntUniqDirEdges(const PGraph &Graph)
Counts unique directed edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via a directe...
Definition: alg.h:301
bool HasDistr(const TGStatDistr &Distr) const
Definition: gstat.h:102
TGStatV GStatV
Definition: gstat.h:162
Definition: gnuplot.h:7
void Sort(const TGStatVal &SortBy=gsvNodes, const bool &Asc=true)
Definition: gstat.cpp:483
bool HasDistr(const TGStatDistr &Stat) const
Definition: gstat.h:201
void GetSccSzCnt(const PGraph &Graph, TIntPrV &SccSzCnt)
Returns a distribution of strongly connected component sizes.
Definition: cncom.h:420
static PGStat New(const PUNGraph &Graph, const TSecTm &Time, TFSet StatFSet=TFSet(), const TStr &GraphNm=TStr())
Definition: gstat.h:73
int GetMin() const
Definition: gstat.h:89
double GetSDev() const
Definition: xmath.h:242
void SetTakeStat(const TFSet &TakeStatSet)
Definition: gstat.h:199
int GetMonthN() const
Definition: tm.cpp:566
int GetNodes() const
Definition: gstat.h:107
void DumpValStat()
Definition: gstat.cpp:235
Definition: tm.h:12
int Len() const
Definition: gstat.h:183
Definition: fl.h:58
void DelLast()
Definition: gstat.h:192
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
Definition: gstat.h:29
have explicit edges (multigraph): TNEGraph, TNodeEdgeNet
Definition: gbase.h:14
enum TGStatVal_ TGStatVal
void SaveTxt(const TStr &FNmPref, const TStr &Desc) const
Definition: gstat.cpp:584
Definition: gstat.h:28
bool operator()(const TGStat &GS1, const TGStat &GS2) const
Definition: gstat.cpp:7
Graph Statistics Sequence.
Definition: gstat.h:155
int GetTime(const int &ValN) const
Definition: gstat.h:189
const char * GetTmStr() const
Definition: tm.h:370
static TPlotInfo GetPlotInfo(const TGStatVal &Val)
Definition: gstat.cpp:351
Definition: gstat.h:28
void TakeStat(const PNGraph &Graph, const TSecTm &Time, TFSet StatFSet, const TStr &GraphName)
Definition: gstat.cpp:105
TCmpByVal(TGStatVal SortBy, bool Asc)
Definition: gstat.h:47
Definition: gstat.h:16
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
Definition: gstat.h:16
void TakeTriadPart(const PGraph &Graph)
Definition: gstat.h:460
void GetInDegCnt(const PGraph &Graph, TIntPrV &DegToCntV)
Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree) ...
Definition: alg.h:179
void Add(const TFlt &Val, const TFlt &Wgt=1)
Definition: xmath.h:217
THash< TInt, TFltPrV > DistrStatH
Definition: gstat.h:58
Statistics of a Graph Snapshot.
Definition: gstat.h:36
void DelBefore(const TSecTm &Tm)
Definition: gstat.cpp:487
void TakeClustCf(const PGraph &Graph, const int &SampleNodes=-1)
Definition: gstat.h:447
Definition: gstat.h:17
TCRef CRef
Definition: gstat.h:53
static PGStat New(const TSecTm &Time=TSecTm(), const TStr &GraphName=TStr())
Definition: gstat.h:69
TIntFltH ValStatH
Definition: gstat.h:57
TFSet StatFSet
Definition: gstat.h:161
int GetSecN() const
Definition: tm.cpp:608
Definition: gstat.h:16
void DelSmallNodes(const int &MinNodes)
Definition: gstat.cpp:503
PGStat operator[](const int &ValN) const
Definition: gstat.h:185
TTmUnit GetTmUnit() const
Definition: gstat.h:198
bool HasVal(const TGStatVal &StatVal) const
Definition: gstat.cpp:75
TGStat(const PGraph &Graph, const TSecTm &Time, TFSet StatFSet=TFSet(), const TStr &GraphName=TStr())
Definition: gstat.h:64
void TakeBccStat(const PGraph &Graph, TFSet StatFSet)
Definition: gstat.h:434
int GetHourN() const
Definition: tm.cpp:596
void Del(const int &ValN)
Definition: gstat.h:191
int GetDayN() const
Definition: tm.cpp:578
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
int GetEdges() const
Definition: gstat.h:108
PGStat New(const PGraph &Graph, const TSecTm &Time, TFSet StatFSet=TFSet(), const TStr &GraphNm=TStr())
Definition: gstat.h:77
int GetVals() const
Definition: gstat.h:97
TGStatVec(const TTmUnit &_TmUnit=tmu1Sec)
Definition: gstat.cpp:411
void Tick()
Definition: tm.h:364
bool SortAsc
Definition: gstat.h:45
static uint MinNodesEdges
Definition: gstat.h:157
int CntUniqBiDirEdges(const PGraph &Graph)
Counts unique bidirectional edges in the graph Graph. Edge is bidirectional if there exist directed e...
Definition: alg.h:316
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
static TFSet NoSvdStat()
Definition: gstat.cpp:396
void SetVal(const TGStatVal &StatVal, const double &Val)
Definition: gstat.cpp:88
Definition: fl.h:128
void Save(TSOut &SOut) const
Definition: gstat.cpp:42
int CntInDegNodes(const PGraph &Graph, const int &NodeInDeg)
Returns the number of nodes with in-degree NodeInDeg.
Definition: alg.h:87
static int NDiamRuns
Definition: gstat.h:38
PGStat Clone() const
Definition: gstat.h:80
int GetHour() const
Definition: gstat.h:88
int GetYear() const
Definition: gstat.h:85
void Add(const PGStat &Growth)
Definition: gstat.h:176
static TFSet NoStat()
Definition: gstat.cpp:376
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
TStr GetTmStr() const
Definition: gstat.h:91
Definition: tm.h:81
void SetNm(const TStr &GraphName)
Definition: gstat.h:94
double CalcEffDiam(const TIntFltKdV &DistNbrsCdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function...
Definition: anf.cpp:7
void Clr()
Definition: gstat.h:180
PGStat At(const int &ValN) const
Definition: gstat.h:186
Definition: gstat.h:28
int GetSec() const
Definition: gstat.h:90
const TGStatV & GetGStatV() const
Definition: gstat.h:188
void PlotAll(const TStr &FNmPref, TStr Desc=TStr(), bool PowerFit=false) const
Definition: gstat.cpp:228
PGStat Last() const
Definition: gstat.h:187
long long int64
Definition: bd.h:27
double GetMean() const
Definition: xmath.h:240
Definition: dt.h:412
Definition: ds.h:219
TStr GetStr(const TLoc &Loc=lUs) const
Definition: tm.cpp:457
int GetDay() const
Definition: gstat.h:87
TQuad< TStr, TStr, TStr, TGpScaleTy > TPlotInfo
Definition: gstat.h:40
void DelAfter(const TSecTm &Tm)
Definition: gstat.cpp:495
void GetTriadParticip(const PGraph &Graph, TIntPrV &TriadCntV)
Triangle Participation Ratio: For each node counts how many triangles it participates in and then ret...
Definition: triad.h:648
void GetValV(const TGStatVal &XVal, const TGStatVal &YVal, TFltPrV &ValV) const
Definition: gstat.cpp:511
void Plot(const TGStatDistr &Distr, const TStr &FNmPref, TStr Desc=TStr(), bool PowerFit=false) const
Definition: gstat.cpp:204
int GetMonth() const
Definition: gstat.h:86
int GetDistrs() const
Definition: gstat.h:101
TGStat & operator=(const TGStat &GStat)
Definition: gstat.cpp:47
double GetClustCf(const PGraph &Graph, int SampleNodes=-1)
Computes the average clustering coefficient as defined in Watts and Strogatz, Collective dynamics of ...
Definition: triad.h:113
Definition: bd.h:196
void SetTm(const TSecTm &GraphTm)
Definition: gstat.h:92
static int TakeSngVals
Definition: gstat.h:39
void SetTmUnit(const TTmUnit &TimeUnit)
Definition: gstat.h:197
TPt< TGStat > PGStat
Definition: gstat.h:4
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TGStat(const TSecTm &GraphTm=TSecTm(), const TStr &GraphName=TStr())
Definition: gstat.cpp:21
void TakeSccStat(const PGraph &Graph, TFSet StatFSet)
Definition: gstat.h:421
TGStatDistr_
Definition: gstat.h:27
double GetVal(const TGStatVal &StatVal) const
Definition: gstat.cpp:81
Definition: gstat.h:23
Definition: gstat.h:16
static TFSet BasicStat()
Definition: gstat.cpp:380
static PGStatVec Load(TSIn &SIn)
Definition: gstat.h:169
TTmUnit
Definition: tm.h:11
int CntDegNodes(const PGraph &Graph, const int &NodeDeg)
Returns the number of nodes with degree NodeDeg.
Definition: alg.h:105
static PGStatVec New(const TTmUnit &_TmUnit=tmu1Sec)
Definition: gstat.cpp:426
static PGStat Load(TSIn &SIn)
Definition: gstat.h:79
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static TFSet DegDStat()
Definition: gstat.cpp:384
void SetDistr(const TGStatDistr &Distr, const TFltPrV &FltPrV)
Definition: gstat.cpp:97
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
TGStatVal_
Definition: gstat.h:15
TPt< TGStatVec > PGStatVec
Definition: gstat.h:9
TGpScaleTy
Definition: gnuplot.h:6
int Len() const
Definition: hash.h:228
void GetWccSzCnt(const PGraph &Graph, TIntPrV &WccSzCnt)
Returns a distribution of weakly connected component sizes.
Definition: cncom.h:337
void Plot(const TGStatVal &XVal, const TGStatVal &YVal, const TStr &OutFNm, TStr &Desc, const TGpScaleTy &Scale=gpsAuto, const bool &PowerFit=false) const
Definition: gstat.cpp:529
TGpSeriesTy
Definition: gnuplot.h:11
bool operator<(const TGStat &GStat) const
Definition: gstat.cpp:61
const TFltPrV & GetDistr(const TGStatDistr &Distr) const
Definition: gstat.cpp:92
void Def()
Definition: xmath.cpp:339
TGStatVal ValCmp
Definition: gstat.h:44
int CntOutDegNodes(const PGraph &Graph, const int &NodeOutDeg)
Returns the number of nodes with out-degree NodeOutDeg.
Definition: alg.h:96
PGraph GetMxScc(const PGraph &Graph)
Returns a graph representing the largest strongly connected component on an input Graph...
Definition: cncom.h:469
Definition: gstat.h:31
void TakeDegDistr(const PGraph &Graph)
Definition: gstat.h:301
void TakeBasicStat(const PGraph &Graph, const bool &IsMxWcc=false)
Definition: gstat.h:257
void TakeDiam(const PGraph &Graph, const bool &IsMxWcc=false)
Definition: gstat.h:326
bool In(const int &FlagN) const
Definition: bits.h:156