Classes
struct	TDelSelfEdges
struct	TDelSelfEdges< PGraph, true >
class	TCNMQMatrix
struct	TGetSubGraph
struct	TGetSubGraph< PGraph, false >
struct	TConvertSubGraph
struct	TConvertSubGraph< POutGraph, PInGraph, false >
Functions
double	CalcEffDiam (const TIntFltKdV &DistNbrsCdfV, const double &Percentile=0.9)
	Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function.
double	CalcEffDiamPdf (const TIntFltKdV &DistNbrsPdfV, const double &Percentile=0.9)
	Helper function for computing a given Percentile of a (unnormalized) probability distribution function.
double	CalcAvgDiamPdf (const TIntFltKdV &DistNbrsPdfV)
	Helper function for computing the mean of a (unnormalized) probability distribution function.
void	CmtyGirvanNewmanStep (PUNGraph &Graph, TIntV &Cmty1, TIntV &Cmty2)
	A single step of Girvan-Newman clustering procedure.
double	_GirvanNewmanGetModularity (const PUNGraph &G, const TIntH &OutDegH, const int &OrigEdges, TCnComV &CnComV)
TIntFltH	MapEquationNew2Modules (PUNGraph &Graph, TIntH &Module, TIntFltH &Qi, int a, int b)
float	Equation (PUNGraph &Graph, TIntFltH &PAlpha, float &SumPAlphaLogPAlpha, TIntFltH &Qi)
void	GetSphereDev (const int &Dim, TRnd &Rnd, TFltV &ValV)
	Sample random point from the surface of a Dim-dimensional unit sphere.
template<class PGraph >
TIntPr	GetRndEdgeNonAdjNode (const PGraph &Graph, int NId1, int NId2)
	Returns a random edge in a graph Graph where the edge does not touch nodes NId1 and NId2.
double	GetInvParticipRatEig (const TFltV &EigVec)
void	GVizDoLayout (const TStr &GraphInFNm, TStr OutFNm, const TGVizLayout &Layout)
	Runs GraphViz layout engine over a graph saved in the file GraphInFNm with output saved to OutFNm.
TStr	GVizGetLayoutStr (const TGVizLayout &Layout)
	Generates the GraphViz command string based on the selected Layout engine.

Function Documentation

double TSnap::TSnapDetail::_GirvanNewmanGetModularity	(	const PUNGraph &	G,
		const TIntH &	OutDegH,
		const int &	OrigEdges,
		TCnComV &	CnComV
	)

Definition at line 36 of file cmty.cpp.

References THash< TKey, TDat, THashFunc >::GetDat(), TUNGraph::GetNI(), TUNGraph::TNodeI::GetOutDeg(), TSnap::GetWccs(), and TVec< TVal, TSizeTy >::Len().

Referenced by TSnap::CommunityGirvanNewman().

                                                                                                                  {
  TSnap::GetWccs(G, CnComV); // get communities
  double Mod = 0;
  for (int c = 0; c < CnComV.Len(); c++) {
    const TIntV& NIdV = CnComV[c]();
    double EIn=0, EEIn=0;
    for (int i = 0; i < NIdV.Len(); i++) {
      TUNGraph::TNodeI NI = G->GetNI(NIdV[i]);
      EIn += NI.GetOutDeg();
      EEIn += OutDegH.GetDat(NIdV[i]);
    }
    Mod += (EIn-EEIn*EEIn/(2.0*OrigEdges));
  }
  if (Mod == 0) { return 0; }
  else { return Mod/(2.0*OrigEdges); }
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TSnap::TSnapDetail::CalcAvgDiamPdf ( const TIntFltKdV & DistNbrsPdfV )

Helper function for computing the mean of a (unnormalized) probability distribution function.

Definition at line 41 of file anf.cpp.

References TVec< TVal, TSizeTy >::Len().

Referenced by TSnap::PlotShortPathDistr().

                                                      {
  double Paths=0, SumLen=0;
  for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
    SumLen += DistNbrsPdfV[i].Key * DistNbrsPdfV[i].Dat;
    Paths += DistNbrsPdfV[i].Dat;
  }
  return SumLen/Paths;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TSnap::TSnapDetail::CalcEffDiam	(	const TIntFltKdV &	DistNbrsCdfV,
		const double &	Percentile
	)

Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function.

Definition at line 7 of file anf.cpp.

References TVec< TVal, TSizeTy >::Last(), and TVec< TVal, TSizeTy >::Len().

Referenced by CalcEffDiamPdf(), TSnap::GetAnfEffDiam(), TSnap::PlotHops(), and TGStat::TakeDiam().

                                                                             {
  const double EffPairs = Percentile * DistNbrsCdfV.Last().Dat;
  int ValN;
  for (ValN = 0; ValN < DistNbrsCdfV.Len(); ValN++) {
    if (DistNbrsCdfV[ValN].Dat() > EffPairs) {  break; }
  }
  if (ValN >= DistNbrsCdfV.Len()) return DistNbrsCdfV.Last().Key;
  if (ValN == 0) return 1;
  // interpolate
  const double DeltaNbrs = DistNbrsCdfV[ValN].Dat - DistNbrsCdfV[ValN-1].Dat;
  if (DeltaNbrs == 0) return DistNbrsCdfV[ValN].Key;
  return DistNbrsCdfV[ValN-1].Key + (EffPairs - DistNbrsCdfV[ValN-1].Dat)/DeltaNbrs;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TSnap::TSnapDetail::CalcEffDiamPdf	(	const TIntFltKdV &	DistNbrsPdfV,
		const double &	Percentile
	)

Helper function for computing a given Percentile of a (unnormalized) probability distribution function.

Definition at line 29 of file anf.cpp.

References CalcEffDiam(), and TGUtil::GetCdf().

Referenced by TSnap::GetBfsEffDiam(), and TSnap::PlotShortPathDistr().

                                                                                {
  TIntFltKdV CdfV;
  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
  return CalcEffDiam(CdfV, Percentile);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::TSnapDetail::CmtyGirvanNewmanStep	(	PUNGraph &	Graph,
		TIntV &	Cmty1,
		TIntV &	Cmty2
	)

A single step of Girvan-Newman clustering procedure.

Definition at line 14 of file cmty.cpp.

References TVec< TVal, TSizeTy >::Clr(), TUNGraph::DelEdge(), TBreathFS< PGraph >::DoBfs(), THash< TKey, TDat, THashFunc >::Empty(), TSnap::GetBetweennessCentr(), TBreathFS< PGraph >::GetHops(), THash< TKey, TDat, THashFunc >::GetKey(), TSnap::GetNodeWcc(), TInt::Mx, THash< TKey, TDat, THashFunc >::SortByDat(), TPair< TVal1, TVal2 >::Val1, and TPair< TVal1, TVal2 >::Val2.

Referenced by TSnap::CommunityGirvanNewman().

                                                                       {
  TIntPrFltH BtwEH;
  TBreathFS<PUNGraph> BFS(Graph);
  Cmty1.Clr(false);  Cmty2.Clr(false);
  while (true) {
    TSnap::GetBetweennessCentr(Graph, BtwEH);
    BtwEH.SortByDat(false);
    if (BtwEH.Empty()) { return; }
    const int NId1 = BtwEH.GetKey(0).Val1;
    const int NId2 = BtwEH.GetKey(0).Val2;
    Graph->DelEdge(NId1, NId2);
    BFS.DoBfs(NId1, true, false, NId2, TInt::Mx);
    if (BFS.GetHops(NId1, NId2) == -1) { // two components
      TSnap::GetNodeWcc(Graph, NId1, Cmty1);
      TSnap::GetNodeWcc(Graph, NId2, Cmty2);
      return;
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

float TSnap::TSnapDetail::Equation	(	PUNGraph &	Graph,
		TIntFltH &	PAlpha,
		float &	SumPAlphaLogPAlpha,
		TIntFltH &	Qi
	)

Definition at line 84 of file cmty.cpp.

References THash< TKey, TDat, THashFunc >::Len().

Referenced by TSnap::Infomap().

                                                                                         {
  float SumPAlpha = 1.0, SumQi = 0.0, SumQiLogQi=0.0, SumQiSumPAlphaLogQiSumPAlpha = 0.0;
  for (int i=0; i<Qi.Len(); i++) {
    SumQi += Qi[i];
    SumQiLogQi += Qi[i]*log(Qi[i]);
    SumQiSumPAlphaLogQiSumPAlpha += (Qi[i]+SumPAlpha)*log(Qi[i]+SumPAlpha);
  }
  return (SumQi*log(SumQi)-2*SumQiLogQi-SumPAlphaLogPAlpha+SumQiSumPAlphaLogQiSumPAlpha);
}

Here is the call graph for this function:

Here is the caller graph for this function:

double TSnap::TSnapDetail::GetInvParticipRatEig ( const TFltV & EigVec )

Definition at line 401 of file gsvd.cpp.

References TVec< TVal, TSizeTy >::Len().

Referenced by TSnap::GetInvParticipRat().

                                                 {
  double Sum2=0.0, Sum4=0.0;
  for (int i = 0; i < EigVec.Len(); i++) {
    Sum2 += EigVec[i]*EigVec[i];
    Sum4 += pow(EigVec[i].Val, 4.0);
  }
  return Sum4/(Sum2*Sum2);
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class PGraph >

TIntPr TSnap::TSnapDetail::GetRndEdgeNonAdjNode	(	const PGraph &	Graph,
		int	NId1,
		int	NId2
	)

Returns a random edge in a graph Graph where the edge does not touch nodes NId1 and NId2.

Definition at line 240 of file ggen.h.

References TRnd::GetUniDevInt(), and TInt::Rnd.

Referenced by TSnap::GenDegSeq().

                                                                     {
  typename PGraph::TObj::TNodeI NI1, NI2;
  int OutDeg = -1;
  do {
    NI1 = Graph->GetRndNI();
    OutDeg = NI1.GetOutDeg();
  } while (OutDeg == 0);
  NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
  int runs = 0;
  while (NI1.IsNbrNId(NId1) || NI1.IsNbrNId(NId2) || NI2.IsNbrNId(NId1) || NI2.IsNbrNId(NId2) || NI1.GetId()==NI2.GetId()) {
    do {
      NI1 = Graph->GetRndNI();
      OutDeg = NI1.GetOutDeg();
    } while (OutDeg == 0);
    NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
    if (runs++ == 1000) { return TIntPr(-1, -1); }
  }
  return TIntPr(NI1.GetId(), NI2.GetId());
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::TSnapDetail::GetSphereDev	(	const int &	Dim,
		TRnd &	Rnd,
		TFltV &	ValV
	)

Sample random point from the surface of a Dim-dimensional unit sphere.

Definition at line 343 of file ggen.cpp.

References TVec< TVal, TSizeTy >::Gen(), TRnd::GetNrmDev(), TVec< TVal, TSizeTy >::Len(), and TMath::Sqr().

Referenced by TSnap::GenGeoPrefAttach().

                                                          {
  if (ValV.Len() != Dim) { ValV.Gen(Dim); }
  double Length = 0.0;
  for (int i = 0; i < Dim; i++) {
    ValV[i] = Rnd.GetNrmDev();
    Length += TMath::Sqr(ValV[i]); }
  Length = 1.0 / sqrt(Length);
  for (int i = 0; i < Dim; i++) {
    ValV[i] *= Length;
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void TSnap::TSnapDetail::GVizDoLayout	(	const TStr &	GraphInFNm,
		TStr	OutFNm,
		const TGVizLayout &	Layout
	)

Runs GraphViz layout engine over a graph saved in the file GraphInFNm with output saved to OutFNm.

Definition at line 5 of file gviz.cpp.

References TStr::CStr(), TStr::Fmt(), TStr::GetFExt(), GVizGetLayoutStr(), and IAssert.

Referenced by TSnap::DrawGViz(), TGraphKey::DrawGViz(), TGHash< TDat >::DrawGViz(), and TAGMUtil::GVizComGraph().

                                                                                  {
  TStr LayoutExe = TSnap::TSnapDetail::GVizGetLayoutStr(Layout), Ext = OutFNm.GetFExt(), GvPath;
  #if defined(GLib_WIN)
    GvPath = "C:\\Prog\\GraphViz\\bin\\";
  #else
    GvPath = "/usr/bin/";
    //OutFNm = OutFNm.GetFMid() + Ext;
  #endif
  IAssert(Ext==".ps" || Ext==".gif" || Ext==".png");
  const TStr ExeCmd = TStr::Fmt("%s -T%s %s -o %s", LayoutExe.CStr(),
    Ext.CStr()+1, GraphInFNm.CStr(), OutFNm.CStr());

  if (system(ExeCmd.CStr())==0) { return; }
  #if defined(GLib_WIN)
  if (system(TStr::Fmt(".\\%s", ExeCmd.CStr()).CStr())==0) { return; }
  #else
  if (system(TStr::Fmt("./%s", ExeCmd.CStr()).CStr())==0) { return; }
  #endif
  if (system(TStr::Fmt("%s%s", GvPath.CStr(), ExeCmd.CStr()).CStr())==0) { return; }
  fprintf(stderr, "[%s:%d] Cannot find GraphViz (%s). Set the PATH.\n", __FILE__, __LINE__, ExeCmd.CStr());
  //#if defined(GLib_WIN)
  //if (ShowPlot) system(TStr::Fmt("start %s", OutFNm.CStr()).CStr());
  //#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

TStr TSnap::TSnapDetail::GVizGetLayoutStr ( const TGVizLayout & Layout )

Generates the GraphViz command string based on the selected Layout engine.

Definition at line 30 of file gviz.cpp.

References Fail, TStr::GetNullStr(), gvlCirco, gvlDot, gvlNeato, gvlSfdp, and gvlTwopi.

Referenced by GVizDoLayout().

                                                 {
  switch(Layout) {
    case gvlDot : return "dot";
    case gvlNeato : return "neato";
    case gvlTwopi : return "twopi";
    case gvlCirco: return "circo";
    case gvlSfdp: return "sfdp";
    default: Fail;
  }
  return TStr::GetNullStr();
}

Here is the call graph for this function:

Here is the caller graph for this function:

TIntFltH TSnap::TSnapDetail::MapEquationNew2Modules	(	PUNGraph &	Graph,
		TIntH &	Module,
		TIntFltH &	Qi,
		int	a,
		int	b
	)

Definition at line 53 of file cmty.cpp.

References THash< TKey, TDat, THashFunc >::AddDat(), TUNGraph::BegEI(), THash< TKey, TDat, THashFunc >::DelKey(), TUNGraph::EndEI(), THash< TKey, TDat, THashFunc >::GetDat(), and THash< TKey, TDat, THashFunc >::IsKey().

Referenced by TSnap::Infomap().

                                                                                           {
  TIntFltH Qi1;
  Qi1 = Qi;     
  float InModule=0.0, OutModule=0.0, Val;
  int Mds[2] = {a,b};
  for (int i=0; i<2; i++) {
    InModule=0.0, OutModule=0.0;
    if (Qi1.IsKey(Mds[i])){
      int CentralModule = Mds[i];
      for (TUNGraph::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
        if (Module.GetDat(EI.GetSrcNId()) == Module.GetDat(EI.GetDstNId()) && Module.GetDat(EI.GetDstNId()) == CentralModule) {
          InModule += 1.0;
        } else if ((Module.GetDat(EI.GetSrcNId()) == CentralModule && Module.GetDat(EI.GetDstNId()) != CentralModule) || (Module.GetDat(EI.GetSrcNId()) != CentralModule && Module.GetDat(EI.GetDstNId()) == CentralModule)) {
          OutModule +=1.0;
        }
            }
      Val = 0.0;
      if (InModule+OutModule > 0) {
        Val = OutModule/(InModule+OutModule);
      }
      Qi1.DelKey(Mds[i]);
      Qi1.AddDat(Mds[i],Val);
    } else {
      Qi1.DelKey(Mds[i]);
      Qi1.AddDat(Mds[i],0.0);
    }
  }
        
  return Qi1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Classes

Functions

Function Documentation