SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
alg.h
Go to the documentation of this file.
1 namespace TSnap {
2 
4 // Node Degrees
5 
7 template <class PGraph> int CntInDegNodes(const PGraph& Graph, const int& NodeInDeg);
9 template <class PGraph> int CntOutDegNodes(const PGraph& Graph, const int& NodeOutDeg);
11 template <class PGraph> int CntDegNodes(const PGraph& Graph, const int& NodeDeg);
13 template <class PGraph> int CntNonZNodes(const PGraph& Graph);
15 template <class PGraph> int CntEdgesToSet(const PGraph& Graph, const int& NId, const TIntSet& NodeSet);
16 
18 template <class PGraph> int GetMxDegNId(const PGraph& Graph);
20 template <class PGraph> int GetMxInDegNId(const PGraph& Graph);
22 template <class PGraph> int GetMxOutDegNId(const PGraph& Graph);
23 
24 // degree histograms
26 template <class PGraph> void GetInDegCnt(const PGraph& Graph, TIntPrV& DegToCntV);
28 template <class PGraph> void GetInDegCnt(const PGraph& Graph, TFltPrV& DegToCntV);
30 template <class PGraph> void GetOutDegCnt(const PGraph& Graph, TIntPrV& DegToCntV);
32 template <class PGraph> void GetOutDegCnt(const PGraph& Graph, TFltPrV& DegToCntV);
34 template <class PGraph> void GetDegCnt(const PGraph& Graph, TIntPrV& DegToCntV);
36 template <class PGraph> void GetDegCnt(const PGraph& Graph, TFltPrV& DegToCntV);
38 template <class PGraph> void GetDegSeqV(const PGraph& Graph, TIntV& DegV);
40 template <class PGraph> void GetDegSeqV(const PGraph& Graph, TIntV& InDegV, TIntV& OutDegV);
41 
43 template <class PGraph> void GetNodeInDegV(const PGraph& Graph, TIntPrV& NIdInDegV);
45 template <class PGraph> void GetNodeOutDegV(const PGraph& Graph, TIntPrV& NIdOutDegV);
46 
48 template <class PGraph> int CntUniqUndirEdges(const PGraph& Graph);
50 template <class PGraph> int CntUniqDirEdges(const PGraph& Graph);
52 template <class PGraph> int CntUniqBiDirEdges(const PGraph& Graph);
54 template <class PGraph> int CntSelfEdges(const PGraph& Graph);
55 
57 // Manipulation
59 template <class PGraph> PGraph GetUnDir(const PGraph& Graph);
61 template <class PGraph> void MakeUnDir(const PGraph& Graph);
63 template <class PGraph> void AddSelfEdges(const PGraph& Graph);
65 template <class PGraph> void DelSelfEdges(const PGraph& Graph);
66 
67 //TODO Implement:
68 //template <class PGraph> void DelBiDirEdges(const PGraph& Graph);
69 
71 template <class PGraph> void DelNodes(PGraph& Graph, const TIntV& NIdV);
73 template <class PGraph> void DelZeroDegNodes(PGraph& Graph);
75 template <class PGraph> void DelDegKNodes(PGraph& Graph, const int& OutDegK, const int& InDegK);
76 
78 // Tree Routines
79 template <class PGraph> bool IsTree(const PGraph& Graph, int& RootNIdX);
80 template <class PGraph> int GetTreeRootNId(const PGraph& Graph) { int RootNId; bool Tree; Tree = IsTree(Graph, RootNId); Assert(Tree); return RootNId; }
81 template <class PGraph> void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig);
82 template <class PGraph> void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig, TIntPrV& NodeMap);
83 
85 // Implementation
86 template <class PGraph>
87 int CntInDegNodes(const PGraph& Graph, const int& NodeInDeg) {
88  int Cnt = 0;
89  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
90  if (NI.GetInDeg() == NodeInDeg) Cnt++;
91  }
92  return Cnt;
93 }
94 
95 template <class PGraph>
96 int CntOutDegNodes(const PGraph& Graph, const int& NodeOutDeg) {
97  int Cnt = 0;
98  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
99  if (NI.GetOutDeg() == NodeOutDeg) Cnt++;
100  }
101  return Cnt;
102 }
103 
104 template <class PGraph>
105 int CntDegNodes(const PGraph& Graph, const int& NodeDeg) {
106  int Cnt = 0;
107  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
108  if (NI.GetDeg() == NodeDeg) Cnt++;
109  }
110  return Cnt;
111 }
112 
113 template <class PGraph>
114 int CntNonZNodes(const PGraph& Graph) {
115  int Cnt = 0;
116  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
117  if (NI.GetDeg() > 0) Cnt++;
118  }
119  return Cnt;
120 }
121 
122 template <class PGraph>
123 int CntEdgesToSet(const PGraph& Graph, const int& NId, const TIntSet& NodeSet) {
124  if (! Graph->IsNode(NId)) { return 0; }
125  const bool IsDir = Graph->HasFlag(gfDirected);
126  const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
127  if (! IsDir) {
128  int EdgesToSet = 0;
129  for (int e = 0; e < NI.GetOutDeg(); e++) {
130  if (NodeSet.IsKey(NI.GetOutNId(e))) { EdgesToSet++; } }
131  return EdgesToSet;
132  } else {
133  TIntSet Set(NI.GetDeg());
134  for (int e = 0; e < NI.GetOutDeg(); e++) {
135  if (NodeSet.IsKey(NI.GetOutNId(e))) { Set.AddKey(NI.GetOutNId(e)); } }
136  for (int e = 0; e < NI.GetInDeg(); e++) {
137  if (NodeSet.IsKey(NI.GetInNId(e))) { Set.AddKey(NI.GetInNId(e)); } }
138  return Set.Len();
139  }
140 }
141 
142 template <class PGraph>
143 int GetMxDegNId(const PGraph& Graph) {
144  TIntV MxDegV;
145  int MxDeg=-1;
146  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
147  if (MxDeg < NI.GetDeg()) { MxDegV.Clr(); MxDeg = NI.GetDeg(); }
148  if (MxDeg == NI.GetDeg()) { MxDegV.Add(NI.GetId()); }
149  }
150  EAssertR(! MxDegV.Empty(), "Input graph is empty!");
151  return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
152 }
153 
154 template <class PGraph>
155 int GetMxInDegNId(const PGraph& Graph) {
156  TIntV MxDegV;
157  int MxDeg=-1;
158  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
159  if (MxDeg < NI.GetInDeg()) { MxDegV.Clr(); MxDeg = NI.GetInDeg(); }
160  if (MxDeg == NI.GetInDeg()) { MxDegV.Add(NI.GetId()); }
161  }
162  EAssertR(! MxDegV.Empty(), "Input graph is empty!");
163  return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
164 }
165 
166 template <class PGraph>
167 int GetMxOutDegNId(const PGraph& Graph) {
168  TIntV MxDegV;
169  int MxDeg=-1;
170  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
171  if (MxDeg < NI.GetOutDeg()) { MxDegV.Clr(); MxDeg = NI.GetOutDeg(); }
172  if (MxDeg == NI.GetOutDeg()) { MxDegV.Add(NI.GetId()); }
173  }
174  EAssertR(! MxDegV.Empty(), "Input graph is empty!");
175  return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
176 }
177 
178 template <class PGraph>
179 void GetInDegCnt(const PGraph& Graph, TIntPrV& DegToCntV) {
180  TIntH DegToCntH;
181  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
182  DegToCntH.AddDat(NI.GetInDeg())++; }
183  DegToCntV.Gen(DegToCntH.Len(), 0);
184  for (int i = 0; i < DegToCntH.Len(); i++) {
185  DegToCntV.Add(TIntPr(DegToCntH.GetKey(i), DegToCntH[i])); }
186  DegToCntV.Sort();
187 }
188 
189 template <class PGraph>
190 void GetInDegCnt(const PGraph& Graph, TFltPrV& DegToCntV) {
191  TIntH DegToCntH;
192  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
193  DegToCntH.AddDat(NI.GetInDeg())++; }
194  DegToCntV.Gen(DegToCntH.Len(), 0);
195  for (int i = 0; i < DegToCntH.Len(); i++) {
196  DegToCntV.Add(TFltPr(DegToCntH.GetKey(i).Val, DegToCntH[i].Val)); }
197  DegToCntV.Sort();
198 }
199 
200 template <class PGraph>
201 void GetOutDegCnt(const PGraph& Graph, TIntPrV& DegToCntV) {
202  TIntH DegToCntH;
203  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
204  DegToCntH.AddDat(NI.GetOutDeg())++; }
205  DegToCntV.Gen(DegToCntH.Len(), 0);
206  for (int i = 0; i < DegToCntH.Len(); i++) {
207  DegToCntV.Add(TIntPr(DegToCntH.GetKey(i), DegToCntH[i])); }
208  DegToCntV.Sort();
209 }
210 
211 template <class PGraph>
212 void GetOutDegCnt(const PGraph& Graph, TFltPrV& DegToCntV) {
213  TIntH DegToCntH;
214  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
215  DegToCntH.AddDat(NI.GetOutDeg())++; }
216  DegToCntV.Gen(DegToCntH.Len(), 0);
217  for (int i = 0; i < DegToCntH.Len(); i++) {
218  DegToCntV.Add(TFltPr(DegToCntH.GetKey(i).Val, DegToCntH[i].Val)); }
219  DegToCntV.Sort();
220 }
221 
222 template <class PGraph>
223 void GetDegCnt(const PGraph& Graph, TIntPrV& DegToCntV) {
224  TIntH DegToCntH;
225  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
226  DegToCntH.AddDat(NI.GetDeg())++; }
227  DegToCntV.Gen(DegToCntH.Len(), 0);
228  for (int i = 0; i < DegToCntH.Len(); i++) {
229  DegToCntV.Add(TIntPr(DegToCntH.GetKey(i), DegToCntH[i])); }
230  DegToCntV.Sort();
231 }
232 
233 template <class PGraph>
234 void GetDegCnt(const PGraph& Graph, TFltPrV& DegToCntV) {
235  TIntH DegToCntH;
236  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
237  DegToCntH.AddDat(NI.GetDeg())++; }
238  DegToCntV.Gen(DegToCntH.Len(), 0);
239  for (int i = 0; i < DegToCntH.Len(); i++) {
240  DegToCntV.Add(TFltPr(DegToCntH.GetKey(i).Val, DegToCntH[i].Val)); }
241  DegToCntV.Sort();
242 }
243 
244 template <class PGraph>
245 void GetDegSeqV(const PGraph& Graph, TIntV& DegV) {
246  DegV.Gen(Graph->GetNodes(), 0);
247  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
248  DegV.Add(NI.GetDeg());
249  }
250 }
251 
252 template <class PGraph>
253 void GetDegSeqV(const PGraph& Graph, TIntV& InDegV, TIntV& OutDegV) {
254  InDegV.Gen(Graph->GetNodes(), 0);
255  OutDegV.Gen(Graph->GetNodes(), 0);
256  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
257  InDegV.Add(NI.GetInDeg());
258  OutDegV.Add(NI.GetOutDeg());
259  }
260 }
261 
262 template <class PGraph>
263 void GetNodeInDegV(const PGraph& Graph, TIntPrV& NIdInDegV) {
264  NIdInDegV.Reserve(Graph->GetNodes(), 0);
265  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
266  NIdInDegV.Add(TIntPr(NI.GetId(), NI.GetInDeg()));
267  }
268 }
269 
270 template <class PGraph>
271 void GetNodeOutDegV(const PGraph& Graph, TIntPrV& NIdOutDegV) {
272  NIdOutDegV.Reserve(Graph->GetNodes(), 0);
273  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
274  NIdOutDegV.Add(TIntPr(NI.GetId(), NI.GetOutDeg()));
275  }
276 }
277 
278 template <class PGraph>
279 int CntUniqUndirEdges(const PGraph& Graph) {
280  TIntSet NbrSet;
281  TIntSet SelfNbrSet;
282  int Cnt = 0;
283  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
284  NbrSet.Clr(false);
285  for (int e = 0; e < NI.GetDeg(); e++) { // unique neighbors of a node
286  const int NbrId = NI.GetNbrNId(e);
287  if (NbrId == NI.GetId()) { // remember self-edges
288  SelfNbrSet.AddKey(NbrId);
289  } else {
290  NbrSet.AddKey(NbrId);
291  }
292  }
293  Cnt += NbrSet.Len();
294  }
295  // OP RS 2014/06/11 self-edges are currently not used
296  //return Cnt / 2 + SelfNbrSet.Len();
297  return Cnt / 2;
298 }
299 
300 template <class PGraph>
301 int CntUniqDirEdges(const PGraph& Graph) {
302  TIntSet NbrSet;
303  int Cnt = 0;
304  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
305  NbrSet.Clr(false);
306  for (int e = 0; e < NI.GetOutDeg(); e++) { // unique out-neighbors of a node
307  if (NI.GetOutNId(e) != NI.GetId()) { // skip self-edges
308  NbrSet.AddKey(NI.GetOutNId(e)); }
309  }
310  Cnt += NbrSet.Len();
311  }
312  return Cnt;
313 }
314 
315 template <class PGraph>
316 int CntUniqBiDirEdges(const PGraph& Graph) {
317  if (! Graph->HasFlag(gfDirected)) { // graph is undirected
318  return CntUniqUndirEdges(Graph); // then every edge is bi-directional
319  }
320  TIntSet NbrSet;
321  int Cnt = 0;
322  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
323  const int SrcId = NI.GetId();
324  for (int e = 0; e < NI.GetOutDeg(); e++) {
325  const int DstId = NI.GetOutNId(e);
326  if (DstId <= SrcId) { continue; } // count each un-dir edge only once
327  if (Graph->IsEdge(DstId, SrcId)) { Cnt++; }
328  }
329  }
330  return Cnt;
331 }
332 
333 template <class PGraph>
334 int CntSelfEdges(const PGraph& Graph) {
335  int Cnt = 0;
336  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
337  for (int e = 0; e < NI.GetOutDeg(); e++) {
338  if (NI.GetId() == NI.GetOutNId(e)) { Cnt++; }
339  }
340  }
341  return Cnt;
342 }
343 
344 template <class PGraph>
345 PGraph GetUnDir(const PGraph& Graph) {
346  PGraph NewGraphPt = PGraph::New();
347  *NewGraphPt = *Graph;
348  MakeUnDir(NewGraphPt);
349  return NewGraphPt;
350 }
351 
352 template <class PGraph>
353 void MakeUnDir(const PGraph& Graph) {
354  CAssert(HasGraphFlag(typename PGraph::TObj, gfDirected)); // graph has to be directed
355  TIntPrV EdgeV;
356  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
357  const int SrcNId = EI.GetSrcNId();
358  const int DstNId = EI.GetDstNId();
359  if (! Graph->IsEdge(DstNId, SrcNId)) {
360  EdgeV.Add(TIntPr(DstNId, SrcNId));
361  }
362  }
363  for (int i = 0; i < EdgeV.Len(); i++) {
364  Graph->AddEdge(EdgeV[i].Val1, EdgeV[i].Val2);
365  }
366 }
367 
368 template <class PGraph>
369 void AddSelfEdges(const PGraph& Graph) {
370  TIntV EdgeV;
371  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
372  const int NId = NI.GetId();
373  if (! Graph->IsEdge(NId, NId)) {
374  EdgeV.Add(NId);
375  }
376  }
377  for (int i = 0; i < EdgeV.Len(); i++) {
378  Graph->AddEdge(EdgeV[i], EdgeV[i]);
379  }
380 }
381 
382 namespace TSnapDetail {
383 
384 template <class PGraph, bool IsMultiGraph>
385 struct TDelSelfEdges { // not a multigraph graph
386  static void Do(const PGraph& Graph) {
387  TIntV EdgeV;
388  // node graph, no explicit edge ids
389  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
390  if (EI.GetSrcNId() == EI.GetDstNId()) {
391  EdgeV.Add(EI.GetSrcNId());
392  }
393  }
394  for (int i = 0; i < EdgeV.Len(); i++) {
395  Graph->DelEdge(EdgeV[i], EdgeV[i]);
396  }
397  }
398 };
399 
400 template <class PGraph>
401 struct TDelSelfEdges<PGraph, true> { // mutligraph specialization
402  static void Do(const PGraph& Graph) {
403  TIntV EdgeV;
404  for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
405  if (EI.GetSrcNId() == EI.GetDstNId()) {
406  IAssert(EI.GetId() >= 0); // real edge id
407  EdgeV.Add(EI.GetId());
408  }
409  }
410  for (int i = 0; i < EdgeV.Len(); i++) { // delete all edges between a pair of nodes
411  Graph->DelEdge(EdgeV[i]);
412  }
413  }
414 };
415 
416 } // namespace TSnapDetail
417 
418 template <class PGraph>
419 void DelSelfEdges(const PGraph& Graph) {
420  TSnapDetail::TDelSelfEdges<PGraph, HasGraphFlag(typename PGraph::TObj, gfMultiGraph)>
421  ::Do(Graph);
422 }
423 
424 template <class PGraph>
425 void DelNodes(PGraph& Graph, const TIntV& NIdV) {
426  for (int n = 0; n < NIdV.Len(); n++) {
427  Graph->DelNode(NIdV[n]);
428  }
429 }
430 
431 template <class PGraph>
432 void DelZeroDegNodes(PGraph& Graph) {
433  TIntV DelNIdV;
434  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
435  if (NI.GetDeg() == 0) {
436  DelNIdV.Add(NI.GetId());
437  }
438  }
439  for (int i = 0; i < DelNIdV.Len(); i++) {
440  Graph->DelNode(DelNIdV[i]);
441  }
442 }
443 
444 template <class PGraph>
445 void DelDegKNodes(PGraph& Graph, const int& OutDegK, const int& InDegK) {
446  TIntV DelNIdV;
447  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
448  if (NI.GetOutDeg() == OutDegK || NI.GetInDeg() == InDegK) {
449  DelNIdV.Add(NI.GetId());
450  }
451  }
452  for (int i = 0; i < DelNIdV.Len(); i++) {
453  Graph->DelNode(DelNIdV[i]);
454  }
455 }
456 
457 // tree has directed edges -- so root is a well-defined
458 // children point to a parent
459 template <class PGraph>
460 bool IsTree(const PGraph& Graph, int& RootNId) {
461  if (Graph->GetNodes() == 1 && Graph->GetEdges() == 0) {
462  RootNId = Graph->BegNI().GetId();
463  return true;
464  }
465  RootNId = -1;
466  if (Graph->GetNodes() != Graph->GetEdges()+1) { return false; }
467  int NZeroOutDeg = 0;
468  int ZeroOutDegN = -1;
469  for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
470  if (NI.GetOutDeg() == 0) {
471  ZeroOutDegN = NI.GetId(); NZeroOutDeg++;
472  }
473  if (NI.GetDeg() == 0) { return false; } // isolated nodes
474  }
475  if (NZeroOutDeg==1) {
476  if (! TSnap::IsConnected(Graph)) { return false; }
477  RootNId = ZeroOutDegN; return true;
478  }
479  return false;
480 }
481 
482 // tree signature -- for each level we sort the node in-degrees and concatenate them into a vector
483 template <class PGraph>
484 void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig) {
485  CAssert(HasGraphFlag(typename PGraph::TObj, gfDirected));
486  Sig.Gen(Graph->GetNodes(), 0);
487  TSnapQueue<int> NIdQ(Graph->GetNodes());
488  NIdQ.Push(RootNId);
489  int LastPos = 0, NodeCnt = 1;
490  while (! NIdQ.Empty()) {
491  const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top()); NIdQ.Pop();
492  IAssert(Node.GetInDeg()==0 || Node.GetOutDeg()==0); // child points or is-pointed to by the parent
493  if (Node.GetInDeg() != 0) {
494  for (int e = 0; e < Node.GetInDeg(); e++) {
495  NIdQ.Push(Node.GetInNId(e)); }
496  } else if (Node.GetOutDeg() != 0) {
497  for (int e = 0; e < Node.GetOutDeg(); e++) {
498  NIdQ.Push(Node.GetOutNId(e)); }
499  }
500  Sig.Add(Node.GetInDeg());
501  if (--NodeCnt == 0) {
502  for (int i = LastPos; i < Sig.Len(); i++) NodeCnt += Sig[i];
503  Sig.QSort(LastPos, Sig.Len()-1, false);
504  LastPos = Sig.Len();
505  }
506  }
507 }
508 
509 // tree signature -- for each level we sort the node in-degrees and concatenate them into a vector
510 template <class PGraph>
511 void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig, TIntPrV& NodeMap) {
512  CAssert(HasGraphFlag(typename PGraph::TObj, gfDirected));
513  NodeMap.Gen(Graph->GetNodes(), 0);
514  Sig.Gen(Graph->GetNodes(), 0);
515  TSnapQueue<int> NIdQ(Graph->GetNodes());
516  NIdQ.Push(RootNId);
517  int LastPos = 0, NodeCnt = 1;
518  while (! NIdQ.Empty()) {
519  const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top()); NIdQ.Pop();
520  IAssert(Node.GetInDeg()==0 || Node.GetOutDeg()==0); // child points or is-pointed to by the parent
521  if (Node.GetInDeg() != 0) {
522  for (int e = 0; e < Node.GetInDeg(); e++) {
523  NIdQ.Push(Node.GetInNId(e)); }
524  NodeMap.Add(TIntPr(Node.GetInDeg(), Node.GetId()));
525  } else if (Node.GetOutDeg() != 0) {
526  for (int e = 0; e < Node.GetOutDeg(); e++) {
527  NIdQ.Push(Node.GetOutNId(e)); }
528  NodeMap.Add(TIntPr(Node.GetOutDeg(), Node.GetId()));
529  }
530  if (--NodeCnt == 0) {
531  for (int i = LastPos; i < NodeMap.Len(); i++) {
532  NodeCnt += NodeMap[i].Val1; }
533  NodeMap.QSort(LastPos, NodeMap.Len()-1, false);
534  LastPos = NodeMap.Len();
535  }
536  }
537  for (int i = 0; i < NodeMap.Len(); i++) {
538  Sig.Add(NodeMap[i].Val1); // degree dignature
539  NodeMap[i].Val1 = NodeMap[i].Val2;
540  NodeMap[i].Val2 = i;
541  }
542 }
543 
544 }; // namespace TSnap
THashSet::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TIntPr
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TSnap
Main namespace for all the Snap global entities.
Definition: alg.h:1
TSnap::GetOutDegCnt
void GetOutDegCnt(const PGraph &Graph, TIntPrV &DegToCntV)
Returns an out-degree histogram: a set of pairs (out-degree, number of nodes of such out-degree) ...
Definition: alg.h:201
TSnap::CntUniqUndirEdges
int CntUniqUndirEdges(const PGraph &Graph)
Counts unique undirected edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via an undi...
Definition: alg.h:279
TSnap::GetNodeOutDegV
void GetNodeOutDegV(const PGraph &Graph, TIntPrV &NIdOutDegV)
Returns a vector of pairs (node id, node out-degree)
Definition: alg.h:271
TSnap::GetDegCnt
void GetDegCnt(const PGraph &Graph, TIntPrV &DegToCntV)
Returns a degree histogram: a set of pairs (degree, number of nodes of such degree) ...
Definition: alg.h:223
TVec::QSort
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1305
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSnap::GetNodeInDegV
void GetNodeInDegV(const PGraph &Graph, TIntPrV &NIdInDegV)
Returns a vector of pairs (node id, node in-degree)
Definition: alg.h:263
TSnap::CntUniqDirEdges
int CntUniqDirEdges(const PGraph &Graph)
Counts unique directed edges in the graph Graph. Nodes (u,v) (where u!=v) are connected via a directe...
Definition: alg.h:301
TInt::Rnd
static TRnd Rnd
Definition: dt.h:1146
THashSet::IsKey
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
TSnap::MakeUnDir
void MakeUnDir(const PGraph &Graph)
Makes the graph undirected. For every edge (u,v) an edge (v,u) is added (if it does not yet exist)...
Definition: alg.h:353
TSnap::GetTreeSig
void GetTreeSig(const PGraph &Graph, const int &RootNId, TIntV &Sig)
Definition: alg.h:484
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TSnap::IsTree
bool IsTree(const PGraph &Graph, int &RootNIdX)
Definition: alg.h:460
TSnap::DelZeroDegNodes
void DelZeroDegNodes(PGraph &Graph)
Removes all the zero-degree nodes, that isolated nodes, from the graph.
Definition: alg.h:432
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TSnap::GetDegSeqV
void GetDegSeqV(const PGraph &Graph, TIntV &DegV)
Returns a degree sequence vector.
Definition: alg.h:245
TSnap::GetInDegCnt
void GetInDegCnt(const PGraph &Graph, TIntPrV &DegToCntV)
Returns an in-degree histogram: a set of pairs (in-degree, number of nodes of such in-degree) ...
Definition: alg.h:179
TSnap::CntSelfEdges
int CntSelfEdges(const PGraph &Graph)
Counts the number of self-edges in a graph. Edge (u,u) is a self-edge.
Definition: alg.h:334
TSnap::GetTreeRootNId
int GetTreeRootNId(const PGraph &Graph)
Definition: alg.h:80
TVec::Sort
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
HasGraphFlag
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
TSnap::CntNonZNodes
int CntNonZNodes(const PGraph &Graph)
Returns the number of nodes with degree greater than 0.
Definition: alg.h:114
TSnap::GetMxOutDegNId
int GetMxOutDegNId(const PGraph &Graph)
Returns a randomly chosen node from all the nodes with the maximum out-degree.
Definition: alg.h:167
Assert
#define Assert(Cond)
Definition: bd.h:251
THashSet::AddKey
int AddKey(const TKey &Key)
Definition: shash.h:1254
TSnap::TSnapDetail::TDelSelfEdges::Do
static void Do(const PGraph &Graph)
Definition: alg.h:386
TSnap::CntEdgesToSet
int CntEdgesToSet(const PGraph &Graph, const int &NId, const TIntSet &NodeSet)
Returns the number of nodes in NodeSet that have an edge to the node NId.
Definition: alg.h:123
TSnap::CntUniqBiDirEdges
int CntUniqBiDirEdges(const PGraph &Graph)
Counts unique bidirectional edges in the graph Graph. Edge is bidirectional if there exist directed e...
Definition: alg.h:316
TFltPr
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
TSnap::CntInDegNodes
int CntInDegNodes(const PGraph &Graph, const int &NodeInDeg)
Returns the number of nodes with in-degree NodeInDeg.
Definition: alg.h:87
TSnap::AddSelfEdges
void AddSelfEdges(const PGraph &Graph)
Adds a self-edge to every node in the graph.
Definition: alg.h:369
gfDirected
directed graph (TNGraph, TNEGraph), else graph is undirected TUNGraph
Definition: gbase.h:13
CAssert
#define CAssert(Cond)
Definition: bd.h:302
THashSet::Len
int Len() const
Definition: shash.h:1121
TSnap::GetMxDegNId
int GetMxDegNId(const PGraph &Graph)
Returns a randomly chosen node from all the nodes with the maximum degree.
Definition: alg.h:143
TSnap::IsConnected
bool IsConnected(const PGraph &Graph)
Tests whether the Graph is (weakly) connected.
Definition: cncom.h:305
TSnapQueue::Push
void Push(const TVal &Val)
Adds an element at the end of the queue.
Definition: gbase.h:214
THash
Definition: hash.h:97
TSnap::DelNodes
void DelNodes(PGraph &Graph, const TIntV &NIdV)
Removes nodes with ids stored in NIdV from the graph.
Definition: alg.h:425
EAssertR
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
TSnap::TSnapDetail::TDelSelfEdges< PGraph, true >::Do
static void Do(const PGraph &Graph)
Definition: alg.h:402
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TVec::Reserve
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
TSnap::DelDegKNodes
void DelDegKNodes(PGraph &Graph, const int &OutDegK, const int &InDegK)
Removes all the node of out-degree OutDegK and all the nodes of in-degree InDegK from the graph...
Definition: alg.h:445
TSnap::CntDegNodes
int CntDegNodes(const PGraph &Graph, const int &NodeDeg)
Returns the number of nodes with degree NodeDeg.
Definition: alg.h:105
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TSnap::DelSelfEdges
void DelSelfEdges(const PGraph &Graph)
Removes all the self-edges from the graph.
Definition: alg.h:419
THash::Len
int Len() const
Definition: hash.h:228
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TSnap::GetMxInDegNId
int GetMxInDegNId(const PGraph &Graph)
Returns a randomly chosen node from all the nodes with the maximum in-degree.
Definition: alg.h:155
TSnap::GetUnDir
PGraph GetUnDir(const PGraph &Graph)
Returs an undirected version of the graph. For every edge (u,v) an edge (v,u) is added (if it does no...
Definition: alg.h:345
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TSnap::CntOutDegNodes
int CntOutDegNodes(const PGraph &Graph, const int &NodeOutDeg)
Returns the number of nodes with out-degree NodeOutDeg.
Definition: alg.h:96