SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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
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.

37  {
38  TSnap::GetWccs(G, CnComV); // get communities
39  double Mod = 0;
40  for (int c = 0; c < CnComV.Len(); c++) {
41  const TIntV& NIdV = CnComV[c]();
42  double EIn = 0, EEIn = 0;
43  for (int i = 0; i < NIdV.Len(); i++) {
44  TUNGraph::TNodeI NI = G->GetNI(NIdV[i]);
45  EIn += NI.GetOutDeg();
46  EEIn += OutDegH.GetDat(NIdV[i]);
47  }
48  Mod += (EIn-EEIn*EEIn / (2.0*OrigEdges));
49  }
50  if (Mod == 0) { return 0; }
51  else { return Mod / (2.0*OrigEdges); }
52 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
int GetOutDeg() const
Returns out-degree of the current node (returns same as value GetDeg() since the graph is undirected)...
Definition: graph.h:90
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
void GetWccs(const PGraph &Graph, TCnComV &CnComV)
Returns all weakly connected components in a Graph.
Definition: cncom.h:376
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.

41  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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.

50  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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.

7  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
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.

21  {
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 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:380
double CalcEffDiam(const TFltPrV &DistNbrsCdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function...
Definition: anf.cpp:21
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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.

29  {
30  TIntFltKdV CdfV;
31  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
32  return CalcEffDiam(CdfV, Percentile);
33 }
static void GetCdf(const TIntPrV &PdfV, TIntPrV &CdfV)
Definition: util.cpp:3
double CalcEffDiam(const TFltPrV &DistNbrsCdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function...
Definition: anf.cpp:21
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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.

35  {
36  TFltPrV CdfV;
37  TGUtil::GetCdf(DistNbrsPdfV, CdfV);
38  return CalcEffDiam(CdfV, Percentile);
39 }
static void GetCdf(const TIntPrV &PdfV, TIntPrV &CdfV)
Definition: util.cpp:3
double CalcEffDiam(const TFltPrV &DistNbrsCdfV, const double &Percentile)
Helper function for computing a given Percentile of a (unnormalized) cumulative distribution function...
Definition: anf.cpp:21
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
bool TSnap::TSnapDetail::chekIfCrossing ( TIntV a,
TIntH t,
int  f,
int  l,
int  TP 
)

Definition at line 195 of file cmty.cpp.

195  {
196  bool after = false;
197  bool before = false;
198  for (int i = 0; i < a.Len(); i++) {
199  if (t.GetDat(a[i]) < TP)
200  before = true;
201  if (t.GetDat(a[i]) > TP)
202  after = true;
203  }
204 
205  if (TP == f)
206  before = true;
207 
208  if (TP == l)
209  after = true;
210 
211  return (after && before);
212 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
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.

15  {
16  TIntPrFltH BtwEH;
17  TBreathFS<PUNGraph> BFS(Graph);
18  Cmty1.Clr(false); Cmty2.Clr(false);
19  while (true) {
20  TSnap::GetBetweennessCentr(Graph, BtwEH);
21  BtwEH.SortByDat(false);
22  if (BtwEH.Empty()) { return; }
23  const int NId1 = BtwEH.GetKey(0).Val1;
24  const int NId2 = BtwEH.GetKey(0).Val2;
25  Graph->DelEdge(NId1, NId2);
26  BFS.DoBfs(NId1, true, false, NId2, TInt::Mx);
27  if (BFS.GetHops(NId1, NId2) == -1) { // two components
28  TSnap::GetNodeWcc(Graph, NId1, Cmty1);
29  TSnap::GetNodeWcc(Graph, NId2, Cmty2);
30  return;
31  }
32  }
33 }
void GetNodeWcc(const PGraph &Graph, const int &NId, TIntV &CnCom)
Returns (via output parameter CnCom) all nodes that are in the same connected component as node NId...
Definition: cncom.h:277
static const int Mx
Definition: dt.h:1049
bool Empty() const
Definition: hash.h:185
void GetBetweennessCentr(const PGraph &Graph, TIntFltH &NIdBtwH, const bool &IsDir=false, const double &NodeFrac=1.0)
Definition: centr.h:450
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
void DelEdge(const int &SrcNId, const int &DstNId)
Deletes an edge between node IDs SrcNId and DstNId from the graph.
Definition: graph.cpp:124
TVal1 Val1
Definition: ds.h:34
TVal2 Val2
Definition: ds.h:35
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
void SortByDat(const bool &Asc=true)
Definition: hash.h:250
bool TSnap::TSnapDetail::edgeIntersect ( PNGraph graph,
TIntV a,
TIntV b 
)

Definition at line 127 of file cmty.cpp.

127  {
128  for (int i = 0; i<a.Len(); i++) {
129  for (int j = 0; j<b.Len(); j++) {
130  if (graph->IsEdge(a[i], b[j]))
131  return true;
132  }
133  }
134 
135  return false;
136 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
bool IsEdge(const int &SrcNId, const int &DstNId, const bool &IsDir=true) const
Tests whether an edge from node IDs SrcNId to DstNId exists in the graph.
Definition: graph.cpp:363
double TSnap::TSnapDetail::Equation ( TIntFltH PAlpha,
double &  SumPAlphaLogPAlpha,
TIntFltH Qi 
)

Definition at line 109 of file cmty.cpp.

109  {
110  double SumPAlpha = 1.0, SumQi = 0.0, SumQiLogQi = 0.0;
111  double SumQiSumPAlphaLogQiSumPAlpha = 0.0, logqi = 0.0, qi = 0.0;
112  for (int i = 0; i<Qi.Len(); i++) {
113  SumQi += Qi[i];
114  qi = Qi[i];
115  if (qi != 0) {
116  logqi = log(qi);
117  } else {
118  logqi = 0;
119  }
120  SumQiLogQi += Qi[i] * logqi;
121  SumQiSumPAlphaLogQiSumPAlpha += (Qi[i] + SumPAlpha)*log(Qi[i] + SumPAlpha);
122  }
123  return (SumQi*log(SumQi) - 2 * SumQiLogQi - SumPAlphaLogPAlpha +
124  SumQiSumPAlphaLogQiSumPAlpha);
125 }
int Len() const
Definition: hash.h:186
double TSnap::TSnapDetail::GetInvParticipRatEig ( const TFltV EigVec)

Definition at line 401 of file gsvd.cpp.

401  {
402  double Sum2=0.0, Sum4=0.0;
403  for (int i = 0; i < EigVec.Len(); i++) {
404  Sum2 += EigVec[i]*EigVec[i];
405  Sum4 += pow(EigVec[i].Val, 4.0);
406  }
407  return Sum4/(Sum2*Sum2);
408 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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.

240  {
241  typename PGraph::TObj::TNodeI NI1, NI2;
242  int OutDeg = -1;
243  do {
244  NI1 = Graph->GetRndNI();
245  OutDeg = NI1.GetOutDeg();
246  } while (OutDeg == 0);
247  NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
248  int runs = 0;
249  while (NI1.IsNbrNId(NId1) || NI1.IsNbrNId(NId2) || NI2.IsNbrNId(NId1) || NI2.IsNbrNId(NId2) || NI1.GetId()==NI2.GetId()) {
250  do {
251  NI1 = Graph->GetRndNI();
252  OutDeg = NI1.GetOutDeg();
253  } while (OutDeg == 0);
254  NI2 = Graph->GetNI(NI1.GetOutNId(TInt::Rnd.GetUniDevInt(OutDeg)));
255  if (runs++ == 1000) { return TIntPr(-1, -1); }
256  }
257  return TIntPr(NI1.GetId(), NI2.GetId());
258 }
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
static TRnd Rnd
Definition: dt.h:1053
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
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.

343  {
344  if (ValV.Len() != Dim) { ValV.Gen(Dim); }
345  double Length = 0.0;
346  for (int i = 0; i < Dim; i++) {
347  ValV[i] = Rnd.GetNrmDev();
348  Length += TMath::Sqr(ValV[i]); }
349  Length = 1.0 / sqrt(Length);
350  for (int i = 0; i < Dim; i++) {
351  ValV[i] *= Length;
352  }
353 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
static double Sqr(const double &x)
Definition: xmath.h:12
double GetNrmDev()
Definition: dt.cpp:63
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
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.

5  {
6  TStr LayoutExe = TSnap::TSnapDetail::GVizGetLayoutStr(Layout), Ext = OutFNm.GetFExt(), GvPath;
7  #if defined(GLib_WIN)
8  GvPath = "C:\\Prog\\GraphViz\\bin\\";
9  #else
10  GvPath = "/usr/bin/";
11  //OutFNm = OutFNm.GetFMid() + Ext;
12  #endif
13  IAssert(Ext==".ps" || Ext==".gif" || Ext==".png");
14  const TStr ExeCmd = TStr::Fmt("%s -T%s %s -o %s", LayoutExe.CStr(),
15  Ext.CStr()+1, GraphInFNm.CStr(), OutFNm.CStr());
16 
17  if (system(ExeCmd.CStr())==0) { return; }
18  #if defined(GLib_WIN)
19  if (system(TStr::Fmt(".\\%s", ExeCmd.CStr()).CStr())==0) { return; }
20  #else
21  if (system(TStr::Fmt("./%s", ExeCmd.CStr()).CStr())==0) { return; }
22  #endif
23  if (system(TStr::Fmt("%s%s", GvPath.CStr(), ExeCmd.CStr()).CStr())==0) { return; }
24  fprintf(stderr, "[%s:%d] Cannot find GraphViz (%s). Set the PATH.\n", __FILE__, __LINE__, ExeCmd.CStr());
25  //#if defined(GLib_WIN)
26  //if (ShowPlot) system(TStr::Fmt("start %s", OutFNm.CStr()).CStr());
27  //#endif
28 }
#define IAssert(Cond)
Definition: bd.h:262
TStr GetFExt() const
Definition: dt.cpp:1421
Definition: dt.h:412
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
char * CStr()
Definition: dt.h:476
TStr GVizGetLayoutStr(const TGVizLayout &Layout)
Generates the GraphViz command string based on the selected Layout engine.
Definition: gviz.cpp:30
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.

30  {
31  switch(Layout) {
32  case gvlDot : return "dot";
33  case gvlNeato : return "neato";
34  case gvlTwopi : return "twopi";
35  case gvlCirco: return "circo";
36  case gvlSfdp: return "sfdp";
37  default: Fail;
38  }
39  return TStr::GetNullStr();
40 }
Definition: gviz.h:3
#define Fail
Definition: bd.h:238
Definition: gviz.h:3
Definition: gviz.h:3
Definition: gviz.h:3
Definition: gviz.h:3
static TStr GetNullStr()
Definition: dt.cpp:1626
bool TSnap::TSnapDetail::inComp ( PNGraph g1,
PNGraph Graph,
TIntH inCompCount,
int  id,
int  neigh 
)

Definition at line 150 of file cmty.cpp.

150  {
151  bool out = true;
152 
153  int inCompN = 0;
154  int inComp = 0;
155 
156  if (g1->IsNode(id) && g1->IsNode(neigh)) {
157  int deg = g1->GetNI(id).GetDeg();
158  int neighDeg = g1->GetNI(neigh).GetDeg();
159 
160 
161  if (inCompCount.IsKey(id)) {
162  inComp = inCompCount.GetDat(id);
163  }
164  if (inCompCount.IsKey(neigh)) {
165  inCompN = inCompCount.GetDat(neigh);
166  }
167 
168  if (inCompN < neighDeg && inComp < deg && (!g1->IsNode(neigh) || Graph->GetNI(neigh).GetDeg() - neighDeg == 0)) {
169  inCompCount.AddDat(neigh, ++inCompN);
170  inCompCount.AddDat(id, ++inComp);
171  out = true;
172  } else {
173  out = false;
174  }
175  }
176  return out;
177 }
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:483
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
bool inComp(PNGraph &g1, PNGraph &Graph, TIntH &inCompCount, int id, int neigh)
Definition: cmty.cpp:150
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:477
int GetDeg() const
Returns degree of the current node, the sum of in-degree and out-degree.
Definition: graph.h:358
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
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.

214  {
215  // NOW NEW stuff add another additional iteration:
216 
217  bool n1new = false;
218  bool n2new = false;
219 
220  // add edge
221  if (!Graph->IsNode(n1)){
222  Graph->AddNode(n1);
223  n1new = true;
224  }
225 
226  if (!Graph->IsNode(n2)) {
227  Graph->AddNode(n2);
228  n2new = true;
229  }
230 
231  Graph->AddEdge(n1, n2);
232 
233  int e = Graph->GetEdges();
234 
235  // get previous alpha for 27
236  double oldAlphaN1 = 0.0;
237  double oldAlphaN2 = 0.0;
238 
239  if (!n1new)
240  oldAlphaN1 = PAlpha.GetDat(n1);
241 
242  if (!n2new)
243  oldAlphaN2 = PAlpha.GetDat(n2);
244 
245  // update alpha for 27
246  TUNGraph::TNodeI node = Graph->GetNI(n1);
247  int nodeDeg = node.GetDeg();
248  float d = ((float)nodeDeg / (float)(2 * e));
249  PAlpha.AddDat(n1, d);
250 
251  //update alphasum
252  SumPAlphaLogPAlpha = SumPAlphaLogPAlpha - oldAlphaN1 + d*log(d);
253 
254  if (n1new) {
255  Module.AddDat(n1, Br);
256  Qi.AddDat(Br, 1.0);
257  Br++;
258  }
259 
260  // update alpha for 28
261  node = Graph->GetNI(n2);
262  nodeDeg = node.GetDeg();
263  d = ((float)nodeDeg / (float)(2 * e));
264  PAlpha.AddDat(n2, d);
265 
266  //update alphasum
267  SumPAlphaLogPAlpha = SumPAlphaLogPAlpha - oldAlphaN2 + d*log(d);
268 
269  //add module
270  if (n2new) {
271  Module.AddDat(n2, Br);
272  Qi.AddDat(Br, 1.0);
273  Br++;
274  }
275 
276  // Start
277 
278  double MinCodeLength = TSnapDetail::Equation(PAlpha, SumPAlphaLogPAlpha, Qi);
279  double PrevIterationCodeLength = 0.0;
280 
281  do {
282  PrevIterationCodeLength = MinCodeLength;
283  int id[2] = { n1, n2 };
284  for (int k = 0; k<2; k++) {
285  for (int i = 0; i<Graph->GetNI(id[k]).GetDeg(); i++) {
286 
287  int OldModule = Module.GetDat(id[k]);
288  int NewModule = Module.GetDat(Graph->GetNI(id[k]).GetNbrNId(i));
289 
290  Module.AddDat(id[k], NewModule);
291 
292  TSnapDetail::MapEquationNew2Modules(Graph, Module, Qi, OldModule, NewModule);
293  double NewCodeLength = TSnapDetail::Equation(PAlpha, SumPAlphaLogPAlpha, Qi);
294  if (NewCodeLength<MinCodeLength) {
295  MinCodeLength = NewCodeLength;
296  OldModule = NewModule;
297  }
298  else {
299  Module.AddDat(id[k], OldModule);
300  }
301  }
302  }
303  } while (MinCodeLength<PrevIterationCodeLength);
304 
305  return MinCodeLength;
306 }
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:86
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
void MapEquationNew2Modules(PUNGraph &Graph, TIntH &Module, TIntFltH &Qi, int a, int b)
Definition: cmty.cpp:54
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:107
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:207
double Equation(TIntFltH &PAlpha, double &SumPAlphaLogPAlpha, TIntFltH &Qi)
Definition: cmty.cpp:109
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
void TSnap::TSnapDetail::MapEquationNew2Modules ( PUNGraph Graph,
TIntH Module,
TIntFltH Qi,
int  a,
int  b 
)

Definition at line 54 of file cmty.cpp.

54  {
55  float InModule = 0.0, OutModule = 0.0, Val;
56  int Mds[2] = { a, b };
57  for (int i = 0; i<2; i++) {
58  InModule = 0.0, OutModule = 0.0;
59  if (Qi.IsKey(Mds[i])) {
60  int CentralModule = Mds[i];
61 
62  //printf("central module: %i\n ",CentralModule);
63 
64  TIntV newM;
65  for (TUNGraph::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
66  if (Module.GetDat(NI.GetId()) == CentralModule)
67  newM.Add(NI.GetId());
68  }
69 
70  for (int j = 0; j<newM.Len(); j++) {
71  //int len1 = newM.Len();
72 
73  //int c = CentralModule;
74  for (int k = 0; k<Graph->GetNI(newM[j]).GetDeg(); k++) {
75  //int len = Graph->GetNI(newM[j]).GetDeg();
76 
77  int ids = Graph->GetNI(newM[j]).GetId();
78  int idd = Graph->GetNI(newM[j]).GetNbrNId(k);
79  int ms = Module.GetDat(ids);
80  int md = Module.GetDat(idd);
81  //int c = CentralModule;
82 
83  if (ms == md) {
84  InModule += 1.0;
85  //printf("IN: \t%i - %i; moduls: %i - %i\n", ids, idd, ms, md);
86  } else {
87  OutModule += 1.0;
88  //printf("OUT: \t%i - %i; moduls: %i - %i\n", ids, idd, ms, md);
89  }
90  }
91  }
92  if (InModule >1) InModule = InModule / 2;
93 
94  //printf("\n");
95 
96  Val = 0.0;
97  if (InModule + OutModule > 0) {
98  Val = OutModule / (InModule + OutModule);
99  }
100  //int control = Mds[i];
101  Qi.AddDat(Mds[i], Val);
102  } else {
103  //int control = Mds[i];
104  Qi.AddDat(Mds[i], 0.0);
105  }
106  }
107 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
Node iterator. Only forward iteration (operator++) is supported.
Definition: graph.h:64
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
int GetDeg() const
Returns degree of the current node.
Definition: graph.h:86
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:213
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:211
int GetNbrNId(const int &NodeN) const
Returns ID of NodeN-th neighboring node.
Definition: graph.h:107
int GetId() const
Returns ID of the current node.
Definition: graph.h:84
bool IsKey(const TKey &Key) const
Definition: hash.h:216
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:209
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
void TSnap::TSnapDetail::transitiveTransform ( TIntV a,
TIntV b 
)

Definition at line 179 of file cmty.cpp.

179  {
180  for (int i = 0; i < a.Len(); i++) {
181  bool diff = false;
182  for (int j = 0; j < b.Len(); j++) {
183  if (a[i] == a[j]) {
184  diff = true;
185  break;
186  }
187  }
188  if (!diff) {
189  b.Add(a[i]);
190  break;
191  }
192  }
193 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
int TSnap::TSnapDetail::vectorIntersect ( TIntV a,
TIntV b 
)

Definition at line 138 of file cmty.cpp.

138  {
139  int count = 0;
140  for (int i = 0; i<a.Len(); i++) {
141  for (int j = 0; j<b.Len(); j++) {
142  if (a[i] == b[j])
143  count++;
144  }
145  }
146 
147  return count;
148 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547