SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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:416
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:697
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:137
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
bool IsKey(const TKey &Key) const
Definition: hash.h:258
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
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
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