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)
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.

                                                                                                                  {
  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); }
}

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.

                                                      {
  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;
}

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.

                                                                             {
  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;
}

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.

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

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.

                                                                       {
  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;
    }
  }
}

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

Definition at line 401 of file gsvd.cpp.

                                                 {
  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);
}

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.

                                                                     {
  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());
}

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.

                                                          {
  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;
  }
}

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.

                                                                                  {
  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
}

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.

                                                 {
  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();
}

Classes

Functions

Function Documentation