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