SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
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::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:1143
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:201
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