SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
anf.cpp
Go to the documentation of this file.
00001 
00002 // Approximate Neighborhood Function
00003 namespace TSnap {
00004 namespace TSnapDetail {
00005 
00006 // interpolate effective diameter
00007 double CalcEffDiam(const TIntFltKdV& DistNbrsCdfV, const double& Percentile) {
00008   const double EffPairs = Percentile * DistNbrsCdfV.Last().Dat;
00009   int ValN;
00010   for (ValN = 0; ValN < DistNbrsCdfV.Len(); ValN++) {
00011     if (DistNbrsCdfV[ValN].Dat() > EffPairs) {  break; }
00012   }
00013   if (ValN >= DistNbrsCdfV.Len()) return DistNbrsCdfV.Last().Key;
00014   if (ValN == 0) return 1;
00015   // interpolate
00016   const double DeltaNbrs = DistNbrsCdfV[ValN].Dat - DistNbrsCdfV[ValN-1].Dat;
00017   if (DeltaNbrs == 0) return DistNbrsCdfV[ValN].Key;
00018   return DistNbrsCdfV[ValN-1].Key + (EffPairs - DistNbrsCdfV[ValN-1].Dat)/DeltaNbrs;
00019 }
00020 
00021 double CalcEffDiam(const TFltPrV& DistNbrsCdfV, const double& Percentile) {
00022   TIntFltKdV KdV(DistNbrsCdfV.Len(), 0);
00023   for (int i = 0; i < DistNbrsCdfV.Len(); i++) {
00024     KdV.Add(TIntFltKd(int(DistNbrsCdfV[i].Val1()), DistNbrsCdfV[i].Val2));
00025   }
00026   return CalcEffDiam(KdV, Percentile);
00027 }
00028 
00029 double CalcEffDiamPdf(const TIntFltKdV& DistNbrsPdfV, const double& Percentile) {
00030   TIntFltKdV CdfV;
00031   TGUtil::GetCdf(DistNbrsPdfV, CdfV);
00032   return CalcEffDiam(CdfV, Percentile);
00033 }
00034 
00035 double CalcEffDiamPdf(const TFltPrV& DistNbrsPdfV, const double& Percentile) {
00036   TFltPrV CdfV;
00037   TGUtil::GetCdf(DistNbrsPdfV, CdfV);
00038   return CalcEffDiam(CdfV, Percentile);
00039 }
00040 
00041 double CalcAvgDiamPdf(const TIntFltKdV& DistNbrsPdfV) {
00042   double Paths=0, SumLen=0;
00043   for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
00044     SumLen += DistNbrsPdfV[i].Key * DistNbrsPdfV[i].Dat;
00045     Paths += DistNbrsPdfV[i].Dat;
00046   }
00047   return SumLen/Paths;
00048 }
00049 
00050 double CalcAvgDiamPdf(const TFltPrV& DistNbrsPdfV) {
00051   double Paths=0, SumLen=0;
00052   for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
00053     SumLen += DistNbrsPdfV[i].Val1 * DistNbrsPdfV[i].Val2;
00054     Paths += DistNbrsPdfV[i].Val2;
00055   }
00056   return SumLen/Paths;
00057 }
00058 
00059 } // namespace TSnapDetail
00060 } // namespace TSnap
00061