SNAP Library 2.1, User Reference  2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
alg.h
Go to the documentation of this file.
00001 namespace TSnap {
00002 
00004 // Node Degrees
00005 
00007 template <class PGraph> int CntInDegNodes(const PGraph& Graph, const int& NodeInDeg);
00009 template <class PGraph> int CntOutDegNodes(const PGraph& Graph, const int& NodeOutDeg);
00011 template <class PGraph> int CntDegNodes(const PGraph& Graph, const int& NodeDeg);
00013 template <class PGraph> int CntNonZNodes(const PGraph& Graph);
00014 // TODO ROK document CntEdgesToSet()
00015 template <class PGraph> int CntEdgesToSet(const PGraph& Graph, const int& NId, const TIntSet& NodeSet);
00016 
00018 template <class PGraph> int GetMxDegNId(const PGraph& Graph);
00020 template <class PGraph> int GetMxInDegNId(const PGraph& Graph);
00022 template <class PGraph> int GetMxOutDegNId(const PGraph& Graph);
00023 
00024 // degree histograms
00026 template <class PGraph> void GetInDegCnt(const PGraph& Graph, TIntPrV& DegToCntV);
00028 template <class PGraph> void GetInDegCnt(const PGraph& Graph, TFltPrV& DegToCntV);
00030 template <class PGraph> void GetOutDegCnt(const PGraph& Graph, TIntPrV& DegToCntV);
00032 template <class PGraph> void GetOutDegCnt(const PGraph& Graph, TFltPrV& DegToCntV);
00034 template <class PGraph> void GetDegCnt(const PGraph& Graph, TIntPrV& DegToCntV);
00036 template <class PGraph> void GetDegCnt(const PGraph& Graph, TFltPrV& DegToCntV);
00038 template <class PGraph> void GetDegSeqV(const PGraph& Graph, TIntV& DegV);
00040 template <class PGraph> void GetDegSeqV(const PGraph& Graph, TIntV& InDegV, TIntV& OutDegV);
00041 
00043 template <class PGraph> void GetNodeInDegV(const PGraph& Graph, TIntPrV& NIdInDegV);
00045 template <class PGraph> void GetNodeOutDegV(const PGraph& Graph, TIntPrV& NIdOutDegV);
00046 
00048 template <class PGraph> int CntUniqUndirEdges(const PGraph& Graph);
00050 template <class PGraph> int CntUniqDirEdges(const PGraph& Graph);
00052 template <class PGraph> int CntUniqBiDirEdges(const PGraph& Graph);
00054 template <class PGraph> int CntSelfEdges(const PGraph& Graph);
00055 
00057 // Manipulation
00059 template <class PGraph> PGraph GetUnDir(const PGraph& Graph);
00061 template <class PGraph> void MakeUnDir(const PGraph& Graph);
00063 template <class PGraph> void AddSelfEdges(const PGraph& Graph);
00065 template <class PGraph> void DelSelfEdges(const PGraph& Graph);
00066 
00067 //TODO Implement:
00068 //template <class PGraph> void DelBiDirEdges(const PGraph& Graph);
00069 
00071 template <class PGraph> void DelNodes(PGraph& Graph, const TIntV& NIdV);
00073 template <class PGraph> void DelZeroDegNodes(PGraph& Graph);
00075 template <class PGraph> void DelDegKNodes(PGraph& Graph, const int& OutDegK, const int& InDegK);
00076 
00078 // Tree Routines
00079 template <class PGraph> bool IsTree(const PGraph& Graph, int& RootNId);
00080 template <class PGraph> int GetTreeRootNId(const PGraph& Graph) { int RootNId; bool Tree; Tree = IsTree(Graph, RootNId);  Assert(Tree);  return RootNId; }
00081 template <class PGraph> void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig);
00082 template <class PGraph> void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig, TIntPrV& NodeMap);
00083 
00085 // Implementation
00086 template <class PGraph>
00087 int CntInDegNodes(const PGraph& Graph, const int& NodeInDeg) {
00088   int Cnt = 0;
00089   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00090     if (NI.GetInDeg() == NodeInDeg) Cnt++;
00091   }
00092   return Cnt;
00093 }
00094 
00095 template <class PGraph>
00096 int CntOutDegNodes(const PGraph& Graph, const int& NodeOutDeg) {
00097   int Cnt = 0;
00098   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00099     if (NI.GetOutDeg() == NodeOutDeg) Cnt++;
00100   }
00101   return Cnt;
00102 }
00103 
00104 template <class PGraph>
00105 int CntDegNodes(const PGraph& Graph, const int& NodeDeg) {
00106   int Cnt = 0;
00107   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00108     if (NI.GetDeg() == NodeDeg) Cnt++;
00109   }
00110   return Cnt;
00111 }
00112 
00113 template <class PGraph>
00114 int CntNonZNodes(const PGraph& Graph) {
00115   int Cnt = 0;
00116   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00117     if (NI.GetDeg() > 0) Cnt++;
00118   }
00119   return Cnt;
00120 }
00121 
00122 template <class PGraph> 
00123 int CntEdgesToSet(const PGraph& Graph, const int& NId, const TIntSet& NodeSet) {
00124   if (! Graph->IsNode(NId)) { return 0; }
00125   const bool IsDir = Graph->HasFlag(gfDirected);
00126   const typename PGraph::TObj::TNodeI NI = Graph->GetNI(NId);
00127   if (! IsDir) {
00128     int EdgesToSet = 0;
00129     for (int e = 0; e < NI.GetOutDeg(); e++) {
00130       if (NodeSet.IsKey(NI.GetOutNId(e))) { EdgesToSet++; } }
00131     return EdgesToSet;
00132   } else {
00133     TIntSet Set(NI.GetDeg());
00134     for (int e = 0; e < NI.GetOutDeg(); e++) {
00135       if (NodeSet.IsKey(NI.GetOutNId(e))) { Set.AddKey(NI.GetOutNId(e)); } }
00136     for (int e = 0; e < NI.GetInDeg(); e++) {
00137       if (NodeSet.IsKey(NI.GetInNId(e))) { Set.AddKey(NI.GetInNId(e)); } }
00138     return Set.Len();
00139   }
00140 }
00141 
00142 template <class PGraph> 
00143 int GetMxDegNId(const PGraph& Graph) {
00144   TIntV MxDegV;
00145   int MxDeg=-1;
00146   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00147     if (MxDeg < NI.GetDeg()) { MxDegV.Clr(); MxDeg = NI.GetDeg(); }
00148     if (MxDeg == NI.GetDeg()) { MxDegV.Add(NI.GetId()); }
00149   }
00150   EAssertR(! MxDegV.Empty(), "Input graph is empty!");
00151   return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
00152 }
00153 
00154 template <class PGraph> 
00155 int GetMxInDegNId(const PGraph& Graph) {
00156   TIntV MxDegV;
00157   int MxDeg=-1;
00158   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00159     if (MxDeg < NI.GetInDeg()) { MxDegV.Clr(); MxDeg = NI.GetInDeg(); }
00160     if (MxDeg == NI.GetInDeg()) { MxDegV.Add(NI.GetId()); }
00161   }
00162   EAssertR(! MxDegV.Empty(), "Input graph is empty!");
00163   return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
00164 }
00165 
00166 template <class PGraph> 
00167 int GetMxOutDegNId(const PGraph& Graph) {
00168   TIntV MxDegV;
00169   int MxDeg=-1;
00170   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00171     if (MxDeg < NI.GetOutDeg()) { MxDegV.Clr(); MxDeg = NI.GetOutDeg(); }
00172     if (MxDeg == NI.GetOutDeg()) { MxDegV.Add(NI.GetId()); }
00173   }
00174   EAssertR(! MxDegV.Empty(), "Input graph is empty!");
00175   return MxDegV[TInt::Rnd.GetUniDevInt(MxDegV.Len())];
00176 }
00177 
00178 template <class PGraph>
00179 void GetInDegCnt(const PGraph& Graph, TIntPrV& DegToCntV) {
00180   TIntH DegToCntH;
00181   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00182     DegToCntH.AddDat(NI.GetInDeg())++; }
00183   DegToCntV.Gen(DegToCntH.Len(), 0);
00184   for (int i = 0; i < DegToCntH.Len(); i++) {
00185     DegToCntV.Add(TIntPr(DegToCntH.GetKey(i), DegToCntH[i])); }
00186   DegToCntV.Sort();
00187 }
00188 
00189 template <class PGraph>
00190 void GetInDegCnt(const PGraph& Graph, TFltPrV& DegToCntV) {
00191   TIntH DegToCntH;
00192   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00193     DegToCntH.AddDat(NI.GetInDeg())++; }
00194   DegToCntV.Gen(DegToCntH.Len(), 0);
00195   for (int i = 0; i < DegToCntH.Len(); i++) {
00196     DegToCntV.Add(TFltPr(DegToCntH.GetKey(i).Val, DegToCntH[i].Val)); }
00197   DegToCntV.Sort();
00198 }
00199 
00200 template <class PGraph>
00201 void GetOutDegCnt(const PGraph& Graph, TIntPrV& DegToCntV) {
00202   TIntH DegToCntH;
00203   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00204     DegToCntH.AddDat(NI.GetOutDeg())++; }
00205   DegToCntV.Gen(DegToCntH.Len(), 0);
00206   for (int i = 0; i < DegToCntH.Len(); i++) {
00207     DegToCntV.Add(TIntPr(DegToCntH.GetKey(i), DegToCntH[i])); }
00208   DegToCntV.Sort();
00209 }
00210 
00211 template <class PGraph>
00212 void GetOutDegCnt(const PGraph& Graph, TFltPrV& DegToCntV) {
00213   TIntH DegToCntH;
00214   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00215     DegToCntH.AddDat(NI.GetOutDeg())++; }
00216   DegToCntV.Gen(DegToCntH.Len(), 0);
00217   for (int i = 0; i < DegToCntH.Len(); i++) {
00218     DegToCntV.Add(TFltPr(DegToCntH.GetKey(i).Val, DegToCntH[i].Val)); }
00219   DegToCntV.Sort();
00220 }
00221 
00222 template <class PGraph>
00223 void GetDegCnt(const PGraph& Graph, TIntPrV& DegToCntV) {
00224   TIntH DegToCntH;
00225   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00226     DegToCntH.AddDat(NI.GetDeg())++; }
00227   DegToCntV.Gen(DegToCntH.Len(), 0);
00228   for (int i = 0; i < DegToCntH.Len(); i++) {
00229     DegToCntV.Add(TIntPr(DegToCntH.GetKey(i), DegToCntH[i])); }
00230   DegToCntV.Sort();
00231 }
00232 
00233 template <class PGraph>
00234 void GetDegCnt(const PGraph& Graph, TFltPrV& DegToCntV) {
00235   TIntH DegToCntH;
00236   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00237     DegToCntH.AddDat(NI.GetDeg())++; }
00238   DegToCntV.Gen(DegToCntH.Len(), 0);
00239   for (int i = 0; i < DegToCntH.Len(); i++) {
00240     DegToCntV.Add(TFltPr(DegToCntH.GetKey(i).Val, DegToCntH[i].Val)); }
00241   DegToCntV.Sort();
00242 }
00243 
00244 template <class PGraph> 
00245 void GetDegSeqV(const PGraph& Graph, TIntV& DegV) {
00246   DegV.Gen(Graph->GetNodes(), 0);
00247   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00248     DegV.Add(NI.GetDeg()); 
00249   }
00250 }
00251 
00252 template <class PGraph> 
00253 void GetDegSeqV(const PGraph& Graph, TIntV& InDegV, TIntV& OutDegV) {
00254   InDegV.Gen(Graph->GetNodes(), 0);
00255   OutDegV.Gen(Graph->GetNodes(), 0);
00256   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00257     InDegV.Add(NI.GetInDeg()); 
00258     OutDegV.Add(NI.GetOutDeg());
00259   }
00260 }
00261 
00262 template <class PGraph> 
00263 void GetNodeInDegV(const PGraph& Graph, TIntPrV& NIdInDegV) {
00264   NIdInDegV.Reserve(Graph->GetNodes(), 0);
00265   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00266     NIdInDegV.Add(TIntPr(NI.GetId(), NI.GetInDeg()));
00267   }
00268 }
00269 
00270 template <class PGraph> 
00271 void GetNodeOutDegV(const PGraph& Graph, TIntPrV& NIdOutDegV) {
00272   NIdOutDegV.Reserve(Graph->GetNodes(), 0);
00273   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00274     NIdOutDegV.Add(TIntPr(NI.GetId(), NI.GetOutDeg()));
00275   }
00276 }
00277 
00278 template <class PGraph>
00279 int CntUniqUndirEdges(const PGraph& Graph) {
00280   TIntSet NbrSet;
00281   int Cnt = 0;
00282   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00283     NbrSet.Clr(false);
00284     for (int e = 0; e < NI.GetDeg(); e++) { // unique neighbors of a node
00285       if (NI.GetNbrNId(e) != NI.GetId()) { // skip self-edges
00286         NbrSet.AddKey(NI.GetNbrNId(e)); }
00287     }
00288     Cnt += NbrSet.Len();
00289   }
00290   return Cnt / 2;
00291 }
00292 
00293 template <class PGraph>
00294 int CntUniqDirEdges(const PGraph& Graph) {
00295   TIntSet NbrSet;
00296   int Cnt = 0;
00297   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00298     NbrSet.Clr(false);
00299     for (int e = 0; e < NI.GetOutDeg(); e++) { // unique out-neighbors of a node
00300       if (NI.GetOutNId(e) != NI.GetId()) { // skip self-edges
00301         NbrSet.AddKey(NI.GetOutNId(e)); }
00302     }
00303     Cnt += NbrSet.Len();
00304   }
00305   return Cnt;
00306 }
00307 
00308 template <class PGraph>
00309 int CntUniqBiDirEdges(const PGraph& Graph) {
00310   if (! Graph->HasFlag(gfDirected)) { // graph is undirected
00311     return CntUniqUndirEdges(Graph);  // then every edge is bi-directional
00312   }
00313   TIntSet NbrSet;
00314   int Cnt = 0;
00315   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00316     const int SrcId = NI.GetId();
00317     for (int e = 0; e < NI.GetOutDeg(); e++) {
00318       const int DstId = NI.GetOutNId(e);
00319       if (DstId <= SrcId) { continue; } // count each un-dir edge only once
00320       if (Graph->IsEdge(DstId, SrcId)) { Cnt++; }
00321     }
00322   }
00323   return Cnt;
00324 }
00325 
00326 template <class PGraph> 
00327 int CntSelfEdges(const PGraph& Graph) {
00328   int Cnt = 0;
00329   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00330     for (int e = 0; e < NI.GetOutDeg(); e++) {
00331       if (NI.GetId() == NI.GetOutNId(e)) { Cnt++; }
00332     }
00333   }
00334   return Cnt;
00335 }
00336 
00337 template <class PGraph>
00338 PGraph GetUnDir(const PGraph& Graph) {
00339   PGraph NewGraphPt = PGraph::New();
00340   *NewGraphPt = *Graph;
00341   MakeUnDir(NewGraphPt);
00342   return NewGraphPt;
00343 }
00344 
00345 template <class PGraph>
00346 void MakeUnDir(const PGraph& Graph) {
00347   CAssert(HasGraphFlag(typename PGraph::TObj, gfDirected)); // graph has to be directed
00348   TIntPrV EdgeV;
00349   for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00350     const int SrcNId = EI.GetSrcNId();
00351     const int DstNId = EI.GetDstNId();
00352     if (! Graph->IsEdge(DstNId, SrcNId)) {
00353       EdgeV.Add(TIntPr(DstNId, SrcNId));
00354     }
00355   }
00356   for (int i = 0; i < EdgeV.Len(); i++) {
00357     Graph->AddEdge(EdgeV[i].Val1, EdgeV[i].Val2);
00358   }
00359 }
00360 
00361 template <class PGraph>
00362 void AddSelfEdges(const PGraph& Graph) {
00363   TIntV EdgeV;
00364   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00365     const int NId = NI.GetId();
00366     if (! Graph->IsEdge(NId, NId)) {
00367       EdgeV.Add(NId);
00368     }
00369   }
00370   for (int i = 0; i < EdgeV.Len(); i++) {
00371     Graph->AddEdge(EdgeV[i], EdgeV[i]);
00372   }
00373 }
00374 
00375 namespace TSnapDetail {
00376 
00377 template <class PGraph, bool IsMultiGraph>
00378 struct TDelSelfEdges { // not a multigraph graph
00379   static void Do(const PGraph& Graph) {
00380     TIntV EdgeV;
00381     // node graph, no explicit edge ids
00382     for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00383       if (EI.GetSrcNId() == EI.GetDstNId()) {
00384         EdgeV.Add(EI.GetSrcNId());
00385       }
00386     }
00387     for (int i = 0; i < EdgeV.Len(); i++) {
00388       Graph->DelEdge(EdgeV[i], EdgeV[i]);
00389     }
00390   }
00391 };
00392 
00393 template <class PGraph>
00394 struct TDelSelfEdges<PGraph, true> { // mutligraph specialization
00395   static void Do(const PGraph& Graph) {
00396     TIntV EdgeV;
00397     for (typename PGraph::TObj::TEdgeI EI = Graph->BegEI(); EI < Graph->EndEI(); EI++) {
00398       if (EI.GetSrcNId() == EI.GetDstNId()) {
00399         IAssert(EI.GetId() >= 0); // real edge id
00400         EdgeV.Add(EI.GetId());
00401       }
00402     }
00403     for (int i = 0; i < EdgeV.Len(); i++) { // delete all edges between a pair of nodes
00404       Graph->DelEdge(EdgeV[i]);
00405     }
00406   }
00407 };
00408 
00409 } // namespace TSnapDetail
00410 
00411 template <class PGraph>
00412 void DelSelfEdges(const PGraph& Graph) {
00413   TSnapDetail::TDelSelfEdges<PGraph, HasGraphFlag(typename PGraph::TObj, gfMultiGraph)>
00414     ::Do(Graph);
00415 }
00416 
00417 template <class PGraph>
00418 void DelNodes(PGraph& Graph, const TIntV& NIdV) {
00419   for (int n = 0; n < NIdV.Len(); n++) {
00420     Graph->DelNode(NIdV[n]);
00421   }
00422 }
00423 
00424 template <class PGraph>
00425 void DelZeroDegNodes(PGraph& Graph) {
00426   TIntV DelNIdV;
00427   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00428     if (NI.GetDeg() == 0) {
00429       DelNIdV.Add(NI.GetId());
00430     }
00431   }
00432   for (int i = 0; i < DelNIdV.Len(); i++) {
00433     Graph->DelNode(DelNIdV[i]);
00434   }
00435 }
00436 
00437 template <class PGraph>
00438 void DelDegKNodes(PGraph& Graph, const int& OutDegK, const int& InDegK) {
00439   TIntV DelNIdV;
00440   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00441     if (NI.GetOutDeg() == OutDegK || NI.GetInDeg() == InDegK) {
00442       DelNIdV.Add(NI.GetId());
00443     }
00444   }
00445   for (int i = 0; i < DelNIdV.Len(); i++) {
00446     Graph->DelNode(DelNIdV[i]);
00447   }
00448 }
00449 
00450 // tree has directed edges -- so root is a well-defined
00451 // children point to a parent
00452 template <class PGraph>
00453 bool IsTree(const PGraph& Graph, int& RootNId) {
00454   if (Graph->GetNodes() == 1 && Graph->GetEdges() == 0) {
00455     RootNId = Graph->BegNI().GetId();
00456     return true;
00457   }
00458   RootNId = -1;
00459   if (Graph->GetNodes() != Graph->GetEdges()+1) { return false; }
00460   int NZeroOutDeg = 0;
00461   int ZeroOutDegN = -1;
00462   for (typename PGraph::TObj::TNodeI NI = Graph->BegNI(); NI < Graph->EndNI(); NI++) {
00463     if (NI.GetOutDeg() == 0) {
00464       ZeroOutDegN = NI.GetId();  NZeroOutDeg++;
00465     }
00466     if (NI.GetDeg() == 0) { return false; } // isolated nodes
00467   }
00468   if (NZeroOutDeg==1) {
00469     if (! TSnap::IsConnected(Graph)) { return false; }
00470     RootNId = ZeroOutDegN;  return true;
00471   }
00472   return false;
00473 }
00474 
00475 // tree signature -- for each level we sort the node in-degrees and concatenate them into a vector
00476 template <class PGraph>
00477 void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig) {
00478   CAssert(HasGraphFlag(typename PGraph::TObj, gfDirected));
00479   Sig.Gen(Graph->GetNodes(), 0);
00480   TSnapQueue<int> NIdQ(Graph->GetNodes());
00481   NIdQ.Push(RootNId);
00482   int LastPos = 0, NodeCnt = 1;
00483   while (! NIdQ.Empty()) {
00484     const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top());  NIdQ.Pop();
00485     IAssert(Node.GetInDeg()==0 || Node.GetOutDeg()==0); // child points or is-pointed to by the parent
00486     if (Node.GetInDeg() != 0) {
00487       for (int e = 0; e < Node.GetInDeg(); e++) {
00488         NIdQ.Push(Node.GetInNId(e)); }
00489     } else if (Node.GetOutDeg() != 0) {
00490       for (int e = 0; e < Node.GetOutDeg(); e++) {
00491         NIdQ.Push(Node.GetOutNId(e)); }
00492     }
00493     Sig.Add(Node.GetInDeg());
00494     if (--NodeCnt == 0) {
00495       for (int i = LastPos; i < Sig.Len(); i++) NodeCnt += Sig[i];
00496       Sig.QSort(LastPos, Sig.Len()-1, false);
00497       LastPos = Sig.Len();
00498     }
00499   }
00500 }
00501 
00502 // tree signature -- for each level we sort the node in-degrees and concatenate them into a vector
00503 template <class PGraph>
00504 void GetTreeSig(const PGraph& Graph, const int& RootNId, TIntV& Sig, TIntPrV& NodeMap) {
00505   CAssert(HasGraphFlag(typename PGraph::TObj, gfDirected));
00506   NodeMap.Gen(Graph->GetNodes(), 0);
00507   Sig.Gen(Graph->GetNodes(), 0);
00508   TSnapQueue<int> NIdQ(Graph->GetNodes());
00509   NIdQ.Push(RootNId);
00510   int LastPos = 0, NodeCnt = 1;
00511   while (! NIdQ.Empty()) {
00512     const typename PGraph::TObj::TNodeI Node = Graph->GetNI(NIdQ.Top());  NIdQ.Pop();
00513     IAssert(Node.GetInDeg()==0 || Node.GetOutDeg()==0); // child points or is-pointed to by the parent
00514     if (Node.GetInDeg() != 0) {
00515       for (int e = 0; e < Node.GetInDeg(); e++) {
00516         NIdQ.Push(Node.GetInNId(e)); }
00517       NodeMap.Add(TIntPr(Node.GetInDeg(), Node.GetId()));
00518     } else if (Node.GetOutDeg() != 0) {
00519       for (int e = 0; e < Node.GetOutDeg(); e++) {
00520         NIdQ.Push(Node.GetOutNId(e)); }
00521       NodeMap.Add(TIntPr(Node.GetOutDeg(), Node.GetId()));
00522     }
00523     if (--NodeCnt == 0) {
00524       for (int i = LastPos; i < NodeMap.Len(); i++) {
00525         NodeCnt += NodeMap[i].Val1; }
00526       NodeMap.QSort(LastPos, NodeMap.Len()-1, false);
00527       LastPos = NodeMap.Len();
00528     }
00529   }
00530   for (int i = 0; i < NodeMap.Len(); i++) {
00531     Sig.Add(NodeMap[i].Val1); // degree dignature
00532     NodeMap[i].Val1 = NodeMap[i].Val2;
00533     NodeMap[i].Val2 = i;
00534   }
00535 }
00536 
00537 }; // namespace TSnap