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
anf.cpp
Go to the documentation of this file.
1 // Approximate Neighborhood Function
3 namespace TSnap {
4 namespace TSnapDetail {
5 
6 // interpolate effective diameter
7 double CalcEffDiam(const TIntFltKdV& DistNbrsCdfV, const double& Percentile) {
8  const double EffPairs = Percentile * DistNbrsCdfV.Last().Dat;
9  int ValN;
10  for (ValN = 0; ValN < DistNbrsCdfV.Len(); ValN++) {
11  if (DistNbrsCdfV[ValN].Dat() > EffPairs) { break; }
12  }
13  if (ValN >= DistNbrsCdfV.Len()) return DistNbrsCdfV.Last().Key;
14  if (ValN == 0) return 1;
15  // interpolate
16  const double DeltaNbrs = DistNbrsCdfV[ValN].Dat - DistNbrsCdfV[ValN-1].Dat;
17  if (DeltaNbrs == 0) return DistNbrsCdfV[ValN].Key;
18  return DistNbrsCdfV[ValN-1].Key + (EffPairs - DistNbrsCdfV[ValN-1].Dat)/DeltaNbrs;
19 }
20 
21 double CalcEffDiam(const TFltPrV& DistNbrsCdfV, const double& Percentile) {
22  TIntFltKdV KdV(DistNbrsCdfV.Len(), 0);
23  for (int i = 0; i < DistNbrsCdfV.Len(); i++) {
24  KdV.Add(TIntFltKd(int(DistNbrsCdfV[i].Val1()), DistNbrsCdfV[i].Val2));
25  }
26  return CalcEffDiam(KdV, Percentile);
27 }
28 
29 double CalcEffDiamPdf(const TIntFltKdV& DistNbrsPdfV, const double& Percentile) {
30  TIntFltKdV CdfV;
31  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
32  return CalcEffDiam(CdfV, Percentile);
33 }
34 
35 double CalcEffDiamPdf(const TFltPrV& DistNbrsPdfV, const double& Percentile) {
36  TFltPrV CdfV;
37  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
38  return CalcEffDiam(CdfV, Percentile);
39 }
40 
41 double CalcAvgDiamPdf(const TIntFltKdV& DistNbrsPdfV) {
42  double Paths=0, SumLen=0;
43  for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
44  SumLen += DistNbrsPdfV[i].Key * DistNbrsPdfV[i].Dat;
45  Paths += DistNbrsPdfV[i].Dat;
46  }
47  return SumLen/Paths;
48 }
49 
50 double CalcAvgDiamPdf(const TFltPrV& DistNbrsPdfV) {
51  double Paths=0, SumLen=0;
52  for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
53  SumLen += DistNbrsPdfV[i].Val1 * DistNbrsPdfV[i].Val2;
54  Paths += DistNbrsPdfV[i].Val2;
55  }
56  return SumLen/Paths;
57 }
58 
59 } // namespace TSnapDetail
60 } // namespace TSnap
61 
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:381
double CalcEffDiamPdf(const TIntFltKdV &DistNbrsPdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) probability distribution functio...
Definition: anf.cpp:29
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
static void GetCdf(const TIntPrV &PdfV, TIntPrV &CdfV)
Definition: util.cpp:3
double CalcAvgDiamPdf(const TIntFltKdV &DistNbrsPdfV)
Helper function for computing the mean of a (unnormalized) probability distribution function...
Definition: anf.cpp:41
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
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430