TSnap::TSnapDetail Namespace Reference

Classes
class	TCNMQMatrix
struct	TConvertSubGraph
struct	TConvertSubGraph< POutGraph, PInGraph, false >
struct	TDelSelfEdges
struct	TDelSelfEdges< PGraph, true >
struct	TGetSubGraph
struct	TGetSubGraph< PGraph, 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. More...
double	CalcEffDiam (const TFltPrV &DistNbrsCdfV, const double &Percentile=0.9)
	Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function. More...
double	CalcEffDiamPdf (const TIntFltKdV &DistNbrsPdfV, const double &Percentile=0.9)
	Helper function for computing a given Percentile of a (unnormalized) probability distribution function. More...
double	CalcEffDiamPdf (const TFltPrV &DistNbrsPdfV, const double &Percentile=0.9)
	Helper function for computing a given Percentile of a (unnormalized) probability distribution function. More...
double	CalcAvgDiamPdf (const TIntFltKdV &DistNbrsPdfV)
	Helper function for computing the mean of a (unnormalized) probability distribution function. More...
double	CalcAvgDiamPdf (const TFltPrV &DistNbrsPdfV)
	Helper function for computing the mean of a (unnormalized) probability distribution function. More...
void	CmtyGirvanNewmanStep (PUNGraph &Graph, TIntV &Cmty1, TIntV &Cmty2)
	A single step of Girvan-Newman clustering procedure. More...
double	_GirvanNewmanGetModularity (const PUNGraph &G, const TIntH &OutDegH, const int &OrigEdges, TCnComV &CnComV)
void	MapEquationNew2Modules (PUNGraph &Graph, TIntH &Module, TIntFltH &Qi, int a, int b)
double	Equation (TIntFltH &PAlpha, double &SumPAlphaLogPAlpha, TIntFltH &Qi)
bool	edgeIntersect (PNGraph &graph, TIntV &a, TIntV &b)
int	vectorIntersect (TIntV &a, TIntV &b)
bool	inComp (PNGraph &g1, PNGraph &Graph, TIntH &inCompCount, int id, int neigh)
void	transitiveTransform (TIntV &a, TIntV &b)
bool	chekIfCrossing (TIntV &a, TIntH &t, int f, int l, int TP)
double	InfomapOnlineIncrement (PUNGraph &Graph, int n1, int n2, TIntFltH &PAlpha, double &SumPAlphaLogPAlpha, TIntFltH &Qi, TIntH &Module, int &Br)
void	GetSphereDev (const int &Dim, TRnd &Rnd, TFltV &ValV)
	Sample random point from the surface of a Dim-dimensional unit sphere. More...
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. More...
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. More...
TStr	GVizGetLayoutStr (const TGVizLayout &Layout)
	Generates the GraphViz command string based on the selected Layout engine. More...

Function Documentation

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

Definition at line 37 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::CalcAvgDiamPdf

(

const TFltPrV &

DistNbrsPdfV

)

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

Definition at line 50 of file anf.cpp.

                                                   {
  double Paths=0, SumLen=0;
  for (int i = 0; i < DistNbrsPdfV.Len(); i++) {
    SumLen += DistNbrsPdfV[i].Val1 * DistNbrsPdfV[i].Val2;
    Paths += DistNbrsPdfV[i].Val2;
  }
  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::CalcEffDiam	(	const TFltPrV &	DistNbrsCdfV,
		const double &	Percentile
	)

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

Definition at line 21 of file anf.cpp.

                                                                          {
  TIntFltKdV KdV(DistNbrsCdfV.Len(), 0);
  for (int i = 0; i < DistNbrsCdfV.Len(); i++) {
    KdV.Add(TIntFltKd(int(DistNbrsCdfV[i].Val1()), DistNbrsCdfV[i].Val2));
  }
  return CalcEffDiam(KdV, Percentile);
}

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

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

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

Definition at line 35 of file anf.cpp.

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

bool TSnap::TSnapDetail::chekIfCrossing	(	TIntV &	a,
		TIntH &	t,
		int	f,
		int	l,
		int	TP
	)

Definition at line 195 of file cmty.cpp.

                                                              {
  bool after = false;
  bool before = false;
  for (int i = 0; i < a.Len(); i++) {
    if (t.GetDat(a[i]) < TP)
      before = true;
    if (t.GetDat(a[i]) > TP)
      after = true;
  }

  if (TP == f)
    before = true;

  if (TP == l)
    after = true;

  return (after && before);
}

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

A single step of Girvan-Newman clustering procedure.

Definition at line 15 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;
    }
  }
}

bool TSnap::TSnapDetail::edgeIntersect	(	PNGraph &	graph,
		TIntV &	a,
		TIntV &	b
	)

Definition at line 127 of file cmty.cpp.

                                                       {
  for (int i = 0; i<a.Len(); i++) {
    for (int j = 0; j<b.Len(); j++) {
      if (graph->IsEdge(a[i], b[j]))
        return true;
    }
  }

  return false;
}

double TSnap::TSnapDetail::Equation	(	TIntFltH &	PAlpha,
		double &	SumPAlphaLogPAlpha,
		TIntFltH &	Qi
	)

Definition at line 109 of file cmty.cpp.

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

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

bool TSnap::TSnapDetail::inComp	(	PNGraph &	g1,
		PNGraph &	Graph,
		TIntH &	inCompCount,
		int	id,
		int	neigh
	)

Definition at line 150 of file cmty.cpp.

                                                                                {
  bool out = true;

  int inCompN = 0;
  int inComp = 0;

  if (g1->IsNode(id) && g1->IsNode(neigh)) {
    int deg = g1->GetNI(id).GetDeg();
    int neighDeg = g1->GetNI(neigh).GetDeg();


    if (inCompCount.IsKey(id)) {
      inComp = inCompCount.GetDat(id);
    }
    if (inCompCount.IsKey(neigh)) {
      inCompN = inCompCount.GetDat(neigh);
    }

    if (inCompN < neighDeg && inComp < deg && (!g1->IsNode(neigh) || Graph->GetNI(neigh).GetDeg() - neighDeg == 0)) {
      inCompCount.AddDat(neigh, ++inCompN);
      inCompCount.AddDat(id, ++inComp);
      out = true;
    } else {
      out = false;
    }
  }
  return out;
}

double TSnap::TSnapDetail::InfomapOnlineIncrement	(	PUNGraph &	Graph,
		int	n1,
		int	n2,
		TIntFltH &	PAlpha,
		double &	SumPAlphaLogPAlpha,
		TIntFltH &	Qi,
		TIntH &	Module,
		int &	Br
	)

Definition at line 214 of file cmty.cpp.

                                                                                                                                                   {
  // NOW NEW stuff add another additional iteration:

  bool n1new = false;
  bool n2new = false;

  // add edge
  if (!Graph->IsNode(n1)){
    Graph->AddNode(n1);
    n1new = true;
  }

  if (!Graph->IsNode(n2)) {
    Graph->AddNode(n2);
    n2new = true;
  }

  Graph->AddEdge(n1, n2);

  int e = Graph->GetEdges();

  // get previous alpha for 27 
  double oldAlphaN1 = 0.0;
  double oldAlphaN2 = 0.0;

  if (!n1new)
    oldAlphaN1 = PAlpha.GetDat(n1);

  if (!n2new)
    oldAlphaN2 = PAlpha.GetDat(n2);

  // update alpha for 27
  TUNGraph::TNodeI node = Graph->GetNI(n1);
  int nodeDeg = node.GetDeg();
  float d = ((float)nodeDeg / (float)(2 * e));
  PAlpha.AddDat(n1, d);

  //update alphasum
  SumPAlphaLogPAlpha = SumPAlphaLogPAlpha - oldAlphaN1 + d*log(d);

  if (n1new) {
    Module.AddDat(n1, Br);
    Qi.AddDat(Br, 1.0);
    Br++;
  }

  // update alpha for 28
  node = Graph->GetNI(n2);
  nodeDeg = node.GetDeg();
  d = ((float)nodeDeg / (float)(2 * e));
  PAlpha.AddDat(n2, d);

  //update alphasum
  SumPAlphaLogPAlpha = SumPAlphaLogPAlpha - oldAlphaN2 + d*log(d);

  //add module
  if (n2new) {
    Module.AddDat(n2, Br);
    Qi.AddDat(Br, 1.0);
    Br++;
  }

  // Start

  double MinCodeLength = TSnapDetail::Equation(PAlpha, SumPAlphaLogPAlpha, Qi);
  double PrevIterationCodeLength = 0.0;

  do {
    PrevIterationCodeLength = MinCodeLength;
    int id[2] = { n1, n2 };
    for (int k = 0; k<2; k++) {
      for (int i = 0; i<Graph->GetNI(id[k]).GetDeg(); i++) {

        int OldModule = Module.GetDat(id[k]);
        int NewModule = Module.GetDat(Graph->GetNI(id[k]).GetNbrNId(i));

        Module.AddDat(id[k], NewModule);

        TSnapDetail::MapEquationNew2Modules(Graph, Module, Qi, OldModule, NewModule);
        double NewCodeLength = TSnapDetail::Equation(PAlpha, SumPAlphaLogPAlpha, Qi);
        if (NewCodeLength<MinCodeLength) {
          MinCodeLength = NewCodeLength;
          OldModule = NewModule;
        }
        else {
          Module.AddDat(id[k], OldModule);
        }
      }
    }
  } while (MinCodeLength<PrevIterationCodeLength);

  return MinCodeLength;
}

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

Definition at line 54 of file cmty.cpp.

                                                                                        {
  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 (Qi.IsKey(Mds[i])) {
      int CentralModule = Mds[i];

      //printf("central module: %i\n ",CentralModule);

      TIntV newM;
      for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
        if (Module.GetDat(NI.GetId()) == CentralModule)
          newM.Add(NI.GetId());
        }

      for (int j = 0; j<newM.Len(); j++) {
        //int len1 = newM.Len();

        //int c = CentralModule;
        for (int k = 0; k<Graph->GetNI(newM[j]).GetDeg(); k++) {
          //int len = Graph->GetNI(newM[j]).GetDeg();

          int ids = Graph->GetNI(newM[j]).GetId();
          int idd = Graph->GetNI(newM[j]).GetNbrNId(k);
          int ms = Module.GetDat(ids);
          int md = Module.GetDat(idd);
          //int c = CentralModule;

          if (ms == md) {
            InModule += 1.0;
            //printf("IN: \t%i - %i; moduls: %i - %i\n", ids, idd, ms, md);
          } else {
            OutModule += 1.0;
            //printf("OUT: \t%i - %i; moduls: %i - %i\n", ids, idd, ms, md);
          }
        }
      }
      if (InModule >1) InModule = InModule / 2;

      //printf("\n");

      Val = 0.0;
      if (InModule + OutModule > 0) {
        Val = OutModule / (InModule + OutModule);
      }
      //int control = Mds[i];
      Qi.AddDat(Mds[i], Val);
    } else {
      //int control = Mds[i];
      Qi.AddDat(Mds[i], 0.0);
    }
  }
}

void TSnap::TSnapDetail::transitiveTransform	(	TIntV &	a,
		TIntV &	b
	)

Definition at line 179 of file cmty.cpp.

                                             {
  for (int i = 0; i < a.Len(); i++) {
    bool diff = false;
    for (int j = 0; j < b.Len(); j++) {
      if (a[i] == a[j]) {
        diff = true;
        break;
      }
    }
    if (!diff) {
      b.Add(a[i]);
      break;
    }
  }
}

int TSnap::TSnapDetail::vectorIntersect	(	TIntV &	a,
		TIntV &	b
	)

Definition at line 138 of file cmty.cpp.

                                        {
  int count = 0;
  for (int i = 0; i<a.Len(); i++) {
    for (int j = 0; j<b.Len(); j++) {
      if (a[i] == b[j])
        count++;
    }
  }

  return count;
}